[Из песочницы] «Распределение в запросе» или «избавляемся от перебора»23.12.2016 01:33

Хороший перебор — это отсутствие перебора. Рассмотрим пример замены полного перебора запросом.

В свое время, года 3 назад, возникла необходимость оптимизации конфигурации 1С и устранения ее узких мест в одной компании. Одним из таких узких мест оказался, казалось бы, безобидный, механизм распределения товаров в реализации по сериям. Суть в том, что строк распределялось достаточно много и было это очень медленно. Не миллионы за раз, конечно, но на это самое распределение для одного документа могло уходить до минуты.

Запрос специально привожу на T-SQL, т.к. думаю, что Хабравцам это будет ближе.

В общем от этого дела становилось всем очень грустно, т.к. параллельно бухгалтера препроводили документы, другие операторы тоже формировали документы отгрузки и когда отгружали «большого» клиента — жизнь на некоторое время замирала.

К слову сказать, размер базы 1С за 2–3 года на тот момент составлял ~500 Гб, заказов от одного клиента за день могло прийти десяток-другой, а в некоторых из них строк могло быть более 1000, в общем «Реализация товаров и услуг» на 1000 строк — это не было ничем сверхъестественным. Реиндексация, обновление статистики, шринк и другие необходимые процедуры проводились регулярно, но сейчас речь не об этом. Вернемся к нашему объекту оптимизации. На тот момент механизм распределения был до банального прост:

  1. Запросом получали остатки по сериям (Номенклатура — Серия — Количество).
  2. Другим запросом получали таблицу товаров к отгрузке (Номенклатура — Заказ покупателя — Количество).
  3. Проходил обыкновенный перебор для каждой номенклатуры по принципу »Пока КоличествоКРаспределению > 0 Цикл……… ».

Т.к. я всегда придерживался позиции, что сам факт перебора на больших объемах данных — это уже само по себе узкое место, то возможность «улучшения» алгоритма перебора я даже рассматривать не планировал. Нужна была альтернатива. Также на тот момент я уже давно набил руку в оптимизации сложных запросов и укрепился в выводе, что нет ни одной задачи, которую нельзя было бы решить исключительно запросом и точно знал, что качественный запрос (пакет запросов) в 99% случаев окажется самым эффективным решением, чем какая-либо пост-обработка результатов запроса. Вопрос оставался только в нахождении этого решения).

Выходил я на перекур с достаточно тривиальным условием задачи (распределить количество по измерениям одной таблицы на количество по измерениям из другой) и 2-мя тезисами:

  • Мы имеем 2 таблицы, которые и так собираются запросом.
  • SQL не знает никакого «Распределить». SQL знает только «больше», «меньше», «равно» (утрированно). Надо дать ему некий параметр для сравнения. Числовой параметр, по которому будет понятно какое количество еще можно распределить в условную строку.

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

У нас есть складские ячейки с количеством вмещаемого в них товара с одной стороны (A, B, C, D) и сам товар (X, Y, Z), который необходимо «как-то» разложить по этим ячейкам, но так, чтоб в ячейку не положили больше товара, чем может быть в ней места.

A — 10 мест
B — 1 место
C — 5 мест
D — 8 мест

X — 13 шт
Y — 1 шт
Z — 4 шт


Результатом должна стать таблица распределения:
A-X-10
B-X-1
C-X-2
C-Y-1
C-Z-2
D-Z-2

Для этого нам надо определить порядок распределения, сделать это оказалось до банального просто: 
select 
	t1.Cell, 
	t1.Qty, 
	ISNULL(sum(t2.Qty),0)+1 as OrderBottom, 
	ISNULL(sum(t2.Qty),0)+t1.Qty as OrderTop
into OrderedCells
from Cells as t1
	left join Cells as t2 
		on t1.Cell > t2.Cell
Group by 
	t1.Cell, 
	t1.Qty

Кстати, здесь же можно учесть и порядок распределения, если, например, в какие-то ячейки товар надо класть в первую очередь. Решается изменением условия в соединении.

Тоже самое и с товарами: 

select 
	t1.Goods, 
	t1.Qty, 
	ISNULL(sum(t2.Qty),0)+1 as OrderBottom, 
	ISNULL(sum(t2.Qty),0)+t1.Qty as OrderTop
into OrderedGoods
from Goods as t1
	left join Goods as t2 
		on t1.Goods > t2.Goods
Group by 
	t1.Goods, 
	t1.Qty

Для простоты понимания разложу все эти позиции поштучно в таблице и наложу одну на другую в порядке распределения:

image

Нам просто нужно написать граничные условия. А теперь осталось просто соединить эти таблицы и получим наш результат: 

select
	OrderedCells.Cell,
	OrderedGoods.Goods,
	case when OrderedGoods.OrderTop < OrderedCells.OrderTop
		then OrderedGoods.OrderTop
	else OrderedCells.OrderTop
	end - case when OrderedGoods.OrderBottom > OrderedCells.OrderBottom
		then OrderedGoods.OrderBottom
	else OrderedCells.OrderBottom
	end + 1 as Qty
from
	OrderedCells
		inner join OrderedGoods
			on OrderedCells.OrderBottom <= OrderedGoods.OrderTop
			and OrderedCells.OrderTop >= OrderedGoods.OrderBottom

Сразу оговорюсь, что в запросе умышленно добавлено большее количество полей, чем надо. Можно было бы обойтись и одной границей распределения (нарастающим итогом) и не делать »+1», но как мне показалось — в таком виде это более наглядно для понимания. Оптимизацию запросов мы в этой теме не рассматриваем, поэтому и индексы здесь тоже не описаны. Ну, а более сложные алгоритмы распределения (по нескольким измерениям, например) решаются только изменением условий соединения и проверки границ.

Вот и все. В итоге вместо минут ожидания на тех же объемах данных этот запрос выполнялся считанные миллисекунды.

Прошу простить за обилие лирики в этой статье. Хотелось дать не математическое решение узкой задачи, а поделиться концептуальным подходом к решению подобных задач, именно ходом своих мыслей.

Комментарии (1)

  • 22 декабря 2016 в 23:34

    +1

    ↑

    ↓

    Еще бы планы запросов, цены бы не было

© Habrahabr.ru