22.12.2016 15:54
alexandersh123 21 4400 Источник
Хороший перебор — это отсутствие перебора. Рассмотрим пример замены полного перебора запросом.

В свое время, года 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», но как мне показалось – в таком виде это более наглядно для понимания. Оптимизацию запросов мы в этой теме не рассматриваем, поэтому и индексы здесь тоже не описаны. Ну а более сложные алгоритмы распределения (по нескольким измерениям, например) решаются только изменением условий соединения и проверки границ.

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

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

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


  1. fishca
    22.12.2016 23:34
    #9979070
    +1

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


  1. vis_inet
    23.12.2016 08:00
    #9979294

    Очень интересно!
    А на форум 1С не писали про такое решение?


    1. fishca
      23.12.2016 15:09
      #9980284

      Уже почти: http://infostart.ru/public/568299/ ;)


      1. vis_inet
        23.12.2016 15:12
        #9980292

        Спасибо!


    1. Ifal
      23.12.2016 16:08
      #9980436

      http://infostart.ru/public/568299/


  1. matraskin
    23.12.2016 08:00
    #9979296

    Еще бы по русски (на языке 1с) написать запрос — тоже цены бы не было.


    1. vis_inet
      23.12.2016 08:11
      #9979304
      +1

      Так ведь почти один к одному…
      К тому же язык запросов 1С двуязычен — писать можно как на русском, так и на английском.


    1. SergeyGershkovich
      23.12.2016 16:08
      #9980438

      Автор молодец, наглядный пример оптимизации 1С!
      Но 1С-совцам лучше дать универсальную процедуру на языке 1С, которая для любой пары таблиц будет генерировать запрос распределения — это буде им проще для применения, чем каждый раз вникать в строгость неравенств по OrderTop и OrderBottom.


  1. am-amotion-city
    23.12.2016 10:48
    #9979594

    case 
  when OrderedGoods.OrderTop < OrderedCells.OrderTop
  then OrderedGoods.OrderTop
  else OrderedCells.OrderTop
  end

    А почему не:


    IF (OrderedGoods.OrderTop < OrderedCells.OrderTop, OrderedGoods.OrderTop, OrderedCells.OrderTop)


    1. Neikist
      23.12.2016 14:29
      #9980196

      Подозреваю что из за переложения с 1С, там именно аналогичным оператором в тексте запроса это делается, и не припомню чтобы там аналоги IF были.


      1. GSchultz
        23.12.2016 16:08
        #9980440

        ВЫБОР КОГДА <Условие> ТОГДА <Выражени1>
        ИНАЧЕ <Выражение2>
        КОНЕЦВЫБОРА


  1. AtomKrieg
    23.12.2016 11:30
    #9979716

    Алгоритм перебора может написать кодом или псевдокодом? Есть предположение что использовался двойной цикл и сложность алгоритма n^2. Но данные имеют структуру поэтому можно заменить на алгоритм сложности n*log n


  1. minamoto
    23.12.2016 12:16
    #9979844
    +1

    шринк и другие необходимые процедуры


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

    Это категорически неверно — исключайте шринк из обслуживания и вообще забудьте о том, что его можно делать регулярно. Он нужен, если вы единоразово зачищаете базу от большого количества данных — переносите часть данных в отдельную базу, готовите тестовый стенд, избавляетесь от исторических данных и т.п. Только в этом случае шринк действительно можно использовать, чтобы уменьшить место, занимаемое файлами базы данных.

    Шринк же на регулярной основе — это классический выстрел в ногу.


    1. vis_inet
      23.12.2016 15:13
      #9980294

      Почему «выстрел в ногу»?


      1. fishca
        23.12.2016 15:16
        #9980300
        +1

        Если базу не шринкуешь, то место переиспользуется


      1. minamoto
        23.12.2016 16:03
        #9980420
        +1

        Потому что шринк приводит к: а) фрагментации — данные ужимаются, поэтому вместо красивых последовательных страниц ваши данные начинают распихиваться по любым свободным местам базы, негативные последствия фрагментации, надеюсь, понятны; б) затратам на рост — в базе не остается свободного места, и когда вы пишете туда новые данные, сиквел сначала обратно расширяет файлы, что сказывается на производительности, причем, если ваш сервер настроен неверно — достаточно сильно может сказаться.


    1. artyomtiteev
      23.12.2016 16:08
      #9980442

      угу. админы просто советы такие дают. не нравится им. как и с логами не разобравшись — секут. хотя эти файлы иногда важнее файла данных…


  1. D_T
    23.12.2016 16:08
    #9980444

    Немного повникал в алгоритм, как понимаю задача сводится к следующей: берем товар X, выкладываем в ячейку А по мере наполнения переходим к следующей, затем выкладываем товар Y и т.д. пока все товары не разложены.

    Алгоритмически это решается в один проход. Никаких лишних переборов не надо.

    ИМХУ без SQL эта задача еще быстрее должна решаться, скорее всего тормоза у автора были в чем-то совсем другом, что просто исчезло при переписывании с нуля. Возможно какая-то специфика 1С, я в ней не силен.

    PS Первый запрос затестил: два Table scan, т.е. те самые лишние переборы, с которомы боролся автор.

    Желающим посмотреть планы
    create table #Cells (Cell char(1), Qty int)
insert into #Cells (Cell, Qty) values ('A', 10)
insert into #Cells (Cell, Qty) values ('B', 1)
insert into #Cells (Cell, Qty) values ('C', 5)
insert into #Cells (Cell, Qty) values ('D', 8)

select 
	t1.Cell, 
	t1.Qty, 
	ISNULL(sum(t2.Qty),0)+1 as OrderBottom, 
	ISNULL(sum(t2.Qty),0)+t1.Qty as OrderTop
from #Cells as t1
	left join #Cells as t2 
		on t1.Cell > t2.Cell
Group by 
	t1.Cell, 
	t1.Qty

drop table #Cells


    1. fishca
      23.12.2016 17:09
      #9980572

      Сканирование временных таблиц — это нормально.
      Может просто индекса нет чтобы его использовать.


    1. Ildarovich
      23.12.2016 17:35
      #9980626

      Вы попали в точку. На специализированном форуме (ссылка выше), где была размещена та же статья, автору указали на это несоответствие.
      В том подмножестве T-SQL, которое реализовано в 1С нет, например, оконных функций, которые в этой задаче позволяют быстро посчитать нарастающий итог — это два первых запроса. Также нет и RowNumber(), который помог бы третий запрос оптимизировать. Поэтому как будто все должно было быть наоборот: запрос должен был тормозить (там n^2), а код — снизить затраты до n. Как автор получил прямо противоположный результат — можно только догадываться.
      В статье действительно больше лирики, чем физики.


  1. dsdr
    23.12.2016 16:08
    #9980446

    Я тоже однажды написал что-то подобное, но это было связано с распределением товарных остатков из двух регистров. Упрощённо, в одном регистре — измерения по складам и партиям, в другом — склад и серийные номера, и нужно было распределить серийные номера по партиям в пределах одного склада. Делалось однократно для переноса остатков между базами, скорее just for fun, чем для реального ускорения. Пришлось делать несколько временных таблиц, которые хитрым образом соединялись сами с собой. Уже, наверно, пару лет такого делать не приходилось.
    Первый подобный приём подсмотрел в книжке Габец и Гончарова «Простые примеры разработки». И там был пример: Как одним запросом получить таблицу расхождений курсов взаиморасчетов. Там как раз можно посмотреть логику объединения таблиц, чтобы получить нужное распределение.