gifts2017

Вопросы про запросы. Продолжение. Cоединения

Опубликовал Николай Васильев (vasilev2015) в раздел Программирование - Практика программирования

Если Вас устраивает фраза "с индексами чё-то быстрее", то статья не для Вас. Судя по комментариям авторитетных коллег, единственная (!) статья на этом сайте, в которой обсуждается теоретическая скорость алгоритмов. Приведены замеры времени выполнения запросов. Построена аппроксимация, согласующаяся с теорией.

Мы все знаем, что индексы ускоряют выполнение запросов, особенно операций соединения. Однако более подробной информации найти не удавалось. И, наконец, мне попалась статья, на (странном) отличном от 1С языке. https://habrahabr.ru/post/278087/ Смотрите также http://www.sql.ru/articles/mssql/2007/051102mergejoin.shtml#20 Ниже  (очень) вольный пересказ, дополненный примерами.

В современном компьютере самое медленное устройство - жесткий диск. Скорость операций соединения в запросах пропорциональна количеству чтений, необходимых для выполнения операции. Все алгоритмы, описанные ниже, выполняются внутри SQL. Рассмотрим случаи:

  1. Если обе таблицы достаточно малы по размеру, каждая строка таблицы читается один раз, обе таблицы загружаются в оперативную память. Скорость пропорциональна суммарному количеству записей обеих таблиц. Наличие индексов не существенно. (N+M)  https://ru.wikipedia.org/wiki/Алгоритм_соединения_хэшированием
  2. Если таблицы большого размера, не могут быть загружены в оперативную память, индексов нет, то каждая строка одной таблицы сравнивается с каждой строкой другой таблицы. Цикл в цикле. Скорость пропорциональна произведению количества строк одной таблицы на количество строк другой таблицы. (N*M) https://ru.wikipedia.org/wiki/Алгоритм_соединения_вложенными_циклами
  3. Если одна таблица индексирована по условию соединения, а вторая – нет, то возможен случай, когда для каждой строки неиндексированной таблицы ищется соответствие по условию во второй, индексированной таблице. Чтобы лучше представить скорость поиска по индексу, вспомните детскую задачу: найти одну тяжелую монетку среди группы других одинаковых монет, используя весы. Монеты делятся на две группы одинакового количества, весами выбирается более тяжелая группа, операция повторяется. Количество необходимых взвешиваний при таком подходе равно степени двойки. Например: 4 монеты – 2 взвешивания, от 5 до 8 монет – 3 взвешивания, от 9 до 15 монет – 4 взвешивания. Если Вы еще помните, что такое логарифм, то наверное Вы уже догадались, что скорость соединения будет пропорциональна произведению количества строк в неиндексированной таблице на логарифм по основанию 2 от количества строк индексированной таблицы N LOG( M ). Наверняка будут комментарии, что монеты можно делить на три кучи, будут вопросы: почему основание 2. Предвосхищая их, замечу, что функция логарифма по основанию 2 линейно зависит от функции логарифма по основанию 3. Кстати, стоимость сортировки списка тоже равна N LOG( M ).
  4. В случае, если обе таблицы индексированы по условию соединения, соединение происходит даже быстрее ожиданий. SQL организует один цикл от 1 до суммы количества строк обеих таблиц, получая их содержимое по порядку. Скорость пропорциональна суммарному количеству записей обеих таблиц. (N+M) https://ru.wikipedia.org/wiki/Алгоритм_соединения_слиянием_сортированных_списков

Для сбора статистики по времени будем использовать три запроса, выполнять в цикле, каждый раз создавать заново, чтобы были одинаковые условия. Текст запросов примерно одинаковый, различия выделены комментариями. Количество строк в запросах изменяется: от 3000 до 30000. Полученные данные группируются в таблицу, делается вывод о зависимости скорости запроса в зависимости от числа строк.


	ПереченьЗапросов = Новый СписокЗначений;
	ПереченьЗапросов.Добавить("БезИндекса",
		"ВЫБРАТЬ ПЕРВЫЕ 999
		|	Продажи.Регистратор
		//|	Продажи.*		
		|ПОМЕСТИТЬ ТабПример
		|ИЗ	РегистрНакопления.Продажи КАК Продажи
		//|УПОРЯДОЧИТЬ ПО	Регистратор
		//|ИНДЕКСИРОВАТЬ ПО Регистратор
		|;
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ТабПример1.*, ТабПример2.*
		|ИЗ
		|	ТабПример КАК ТабПример1
		|		ЛЕВОЕ СОЕДИНЕНИЕ ТабПример КАК ТабПример2
		|		ПО ТабПример1.Регистратор = ТабПример2.Регистратор");
		
	ПереченьЗапросов.Добавить("МногоПолей",
		"ВЫБРАТЬ ПЕРВЫЕ 999
		//|	Продажи.Регистратор
		|	Продажи.*		
		|ПОМЕСТИТЬ ТабПример
		|ИЗ	РегистрНакопления.Продажи КАК Продажи
		//|УПОРЯДОЧИТЬ ПО Регистратор
		|ИНДЕКСИРОВАТЬ ПО Регистратор
		|;
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ТабПример1.*, ТабПример2.*
		|ИЗ
		|	ТабПример КАК ТабПример1
		|		ЛЕВОЕ СОЕДИНЕНИЕ ТабПример КАК ТабПример2
		|		ПО ТабПример1.Регистратор = ТабПример2.Регистратор");
		
	ПереченьЗапросов.Добавить("Принудительно",
		"ВЫБРАТЬ ПЕРВЫЕ 999
		//|	Продажи.Регистратор
		|	Продажи.*		
		|ПОМЕСТИТЬ ТабПример
		|ИЗ	РегистрНакопления.Продажи КАК Продажи
		|УПОРЯДОЧИТЬ ПО	Регистратор
		|ИНДЕКСИРОВАТЬ ПО Регистратор
		|;
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ТабПример1.*, ТабПример2.*
		|ИЗ
		|	ТабПример КАК ТабПример1
		|		ЛЕВОЕ СОЕДИНЕНИЕ ТабПример КАК ТабПример2
		|		ПО ТабПример1.Регистратор = ТабПример2.Регистратор");	
		
	//создаем пустую таблицу значений.
	Запрос = Новый Запрос("Выбрать 0 БезИндекса, 0 МногоПолей, 0 Принудительно Где Ложь");
	Таб = Запрос.Выполнить().Выгрузить();
	
	//цикл по количеству строк
	Для СтрокЗапроса1 = 1 По 10 Цикл		
		СтрокЗапроса = СтрокЗапроса1 * 3000;		
		СтрокаТаб = Таб.Добавить();		
		
		//цикл по типу запросов
		Для Каждого СтрЗапрос ИЗ ПереченьЗапросов Цикл
			Запрос = Новый Запрос;
			Запрос.Текст = СтрЗаменить( СтрЗапрос.Представление, "999", формат(СтрокЗапроса,"ЧГ=0") );
			Время1 = ТекущаяУниверсальнаяДатаВМиллисекундах();
			Результат = Запрос.Выполнить();
			СтрокаТаб[СтрЗапрос.Значение] = (ТекущаяУниверсальнаяДатаВМиллисекундах()-Время1) * 0.001;
		КонецЦикла;
	КонецЦикла;
	
	таб.ВыбратьСтроку();

В результате получилась таблица:

Кол. строк / 3000 БезИндекса МногоПолей Принудительно
1 0,073 2,526 0,547
2 0,111 6,837 0,921
3 0,137 12,118 1,817
4 0,192 16,429 3,519
5 0,235 19,551 3,723
6 0,29 22,934 3,387
7 0,334 27,816 4,952
8 0,399 36,213 6,143
9 0,452 39,354 6,325
10 0,488 44,717 7,663

Во первых, для меня стало неожиданностью, что запрос "МногоПолей" выполняется медленно. Несмотря на слово "Индексировать", индекс не используется. Конечно, регистр накопления индексирован по регистратору. Не думаю, что дело в звездочке. Пробовал по-разному. Но на моей базе так. Для некоторых регистров накопления в таких же случаях индексы работают. На ваших базах может быть другая ситуация. Буду признателен за комментарии.

Для этой таблицы составил аппроксимацию. Значения близкие. Обозначим А2 = (Кол. строк / 3000).

БезИндекса = A2 / 2;  МногоПолей = A2*A2 / 2; Принудительно =LOG(A2;2)*A2 /4

Кол. строк / 3000 БезИндекса МногоПолей Принудительно
1 0,05 0,5 0,00
2 0,1 2 0,50
3 0,15 4,5 1,19
4 0,2 8 2,00
5 0,25 12,5 2,90
6 0,3 18 3,88
7 0,35 24,5 4,91
8 0,4 32 6,00
9 0,45 40,5 7,13
10 0,5 50 8,30

Колонка "Принудительно" показывает стоимость операции N LOG( M ) из-за того, что перед соединением таблиц было проведено принудительное индексирование командой "упорядочить". Это не моя идея. Цитирую статью 1998 года: "Оптимизатор Oracle будет использовать индексное сканирование, если запрос содержит раздел ORDER BY с указанием индексированного столбца.". http://www.sbras.ru/win/docs/db/sql/sql25.htm Мне кажется, что популярное сейчас "Горизонтальное масштабирование" связано только лишь с этой особенностью индекса.

Полученные численные данные согласуются с ожиданием. Причем, это не один замер времени, а группа замеров, образующая предсказанную линейную или квадратичную зависимость.

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Антон Стеклов (asved.ru) 06.07.16 16:48
1 - описывается Table scan, операция логического чтения
2 - описывается nested loops - алгоритм сравнения таблиц, выполняемый уже после чтения. Вы путаете разные логические этапы плана.
3 - да, в первом случае Index seek как чтение ограничивает количество строк с одной из сторон сравнения. Каким же алгоритмом будет делаться сравнение - неизвестно.
4 - С двух сторон Index seek, каким же алгоритмом будет делаться сравнение - неизвестно. Я могу сделать так, что в конкретной БД соединение по полностью индексному условию будет выполняться очень долго. И исправить ситуацию одной командой СУБД.

Nested Loops на существенных количествах строк - это почти всегда ошибка прогнозирования, как следствие встает вопрос актуальности статистик, никоим образом от синтаксиса запроса не зависящий.

Ну и в целом - без планов запроса такие вещи объяснять не нужно, потому что объяснение это притянуто за уши и в целом неверно.
2. Alexander Speshilov (speshuric) 07.07.16 00:05
Нельзя так мерять. Навскидку ошибки, которые стыдно даже читать в "HighLoad":
  • Запросы рассматривать без СУБД нельзя. Даже примитивные. Про какую из 5 поддерживаемых СУБД вы пишете (MS, Ora, IBM, Postgres, 1C) и про какую её версию?
  • Соединения двух таблиц интересны в очень-очень специфичных случаях, например, когда вы демонстрируете особенность СУБД и смогли (а это не просто) построить репро на одном соединении.
  • Смотреть время выполнения запроса можно примерно с 20-30 оговорками. В принципе. Или обосновать, почему этого достаточно. Без упоминания статистик, планов запросов, внятного обоснования структуры таблиц обосновать не получится.
  • Без плана запроса и обоснования, что этот план релевантен для любых разумных статистик сравнивать запросы нельзя. Может у вас один регистратор 100000 движений генерит? Что мы тогда соединяем?
  • Во временных таблицах у вас неуникальный индекс. Кластеризованный (в MS SQL). Говорить, что он "не используется" - расписываться в непонимании работы СУБД.
  • Примеры 2 и 3 если что вернут потенциально разные данные (из-за УПОРЯДОЧИТЬ). Что вы сравнили? Сколько строк в результатах выборок?
  • Не видно какую часть занимает выборка в временную таблицу и какую второй запрос. Там вас может ждать сюрприз. И это еще не обсуждая, что построение индекса вовсе не бесплатная операция.
  • Продажи - если мне не изменяет память жирный оборотный регистр с горой полей. С чего вы решили, что оно бесплатно заливается во временную таблицу и тянется на клиента?
  • 1С переиспользует временные таблицы (ну по крайней мере 2 года назад так было). Это может неожиданно влиять на запросы.
  • Код выполняется на клиенте или на сервере предприятия?
  • Я понятия не имею, какая у вас конфигурация сервера: сколько памяти, какие диски, как по ним разнесены базы, отдельно ли темпдб, какая в этот момент нагрузка на сервере, сколько файлов в темпдб, где клиент, где сервер предприятия и еще примерно сотня параметров только сервера СУБД. А вы не озвучивая всего этого делаете выводы. Непрофессионально.
  • Вы почему-то используете левое соединение. Мне этот выбор не очевиден для ваших запросов и вашего способа наполнения таблиц (одна и та же таблица, которая соединяется по потенциально неуникальному полю)
Дальше даже писать лень. И, кстати, если вы не переврали пересказываемую статью (ссылки на оригинал нет, сравнить не могу), то выбросьте её из головы, она плохая.
gadjik; prog.ert; Yashazz; DrAku1a; +4 Ответить 3
3. Антон Стеклов (asved.ru) 08.07.16 22:00
(2) speshuric, офигеть, Вы даже запросы не поленились почитать. Я, честно говоря, после прочтения текста на запросы уже не увидел смысла смотреть.
4. Николай Васильев (vasilev2015) 13.07.16 17:05
(2) speshuric, Спасибо.
Действительно, численные примеры приведены без конкретных условий. Однако даже такие данные имеют смысл: служат для построения математической модели. Восстановление модели по данным - основная задача науки "математическая статистика". (да, я Математик.)
Количество строк в запросах указано.
Выборка во временную таблицу происходит быстро (блин, опять непрофессионально :)))

Давайте выбросим плохие статьи, не будем интересоваться алгоритмами, а просто будем твердить мантру "С индексами быстрее".
5. Николай Васильев (vasilev2015) 13.07.16 17:31
(3) asved.ru,
Какую статью в рамках этого сайта Вы бы могли порекомендовать, где описаны алгоритмы соединений, скорость алгоритмов ?
6. Николай Васильев (vasilev2015) 13.07.16 21:42
(2) speshuric,
убрал из раздела "Highload"
7. Антон Стеклов (asved.ru) 13.07.16 22:21
(5) vasilev2015, боюсь, в рамках этого сайта с теорией плохо. Поищите по трекерам книги по производительности MSSQL. Короткевича, например.
Вот это видео обязательно посмотрите: https://www.youtube.com/watch?v=4yHc8-Idf-w
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа