«Розподіл в запиті» або «позбавляємося від перебору»

Хороший перебір — це відсутність перебору. Розглянемо приклад заміни повного перебору запитом.

У свій час, роки 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
Cells left join 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», але як мені здалося – в такому вигляді це більш наочно для розуміння. Оптимізацію запитів ми в цій темі не розглядаємо, тому й індекси тут теж не описані. Ну а більш складні алгоритми розподілу (за кількома вимірами, наприклад) вирішуються тільки зміною умов з'єднання і перевірки кордонів.

От і все. У підсумку замість хвилин очікування на тих же обсягах даних цей запит виконувався лічені мілісекунди.

Прошу пробачити за велику кількість лірики в цій статті. Хотілося дати не математичне рішення вузької завдання, а поділитися концептуальним підходом до вирішення подібних завдань, саме ходом своїх думок.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.