0. ildarovich 6742 20.09.13 10:00 Сейчас в теме

Баттерфляй - метод быстрого расчета нарастающего итога в запросе

Описывается метод предельно быстрого расчета нарастающего итога в запросе для случая, когда суммируемые строки таблицы пронумерованы.
В качестве только одного из возможных примеров использования метода приведен отчет по остаткам номенклатуры на каждый интервал (минуту, час, день, месяц, квартал,год) заданного периода.

Перейти к публикации

Комментарии
Избранное Подписка Сортировка: Древо
1. kapustinag 20.09.13 20:19 Сейчас в теме
Да, это сильно. Снимаю шляпу.
При первом взгляде на текст запроса подумал, что выигрыш по времени начнет проявляться позже, так как стандартное решение содержит только операции сложения, а полученное Вами - много умножений, делений, вычитаний - то есть операций более медленных. Но с измерениями не поспоришь.
2. Yashazz 2883 21.09.13 22:20 Сейчас в теме
Ильдарович, а ты замерял в сравнении со штатными функциями СКД, которые теперь позволяют легко делать подобное? С "ВычислитьВыражение" и прочими? Что быстрее и оптимальнее по ресурсоёмкости?
4. ildarovich 6742 23.09.13 10:02 Сейчас в теме
(2) Нет, я этого не делал. "Нельзя объять необъятное" - пока сосредоточился на там, что можно сделать в самом запросе. С точки зрения быстроты, в коде, в отличии от запроса, нет проблемы обращения к предыдущим значениям ряда, поэтому там рассмотренная задача не представляет сложностей и решается быстро (метод "0" в обработке). Рассуждая логически, в СКД должно быть также, хотя все нужно проверять. С точки зрения оптимальности тут вообще нельзя ничего говорить, не определив всех условий конкретной практической задачи и не рассмотрев еще и разных последовательностей и комбинаций приемов, которые, возможно, нужно будет еще придумывать.
3. Поручик 4333 22.09.13 01:53 Сейчас в теме
Ужас. Статьи автора всегда читаю, как фантастику. Как в своё время читал описание Ады или Модулы-2. Кто в теме, тот в курсе.
spezc; корум; the1; +3 Ответить
47. spezc 594 06.04.17 04:53 Сейчас в теме
(3) Согласен, Сергей как из другой вселенной)))
5. foliage 23.09.13 10:27 Сейчас в теме
Прочтение статей автора не оставляет сомнений в его же "совсем общем" выводе.
6. Lemkus 23.09.13 12:02 Сейчас в теме
При нечетном количестве строк вроде не работает.
7. ildarovich 6742 23.09.13 12:59 Сейчас в теме
(6) Почему Вы так решили? - Скачайте и проверьте сами. - Метод работает на любом количестве строк(см. скриншот).
Прикрепленные файлы:
8. Lemkus 23.09.13 13:07 Сейчас в теме
(7) Пардон, невнимательно прошел по алгоритму
9. kuzev 40 23.09.13 17:02 Сейчас в теме
Занимался этой задачей год назад. Реализовал расчет простым запросом, как написано в начале статьи. Сравнивал только не номера строк, а даты. Данный прием потребовался для моделирования (расчета остатка на дату с учетом начального или конечного остатка, приходов и расходов).
ildarovich, запросы наше всё =)
12. ildarovich 6742 23.09.13 20:48 Сейчас в теме
(10) Ссылка относится к СКД. В статье речь идет о запросе. То есть результат получается не постобработкой результатов запроса в оперативной памяти в коде или СКД, а внутри запроса и с ним еще можно много чего после этого сделать. Интерес был в том, чтобы доказать, что ограничения реляционной модели манипулирования данными не такие уж и узкие, чтобы отказываться от нее при некоторых затруднениях.
14. kereo 55 23.09.13 21:09 Сейчас в теме
(12) это скорее заметка для себя =)
15. hogik 430 24.09.13 03:22 Сейчас в теме
(12)
"... ограничения реляционной модели манипулирования данными не такие уж и узкие, чтобы отказываться от нее при некоторых затруднениях."(с)
Сергей.
От неё (модели) не надо отказываться. Надо отказаться от языка "манипулирования данными"(с) в тех алгоритмах, где для его (языка) применения требуется голова Вашего уровня...
18. ildarovich 6742 25.09.13 01:39 Сейчас в теме
(15) Владимир! Я внимательно читаю Ваши комментарии. Но у меня есть своё, отличное от Вашего мнение на тему "реляционное vs навигационное" манипулирование данными. Мне представляется, что на данный момент правильность выбора концепции, заложенной в платформе, подтверждена практикой. Декларативный SQL-подобный язык запросов для извлечения данных, скриптовый процедурный язык для интерфейса и склейки различных механизмов, СКД - для представления (только ли?) данных пользователю. Брать за основу непроверенные временем технологии было бы и сейчас и тогда безответственно и недальновидно. А так, посмотрите: MSSQL, Postgre, DB2, Oracle. С чем другим мы бы сейчас работали, прими 1С в свое время другое решение? Взять проприетарную и очень проблемную Cashe и сложить все яйца в одну корзину? Придумать нечто совсем свое? Бежать впереди паровоза по непроторенному пути? Это непозволительная роскошь для фирмы, опирающейся на собственные силы. Возьмите ё-мобиль. Гораздо более хорошо исследованная и предсказуемая область, серьезные финансовые ресурсы. А результат тем не менее все еще не получен. Мы готовы ждать так долго в области информационных технологий?
Krasnyj; monkbest; hogik; +3 Ответить
11. Ёпрст 1036 23.09.13 17:55 Сейчас в теме
вот-вот, ключевое понятие - ид чего либо, например строки.
Не всегда это есть, к сожалению в обычных запросах. А спецом "нумеровать" результат - лишнее самосоединение.
Поентому, выигрыш решения..сомнительный.
13. ildarovich 6742 23.09.13 21:01 Сейчас в теме
(11) Да, нумерация нужна, но ее можно получить тем же приемом БЕЗ самосоединения.
Я не предлагаю этот прием как универсальный рецепт на все случаи жизни. В статье четко говорится, что при обработке в коде и в СКД затруднений с получением нарастающих итогов нет. Также говорится о том, что выигрыш начинается с больших значений числа строк - говорится каких. Кстати, есть более короткая версия того-же запроса, которая в файловом варианте работает на 30% быстрее (с использованием соединения, а не группировки в правом крыле). То есть выигрыш начинается еще с меньших цифр, чем сейчас указано.
16. ilov_boris 158 24.09.13 22:48 Сейчас в теме
"Где это можно использовать на практике?"
Нигде. Как умственное упражнение полезно. Но за использование подобного в продакшене нужно по рукам бить.
17. ildarovich 6742 25.09.13 00:57 Сейчас в теме
20. ilov_boris 158 25.09.13 09:51 Сейчас в теме
(17) это проще и нагляднее делать кодом. И кроме того есть регистры накопления для этих целей.
21. kereo 55 25.09.13 10:14 Сейчас в теме
(16) ilov_boris, задача из жизни сформировать отчет, где идет оценка склада по средней стоимости склада с нарастающим итогом с указаной даты и еще куча других цифр.
22. ildarovich 6742 25.09.13 10:16 Сейчас в теме
(16) Вот несколько практических задач:
1) Получить список менеджеров, установивших цены, которые в процентах максимально отличались от своих предыдущих значений;
2) Получить список номенклатурных позиций, отличающихся максимальной волатильностью цен, подсчитанной как частота изменений цен, больших чем среднее значение изменений;
3) Определить чек, в котором находится 1000-ая единица проданного товара (такие чеки будут участвовать в розыгрыше призов);
4) Пересчитать скидки по интервальной накопительной системе скидок при возврате товара;
5) Рассчитать выплаты по кредитной линии, если моменты выдачи и возврата денежных средств произвольны;
6) Рассчитать стоимость овердрафта по пластиковой карте в зависимости от его суммы и времени;
7) Рассчитать стоимость ответственного хранения (для сложных условий);
8) Провести пакетный расчет стоимости списания по скользящему среднему.
Все эти задачи имеют общее свойство - решаются с использованием тэта-соединений в запросах. То есть их трудоемкость определяется квадратичной зависимостью и может быть уменьшена до линейной применением предлагаемого приема.
Восьмой; корум; zaxarovsky; +3 Ответить
23. ilov_boris 158 25.09.13 10:27 Сейчас в теме
(22) "Все эти задачи имеют общее свойство -" решаются императивно.
SQL не для вычислений предназначен.
MrFlanker; hogik; +2 1 Ответить
24. kereo 55 25.09.13 14:04 Сейчас в теме
(23) ilov_boris, в налоговых инспекциях стоит система ЭОД(Электронная обработка данных), в которой очень много расчетов выполняет именно SQL, через запуск хранимых процедур, в т.ч. налогов.
25. hogik 430 25.09.13 18:33 Сейчас в теме
(24)
"много расчетов выполняет именно SQL, через запуск хранимых процедур"(с)

Сильный аргумент. :-) :-) :-)

Вот тут хорошо и кратко написано:

"Храни́мая процеду́ра — ... у них могут быть входные и выходные параметры и локальные переменные, в них могут производиться числовые вычисления и операции над символьными данными, результаты которых могут присваиваться переменным и параметрам. ... Кроме того, в хранимых процедурах возможны циклы и ветвления, то есть в них могут использоваться инструкции управления процессом исполнения."(с)
27. kereo 55 25.09.13 19:49 Сейчас в теме
(25), (26) hogik, Аргумент, может быть и не очень хороший.
Поясню, что я хотел этим сказать. Объем данных там очень большой, который используется для расчетов, в том числе и нарастающие итоги там тоже есть (к примеру регрессивная шкала начисления ЕСН или по новому страховых взносов). А пользуются этой системой по все России. Т. е. расчеты на SQL очень большого объема и применяемые не в одной и не 2-х организациях.

SQL это стандарт языка запросов. А хранимые процедуры написаны разве не на SQL?
Храни́мая процеду́ра — объект базы данных, представляющий собой набор SQL-инструкций

А вот, что написано в wikipedia на этот счет:
Со временем SQL усложнился — обогатился новыми конструкциями, обеспечил возможность описания и управления новыми хранимыми объектами (например, индексы, представления, триггеры и хранимые процедуры) — и стал приобретать черты, свойственные языкам программирования.
28. hogik 430 25.09.13 20:03 Сейчас в теме
(27)
"Аргумент, может быть и не очень хороший."(с)
Игорь (kereo).
Нет. Аргумент очень хороший. :-)
Т.к. подтверждает позицию/мнение оппонента.
26. hogik 430 25.09.13 19:12 Сейчас в теме
(24)
А чего Вы называете этими тремя буквами?
Многие называют SQL-ем всё, что называется СУБД. :-)
32. zaxarovsky 95 18.10.13 08:50 Сейчас в теме
19. hogik 430 25.09.13 02:01 Сейчас в теме
29. sapervodichka 25.09.13 22:10 Сейчас в теме
это просто Ужос!!! )))) (+1 поставил)
30. RailMen 30.09.13 01:40 Сейчас в теме
31. Silenser 510 30.09.13 14:14 Сейчас в теме
Статьи по запросам у автора очень интересны. Но я все же поддержу тех, кто считает, что подобные вычисления нужно разделять во времени, а не делать сиюминутно. Таблица итогов по периодам выглядит более прозрачно и понятнее, нежели динамически формируемый запрос. Возможно, это мои личные предпочтения, но динамически формируемые запросы я довольно сильно не люблю, т.к. крайне сложно читать логику и, зачастую, без отладчика разобрать мысль автора (не данного автора, а некого абстрактного программиста) крайне сложно.
Yakud3a; TeMochkiN; tormozit; корум; lunjio; It-developer; denis_aka_wolf; 3762515; MrFlanker; Valet; +10 Ответить
33. MrFlanker 165 18.01.14 18:22 Сейчас в теме
Публикация очень похожа на студенческую работу:... сделать понятные, простые вещи неудобным способом и назвать по своему.
34. Evil Beaver 6348 24.01.14 11:11 Сейчас в теме
35. ildarovich 6742 09.02.14 13:45 Сейчас в теме
В отчете "Возраст" остатков номенклатуры показан один из вариантов практического применения описанного метода.
36. speshuric 1124 19.02.14 13:21 Сейчас в теме
1. Не рассмотрен нарастающий итог с группировками. Сам по себе нарастающий итог - достаточно редкая задача, почти всегда интересует нарастающий итог в каком-то разрезе (например, контрагентов, товаров и т.п.). Как только появляются группировки, то возникает важная оговорка, что даже ресурсоёмкость начального "наивного" запроса растет лишь как квадрат самой толстой группы. А при грамотном разбиении на группы это уже не так страшно.
Тем более, если есть какие-то вспомогательные системы (например, хранимые остатки, как в РН), то размер максимальной группы не растёт так быстро.

2. Не совсем понял откуда оценка 4,5*N. Если из картинки, то там 4,5 для 8 записей и очевидно, что коэффициент 4,5 не сохранится для 16 записей. Там навскидку должно получаться что-то типа N*log(N). Но и эта оценка только количества операций суммирования: нет, например, оценки стоимости построения запроса, а в 1С в том виде, как вы написали, она не линейна от количества кусков.

3. В СУБД очень часто самым дефицитным ресурсом являются не процессоры, а количество дисковых операций и память. Да, для примитивной ситуации, когда есть только колонка сортировки и суммы, упереться в диски и память не получится. Но в реальной ситуации только кортеж группировки будет тянуть байт на 100-300. Тогда у вас tempdb захлебнётся (по памяти или дискам, они в данном случае взаимозаменяемы), ведь на суммирование нужно держать объём больше начального объёма таблицы (одно левое крыло уже больше). То есть на таблицах 10 и более ГБ батерфляй рискует грустно сдохнуть. "Наивный", правда, тоже сдохнет, но если не будет спасения в виде группировок.

4. Ну и если вы уж так упираетесь в нарастающий итог, то в SQL Server 2012 появились средства для их вычисления "одним запросом": MSDN: Пример В.Нахождение скользящей средней и кумулятивной суммы. Понятно, что это в 1С-ные запросы не попадает, но вариант точно быстрее и незатратный по памяти/дискам. Таким образом "непосредственно на языке T-SQL" ваше решение не следует использовать.

5. У вас колонка Ё не индексирована. Это влияет на план выполнения запроса. Не в десятки раз, конечно, но влияет.
37. ildarovich 6742 19.02.14 15:12 Сейчас в теме
(36) 1) Нарастающий итог с группировками не рассмотрен только для того, чтобы не усложнять изложение. Но это не является проблемой - в обработке, приложенной к статье и в отчете "Возраст" остатков номенклатуры, где также применяется данный метод, используются группировки - запрос становится лишь чуточку сложнее. Линейной зависимости величины затрат (времени, памяти) метода от числа строк группировки не нарушают.
2) У меня тоже сначала в голове крутилось N*log(N). Но на самом деле так было бы, если бы крылья бабочки имели равную ширину и не сужались бы быстро к центру (тогда бы это была и не бабочка). А поскольку крылья сужаются также как 1/log(N), то в итоге получаются ЛИНЕЙНАЯ ЗАВИСИМОСТЬ. Ведь сумма ряда 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 2 (двум!). С левой стороны 2N, с правой стороны 2N, ну и еще на вычитание 0,5N. Так и получается 4,5N. Для 8-ми, 16-ти и сколько угодного исходного количества записей.
3) Квадратики на схеме обозначают не только операции процессора (суммирование), но и чтение, запись, хранение. Получается, что по сравнением с простой обработкой таблицы (например, добавлением единицы ко всем записям), потребуется в 4,5 раза больше ресурсов (процесссора, чтения, записи, места в tempdb). Это не в 20 и не в 100 раз больше! То есть для большой ширины кортежа потребуется еще 3,5 этой ширины на работу метода - не думаю, что это заставит сдохнуть сервер.
4) Про возможности SQL Server 2012 я знаю. В начале статьи есть ссылка на исследование именно этой новой возможности. Но, согласитесь, что алгоритмическая возможность фундаментальнее. Мы тут остаемся в рамках реляционного подхода, строго следуя заветам К. Дж. Дейта [SQL и реляционная теория. Как грамотно писать код на SQL].
-
Действительными ограничениями метода я считаю отсутствие во многих задачах исходной порядковой нумерации строк, нарастающий итог которых требуется получить. Кроме того, сейчас появилась возможность быстро рассчитывать нарастающий итог вне запроса (в СКД), что также сужает (хотя это вопрос все еще открытый - доказательств пока нет) область применения метода.
утюгчеловек; speshuric; +2 Ответить
38. speshuric 1124 19.02.14 17:57 Сейчас в теме
(37)
По оценке. Да, ок, я понял почему линейно зависит, хотя и не 4,5. Левое крыло 2N, действительно, а правое у меня получается заметно тяжелее. Вроде бы 4N (за счет схемы Р0*Л8+Л4 в П4, П4 в Л4), но нужно проверить расчеты. Но линейно.

По группировкам. Получается, что если в одной группе примерно до 100 элементов, то проще обойтись треугольным запросом. Если больше - до 1000, то надо проверять. Дальше - скорее всего бабочка обгонит.

По памяти. Для итогового буфера запроса один фиг понадобится N записей. Так что, хотя в процессе выполнения бабочка и прожорливее, но на финише по памяти тоже всё относительно ок.

По тому что "фундаментальнее" я не соглашусь. В реляционной теории на самом деле много еще неустоявшихся моментов, а уж того в чем "Р"СУБД вовсе даже и не "Р" - пруд пруди. Собственнно Дейт и Дарвен в третьем манифесте (относительно связки с ОО) и других трудах еще 15 лет назад это описывали.
39. ildarovich 6742 21.02.14 09:25 Сейчас в теме
(38) В целом согласен с Вашими оценками - Вы уловили самую суть.
Хотел было поспорить по-поводу "фундаментальнее", но теперь передумал. Будет напоминать спор Шелдона и Леонарда (из известногоо сериала) по-поводу того, какая физика круче: теоретическая или экспериментальная. Результат предсказуем - каждый останется при своем мнении.
40. ildarovich 6742 21.02.14 13:02 Сейчас в теме
(38)(39) Все же не удержусь, чтобы привести аргументы в поддержку «фундаментальности» решения.
По сравнению с новыми оконными функциями сервера MS SQL 2012 метод оперирует более высокими уровнями абстракции, то есть слабо зависит от программной и аппаратной платформы, а может работать и без компьютера вообще!
Представьте себе, что вы стоите в многотысячной очереди в Храм, например. Вас, как и всех в очереди, конечно, интересует, когда Вы туда попадете. Попросите людей в очереди оценить время своей молитвы (или, как сейчас говорят, «попытки связаться с разработчиком») , прибавить его ко времени, записанного на листочке впереди стоящим человеком и передать этот листок по очереди дальше. Если оценить, что одному человеку на это потребуется примерно 20 секунд, то для 10 тысяч человек в очереди потребуется примерно 55 минут. Если же применить «бабочку» - расположить рядом еще 10 тысяч «счетчиков» в виде бинарного дерева (крыла бабочки), то результат будет получен уже примерно через 10 минут – в 5,5 раз быстрее. Для 100 тысяч человек получится уже 555 / 12 минут – в 50 раз быстрее (приблизительно). То есть ускоряется даже не «треугольник», а простой линейный подсчет. «Бабочка» дает возможность распараллеливания расчета нарастающего итога!
Так что стоит задуматься (не нам) над тем: - Не применить ли «бабочку» при реализации самих оконных функций в MS SQL для распараллеливания этих операций? А всякие модные сейчас распределенные вычисления и СУБД, Биг-Даты и тому подобное?
Вот, что я имел в виду, говоря, что данное решение более общее (фундаментальное).
41. speshuric 1124 21.02.14 17:15 Сейчас в теме
(40) Стоп-стоп.
1. Я не буду стоять в Храм. Давайте это лучше будет очередь улететь на Марс :)
2. 20 секунд и 10000 человек последовательно передают данные - это 200000 секунд. Это 55 часов. Не минут.
3. Левое крыло, если все будут действовать параллельно, просчитается за 16 итераций. Правое - тоже логарифм, но в уме что-то не прикину будет оверхэд или не будет. Пусть даже и не будет - всё равно 32 итерации 32*20 - 640 секунд. Отличный, кстати, результат.
4. Но если представить себе всю эту тусовку, то станет понятно, что управлять такой распараллеленной операцией будет ОЧЕНЬ тяжело. И возникнут оверхэды на синхронизацию, хождение и управление. Но, кстати, в час-полтора будет уложиться всё равно реально.

Это хорошая демонстрация бесконечного распараллеливания в "последовательной" задаче. И, да, он во всяких хадупах и т.п. проканает, наверное (хотя сходу у меня в голове этот алгоритм в мэп-редьюс не укладывается).
И я не спорю, что это эффективно и круто.
Я же функцию SUM-ORDER BY считаю потому более фундаментальной, что она не декларирует как считать. А считать она может как угодно (той же бабочкой). Собственно, мне кажется, это и была одна из главных идей РСУБД - отделить задачу от реализации.
HystriX; ildarovich; +2 Ответить
42. Sergey.Noskov 16.07.14 13:50 Сейчас в теме
В давние времена, когда брался за решение сложной задачи именно с мыслями "Какая интересная задачка, но мне любой запрос по плечу!" то приходилось ваять мегабайты строк запросов.
Потом, когда заинтересовался спецификой крупных внедрений и областью задач уровня 1С:Эксперт, прочитал просто гениальную фразу на диске ИТС: "Регистр должен быть самодостаточным" и образ мышления развернулся в сторону "Какая интересная задачка, надо хорошенько продумать архитектуру".
Понимаю, что нарастающий итог - задача не тривиальная, но и тут можно разработать архитектурное решение, которое покроет 90% сценариев формирования отчета при котором запрос будет до безобразия примитивным.
43. ildarovich 6742 17.07.14 12:14 Сейчас в теме
(42) serno, все это абстрактная философия.В конкретных случаях она может не помочь.
нарастающий итог - задача не тривиальная, но и тут можно разработать архитектурное решение, которое покроет 90% сценариев формирования отчета при котором запрос будет до безобразия примитивным
Конечно, нужно разрабатывать эти архитектурные решения и сравнивать затраты на поддержание в актуальном состоянии вспомогательных структур данных и выгоды в виде сокращения времени выполнения запроса. Однако, во-первых, здесь нет уверенности, что "кубиков", которые есть в 1С всегда будет достаточно для построения любых необходимых структур данных. Во-вторых, иногда находятся алгоритмические решения, которые дают очень большие выигрыши во времени без всяких вспомогательных структур данных. Один из примеров приведен в статье "Неоплаченные долги при распределении оплаты по правилу ФИФО одним запросом и намного быстрее, чем Вы думали". Вот такие решения я и ищу.
44. danila_inf 22.08.14 17:50 Сейчас в теме
Как решение достаточно оригинально.
Оценить можно с разных сторон.
И с точки зрения сборки запроса(- неудобно)
и по времени выполнения (+ быстрее)
Для меня лично ограничений больше чем возможностей.
В моей практике не было запросов(работающих на реальном предприятии), с нарастающим итогом выполняющихся очень долго. Так что следующий запрос с нарастающим итогом напишу по старинке))
45. ildarovich 6742 14.05.15 13:31 Сейчас в теме
Вот в этой статье http://habrahabr.ru/company/epam_systems/blog/247805/ говорится о том, что очень похожий метод применяется в параллельных алгоритмах "свертки", выполняемых графической подсистемой CUDA. Приведена очень похожая картинка. Метод назван Blelloch scan. Говорится о его высокой эффективности.
Похоже, что нарастающий итог - это задача prefix sum.
46. ildarovich 6742 13.07.16 13:45 Сейчас в теме
По тому же принципу можно считать нарастающий итог не сумм, а произведений. Тоже будет быстро.
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Автор новостных обзоров на тему 1С и бухучета
Санкт-Петербург
По совместительству

Ведущий программист 1С
Омск
зарплата от 70 000 руб. до 110 000 руб.
Полный день

Программист 1С
Екатеринбург
зарплата до 120 000 руб.
Полный день

Консультант-аналитик 1С
Рязань
зарплата до 80 000 руб.
Полный день

Программист 1С
Рязань
зарплата от 90 000 руб.
Полный день