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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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