Быстрое определение интервалов в запросе

Опубликовал ildarovich в раздел Программирование - Практика программирования

В статье описывается новый метод определения интервалов между данными различных записей в запросе. В отличие от общеизвестного метода, время работы предлагаемого метода зависит от объема данных ЛИНЕЙНО. Это обеспечивает ему значительный выигрыш по быстродействию на больших объемах данных.
В качестве иллюстрации возможностей метода приведен отчет, показывающий гистограмму распределения времени между продажами.

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

 Дата                      НачалоИнтервала  КонецИнтервала 
t1   t1 t2
t2   t2 t3
t3 ------> t3 t4
...   ... ...
tn   tn-1 tn


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

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

Общеизвестным методом решения этой задачи в запросе является запрос следующего вида:

ВЫБРАТЬ
    Слева.Дата КАК НачалоИнтервала,
    МИНИМУМ(Справа.Дата) КАК КонецИнтервала
ИЗ 
    Даты КАК Слева 
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ Даты КАК Справа
        ПО Слева.Дата < Справа.Дата
СГРУППИРОВАТЬ ПО 
    Слева.Дата

В большинстве случаев этого достаточно. Однако когда число элементов в исходной таблице становится достаточно большим, время выполнения запроса существенно возрастает. Это связано с квадратичным характером зависимости времени работы запроса от объема исходной таблицы: для каждой записи при расчете агрегатной функции МИНИМУМ просматривается в среднем половина других записей!

Идея, лежайшая в основе данного метода, ранее была использована при ускорении расчета нарастающего итога в запросе, описанном в статье Баттерфляй - метод быстрого расчета нарастающего итога в запросе . Однако в данном случае запрос получился более простым и универсальным.

В основе метода лежит поразрядная сортировка, а его схема имеет много общего с олимпийской системой соревнований (методом плей-офф). В каждом туре группируются записи, отличающиеся (при вычитании единицы) младшим разрядом номера: 1-2, 3-4, 5-6, 7-8 и так далее. В каждой паре определяется (и далее попадает в результирующую выборку) промежуток: интервал от верхней границы младшего элемента до нижней границы верхнего. А также определяется новая общая нижняя и верхняя граница. В следующем туре пара получает номер, полученный отбрасыванием младшего разряда номеров элементов пары. И так до финала. Промежуток определяется только тогда, когда в группировке есть оба элемента, иначе из пары в следующий тур выходит единственный элемент с теми же границами.

Вышесказанное иллюстрируется схемой одной группировки (матча):

СхемаГруппировки

и общей схемой группировок:

Общая схема группировок

Для тридцати двух туров и интервалов, измеряемых секундами, запрос имеет вид:

ВЫБРАТЬ
	РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1980, 1, 1), Дано.НачалоИнтервала, СЕКУНДА) + 1 КАК НомерПары,
	Дано.НачалоИнтервала КАК НижняяГраница,
	Дано.НачалоИнтервала КАК ВерхняяГраница
ПОМЕСТИТЬ Тур0
ИЗ
	&Интервалы КАК Дано
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	ВЫРАЗИТЬ(Тур0.НомерПары / 2 КАК ЧИСЛО(10, 0)) КАК НомерПары,
	МИНИМУМ(Тур0.НижняяГраница) КАК НижняяГраница,
	МАКСИМУМ(Тур0.ВерхняяГраница) КАК ВерхняяГраница,
	МИНИМУМ(Тур0.ВерхняяГраница) КАК НачалоИнтервала,
	МАКСИМУМ(Тур0.НижняяГраница) КАК КонецИнтервала
ПОМЕСТИТЬ Тур1
ИЗ
	Тур0 КАК Тур0

СГРУППИРОВАТЬ ПО
	ВЫРАЗИТЬ(Тур0.НомерПары / 2 КАК ЧИСЛО(10, 0))
;
...
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	ВЫРАЗИТЬ(Тур31.НомерПары / 2 КАК ЧИСЛО(10, 0)) КАК НомерПары,
	МИНИМУМ(Тур31.НижняяГраница) КАК НижняяГраница,
	МАКСИМУМ(Тур31.ВерхняяГраница) КАК ВерхняяГраница,
	МИНИМУМ(Тур31.ВерхняяГраница) КАК НачалоИнтервала,
	МАКСИМУМ(Тур31.НижняяГраница) КАК КонецИнтервала
ПОМЕСТИТЬ Финал
ИЗ
	Тур31 КАК Тур31

СГРУППИРОВАТЬ ПО
	ВЫРАЗИТЬ(Тур31.НомерПары / 2 КАК ЧИСЛО(10, 0))
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Тур1.НачалоИнтервала,
	Тур1.КонецИнтервала
ИЗ
	Тур1 КАК Тур1
ГДЕ
	Тур1.НачалоИнтервала < Тур1.КонецИнтервала

ОБЪЕДИНИТЬ
...
ВЫБРАТЬ
	Финал.НачалоИнтервала,
	Финал.КонецИнтервала
ИЗ
	Финал КАК Финал
ГДЕ
	Финал.НачалоИнтервала < Финал.КонецИнтервала

Тридцать два тура выбрано потому, что этого будет достаточно, чтобы охватить период с 1 января 1980-го до 2 февраля 2116 года (для интервалов, измеряемых секундами). Задание числа туров с большим запасом позволяет использовать всегда один и тот же текст запроса, а не формировать его динамически в зависимости от реально анализируемого промежутка времени. При этом избыточные запросы на быстродействии никак не сказываются, поскольку в лишних турах будет участвовать только один элемент.

Кажется удивительным, что такая громоздкая конструкция из тридцати трех запросов может побеждать по времени исходный запрос. Объяснением этому является тот факт, что в каждом следующем туре число участников сокращается вдвое (плюсы плей-офф). Следовательно, число матчей будет равно числу участников минус один! То есть число операций в данной схеме будет пропорциональным числу исходных записей, а не квадрату этого числа. Чем и объясняется быстродействие метода.

Сказанное подтверждается результатами испытаний, приведенными на Фиг.2 (для файлового варианта) и Фиг.3 (для MSSQL).

График быстродействия для файловой ИБ

График быстродействия для SQL

Из графиков следует, что предлагаемый метод превосходит традиционный, начиная примерно с 250 записей в файловом варианте и с 1500 записей в варианте SQL. Следовательно, например, средний курс валюты за год в файловом варианте уже будет выгоднее считать предлагаемым методом.

Но вообще-то это запрос не "на каждый день". Только для действительно больших объемов данных и случаев, когда результат требуется для дальнейшего использования в запросе. Иначе проще использовать внезапросную технику (например, СКД).   

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

Также следует сказать, что данное решение предназначено пока только для случаев тэта-соединений таблицы с самой собой. Внешне похожая на данную задача "множественных срезов последних" предлагаемым способом не решается, хотя также имеет определенные проблемы с быстродействием и перспективы его повышения данным методом на больших объемах данных. Для распространения описанного подхода на этот случай требуются определенные усложнения, о которых, возможно, будет рассказано позже. 

В качестве примера использования предлагаемого метода к статье прилагается отчет на основе СКД, который строит гистограмму интервалов между продажами в разрезе организаций со всеми возможными отборами. Отчет построен на обычных формах для конфигурации "Управление торговлей 10.3". Используется оборотный регистр "Продажи". Благодаря применяемому методу достигается высокая скорость построения отчета на любых объемах данных.

Файлы

Наименование Файл Версия Размер Кол. Скачив.
Отчет "Гистограмма интервалов между продажами" для УТ10.3
.erf 11,30Kb
30.09.15
20
.erf 8.2 11,30Kb 20 Скачать

См. также

Лучшие комментарии

3. Поручик 01.10.2015 14:08
Определить автора можно по заголовку, даже не заглядывая на страницу.
# Ответить
4. amiralnar 02.10.2015 08:46
Бесподобно!
+ 2 [ wowik; Makushimo; ]
# Ответить
13. kint 06.01.2016 13:33
В свое время пришлось разбираться с интервалами.
Стандартные задачи поиска свободных мест размещения, подбора интервалов оказания услуг, графики, расписания и т.п.
Оставлю здесь ссылку на свои заметки,- возможно, кому-то пригодится.
Самое вкусное (алгоритмы свертки и соединения), правда, там осталось за кадром (руки не дошли). Но основные понятия даны.

Дмитрий Малюгин
Ответили: (14)
+ 1 [ ildarovich; ]
# Ответить

Комментарии

1. spezc 01.10.2015 07:07
Спасибо за статью, интересно.
# Ответить
2. Evil Beaver 01.10.2015 12:40
Вот люблю я статьи маэстро! Они делают меня лучше
+ 1 [ dddxddd; ]
# Ответить
3. Поручик 01.10.2015 14:08
Определить автора можно по заголовку, даже не заглядывая на страницу.
# Ответить
4. amiralnar 02.10.2015 08:46
Бесподобно!
+ 2 [ wowik; Makushimo; ]
# Ответить
5. 1cmax 07.10.2015 08:47
Предполагаю, что у автора фундаментальное мат. образование, мало таких в мире 1с
Ответили: (6)
# Ответить
6. ildarovich 07.10.2015 10:30
(5) 1cmax, нет, образование у меня техническое
# Ответить
7. _also 20.10.2015 16:40
Ничего не понял, но, на всякий случай, плюсанул )))))
# Ответить
8. qwinter (файл скачал) 27.10.2015 14:48
А банальный обход этой таблицы в цикле решает эту задачу медленнее?
Ответили: (9)
# Ответить
9. ildarovich 27.10.2015 15:20
(8) qwinter, думаю, что
банальный обход этой таблицы в цикле
вне запроса решает эту задачу быстрее. Даже с учетом необходимости сортировки. СКД или оконные функции в других СУБД тоже могут помочь. Однако, если интервалы нужны в самом запросе для последующей обработки, то выгоднее использовать этот подход.
Ответили: (10)
# Ответить
10. qwinter (файл скачал) 27.10.2015 21:37
(9) ildarovich, запрос конечно веселый)) 900 строчек)))
# Ответить
11. Sevg 29.10.2015 10:54
Хороший новый способ взгляда на проблему.
# Ответить
12. ildarovich 01.12.2015 12:53
Кажется, нашел еще одно важное применение данного алгоритма. Это поиск пропущенных номеров! Задача актуальна, если судить по дискуссии в Интересная задачка для решения на SQL (Найти в диапазоне номеров пропуск).
Приведенный в статье алгоритм позволит найти все пропуски как интервалы между номерами, которые больше, чем 1. И сделает это быстро!
Это если стоит задача найти все пропуски. Если нужно найти только первый, то данный алгоритм будет не нужен. Подойдет запрос с условием
ГДЕ Номер + 1 НЕ В (ВЫБРАТЬ * ИЗ МножествоНомеров)
Но в нем тоже могут быть подводные камни, связанные с возможным использованием NESTED LOOP для этой проверки. Это можно обойти через прием с группировкой.
# Ответить
13. kint 06.01.2016 13:33
В свое время пришлось разбираться с интервалами.
Стандартные задачи поиска свободных мест размещения, подбора интервалов оказания услуг, графики, расписания и т.п.
Оставлю здесь ссылку на свои заметки,- возможно, кому-то пригодится.
Самое вкусное (алгоритмы свертки и соединения), правда, там осталось за кадром (руки не дошли). Но основные понятия даны.

Дмитрий Малюгин
Ответили: (14)
+ 1 [ ildarovich; ]
# Ответить
14. ildarovich 06.01.2016 16:11
(13) kint, большое спасибо, интересно
# Ответить
Внимание! За постинг в данном форуме $m не начисляются.
Внимание! Для написания сообщения необходимо авторизоваться
Текст сообщения*
Прикрепить файл