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

01.10.2015

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

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

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

Дата		НачалоИнтервала	КонецИнтервала
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).

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

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

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

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

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

Текст публикации

Все новости