Интервальные запросы в SQL Server

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

Начиная с SQL Server 2008, пространственные интервалы можно представить с помощью пространственных типов данных GEOMETRY и GEOGRAPHY, и оперировать этими типами данных посредством методов. К пространственным запросам можно также применять индексацию и оптимизацию.

Для интервалов других типов, в частности, очень распространенного временного типа, в SQL Server пока не предусмотрено специальной поддержки. Чаще всего такие интервалы представляют двумя атрибутами, содержащими нижнее и верхнее значения, и используют предикаты, задействующие эти атрибуты в запросах, связанных с интервалами. Для интервалов специальных средств индексации и оптимизации нет.

При подготовке запросов, связанных с интервалами, требуется определить типовые отношения между интервалами. Один из самых распространенных запросов — проверить наличие пересечения двух интервалов (например, найти два сеанса, которые были активными в течение определенного периода времени, представленного входами @l и @u). Проверка на пересечение — это комбинация одиннадцати из тринадцати отношений, определенных Джеймсом Алленом (www.ics.uci.edu/~alspaugh/cls/shr/allen.html). Эти одиннадцать отношений: meets, overlaps, finished-by, contains, starts, equals, started-by, during, finishes, overlapped-by и met-by. К сожалению, классическим методам, используемым для определения пересечения интервалов и некоторых других отношений, свойственны фундаментальные проблемы оптимизации. В результате производительность запросов, связанных с интервалами, обычно очень невысока.

Но положение не безнадежно — исследователи из Мюнхенского университета (Ганс-Питер Кригель, Марко Потке и Томас Зайдль) создали остроумную модель под названием Relational Interval Tree (RI-дерево). Благодаря усовершенствованиям Лорана Мартена (Франция) появилась возможность эффективно обрабатывать интервалы в SQL Server. Однако модель и дальнейшая оптимизация связаны с математическими вычислениями, которые могут показаться слишком сложными.

Существует возможность встроить модель в компонент базы данных SQL Server и сделать ее прозрачной для пользователя, которому достаточно применить простой синтаксис, чтобы сформировать новый вид индекса, оставив запросы неизменными. Остальное — дело SQL Server; ваши запросы будут просто выполняться быстрее. Пока в SQL Server нет подобных функций, но я надеюсь, что компания Microsoft положительно отнесется к идее и реализует такую функциональность в будущих версиях.

В данной статье сначала описывается традиционное представление интервалов в SQL Server, классические запросы к интервалам и основные проблемы оптимизации таких запросов. Затем будут описаны модель RI-дерева и дальнейшая оптимизация. В конце речь пойдет о потенциале интеграции модели RI-дерева в SQL Server.

Следующие ресурсы включают мой запрос относительно расширения функциональности к Microsoft, научную публикацию с описанием модели RI-дерева и статьи, описывающие дальнейшие этапы оптимизации:

• Microsoft Connect submission suggesting integration in SQL Server (connect.microsoft.com/SQLServer/feedback/details/780746);
• научная публикация с описанием модели RI-дерева (Kriegel, Potke и Seidl, Мюнхенский университет): «Managing Intervals Efficiently in Object-Relational Databases» (www.dbs.ifi.lmu.de/Publikationen/Papers/VLDB2000.pdf);
• статьи, описывающие оптимизацию модели RI-дерева (Laurent Martin): «A Static Relational Interval Tree» (www.solidq.com/sqj/Pages/2011-September-Issue/A-Static-Relational-Interval-Tree.aspx) и «Advanced interval queries with the Static Relational Interval Tree»(www.solidq.com/sqj/Pages/Relational/Advanced-interval-queries-with-the-Static-Relational-Interval-Tree.aspx).

Традиционные представления интервалов

Традиционно интервалы в SQL Server представляются двумя атрибутами, содержащими нижнее и верхнее значения каждого интервала, и атрибутом, содержащим ключ. Конечно, в таблице могут быть другие атрибуты для иных целей. В моих примерах используется таблица с именем Intervals и 10 000 000 строк, представляющих интервалы традиционным способом.

С помощью исходного текста в листинге 1 и листинге 2 создайте и заполните данными такую таблицу для своей среды. Листинг 1 строит базу данных с именем IntervalsDB, вспомогательную функцию с именем GetNums, которая формирует последовательность целых чисел в заданном диапазоне, и промежуточную таблицу с именем Stage с 10 000 000 строк.

Вы будете использовать один и тот же источник данных из промежуточной таблицы сначала для заполнения традиционного представления интервалов, а затем представления RI-дерева. Выполните программный код в листинге 2, чтобы создать таблицу Intervals с традиционным представлением интервалов и заполните ее образцовыми данными из промежуточной таблицы.

Для представления как нижних, так и верхних значений интервала используются целые числа, так как модель RI-дерева, которая рассматривается ниже, работает с целыми числами. Значения даты и времени нужно сопоставить целым числам, например, вычисляя разницу между некоторой точкой отсчета и целевым значением с учетом требуемой точности. Конечно, в традиционном представлении интервалов можно использовать любой тип, реализующий полный порядок.

Обратите внимание на два индекса, определенные в таблице Intervals. Один индекс создан по столбцу lower в качестве ключа и охватывает столбец upper, а другой создан по столбцу upper в качестве ключа и охватывает столбец lower.

В большинстве запросов, связанных с интервалами — например, запрос, определяющий пересечения интервалов, — участвуют два предиката диапазона. Например, если входной интервал определен переменной @l (для lower) и @u (для upper), то интервалами, пересекающимися с входным интервалом, являются те, которые удовлетворяют следующему предикату: lower <= @u AND upper >= @l. В этом состоит фундаментальная проблема оптимизации — поиск в индексе может основываться только на одном предикате диапазона. Другие предикаты диапазона необходимо обработать как остаточные. Поэтому оптимизатору необходимо выбрать для работы один из двух индексов и выполнить поиск на основе одного из предикатов по ключу основного индекса, чтобы отобрать подходящие строки. При просмотре оставшихся строк в листах индекса проверьте другой предикат, чтобы определить, какие строки следует возвратить.

Понять это очень важно, поэтому полезно остановиться на данном вопросе подробнее. Рассмотрим следующий список, отсортированный по X, Y:

X, Y

1, 10

1, 20

1, 40

1, 50

2, 20

2, 30

2, 50

3, 20

3, 40

3, 50

3, 50

3, 60

4, 10

4, 10

4, 50

4, 60

Предположим, отсортированный список представляет данные на конечный уровень двоичного индекса. Рассмотрим запрос со следующим фильтром: X >= 3 и Y <= 40. На основе предиката X >= 3 можно с помощью поиска в индексе перейти прямо к конечной строке (3, 20) и просмотреть только строки, удовлетворяющие предикату. Однако нельзя избежать просмотра всех оставшихся строк в элементах индекса и проверки оставшегося предиката Y <= 40 в качестве остаточного предиката.

Мы можем наблюдать проблему оптимизации на примере запроса, выполняющего поиск пересечения в таблице Intervals. Прежде всего, используйте следующий программный код, чтобы включить STATISTICS IO и STATISTICS TIME:

SET STATISTICS IO ON;
SET STATISTICS TIME ON;

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

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT id
FROM dbo.Intervals
WHERE lower <= @u AND upper >= @l
OPTION (RECOMPILE);

Я использую параметр запроса RECOMPILE, так как в противном случае значения переменной не будут проанализированы. План этого запроса показан на рисунке 1.

Рисунок 1. План исполнения традиционного запроса на?пересечение

Входные данные в этом запросе представляют интервал, находящийся приблизительно в середине всего диапазона, поэтому в действительности неважно, какой из двух индексов используется оптимизатором. В данном случае оптимизатор выбрал индекс idx_upper. Что касается проблемы оптимизации, обратите внимание, что в разделе Seek Predicates содержится только предикат для столбца upper; предикат для столбца lower находится в разделе Predicate — это остаточный предикат. В результате приходится просматривать около половины конечного уровня индекса. На моем компьютере статистика для этого запроса была следующая — операции логического считывания: 11256; время процессора: 482 мс. Надо признать, не очень высокая эффективность.

Как отмечалось выше, при поиске интервала в середине всего диапазона не имеет значения, какой индекс используется оптимизатором. Однако при поиске интервала, находящегося поблизости от начала диапазона, естественно, эффективнее использовать idx_lower, что связано с просмотром меньшей области в начале элементов индекса. Проведите эксперимент с входными данными @l = 80 и @u = 100; используйте параметр RECOMPILE так, чтобы оптимизатор мог анализировать значения переменных. Статистика для данного запроса — операции логического считывания: 3; время процессора: 0 мс.

Аналогично при запросе, обращенном к концу диапазона данных, оптимизатор выбирает idx_upper, просматривая малую область в конце листа индекса. Например, попробуйте выполнить запрос с входными данными @l = 9999900 и @u = 9999920. Статистика для данного запроса — операции логического считывания: 3; время процессора: 0 мс.

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

RI-дерево

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

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

Рисунок 2. Виртуальное базовое дерево и узел ветвления

Можно воспользоваться функцией LOG, чтобы вычислить высоту дерева. Чтобы охватить диапазон от 1 до значения @max, высота двоичного дерева — @h = CEILING(LOG(@max + 1, 2)). Корень дерева — POWER(2, @h-1). Причина, по которой дерево — виртуальное, заключается в том, что полное дерево нигде не запоминается; его узлы используются только при необходимости, как будет показано ниже.

Узел ветвления. Фундаментальный компонент модели RI-дерева — объект, именуемый «узлом ветвления» (fork node). Он рассчитывается для каждого интервала, который необходимо представить в базе данных, и хранится вместе с ним. На рисунке 2 показано, как вычисляется узел ветвления для некоторого тестового интервала. Вы проходите по виртуальному дереву начиная с корня с разветвлением на два; первый узел, обнаруженный внутри интервала, — узел ветвления.

В листинге 3 реализован алгоритм, основанный на модели RI-дерева в определяемой пользователем функции T-SQL с именем forkNode для дерева с высотой 31 (охватывает диапазон от 1 до 2147483647).

Например, вызовите функцию с входными данными 11 и 13, и получите 12 в качестве узла ветвления на выходе:

SELECT dbo.forkNode(11, 13);

Недостаток расчета узла ветвления, представленного в листинге 3, в том, что используется определяемая пользователем функция T-SQL и итеративная логика. Такая комбинация очень неэффективна, особенно если требуется рассчитывать узел ветвления для каждого интервала, сохраняемого в базе данных. Чтобы дать представление о степени неэффективности, отмечу, что на моем компьютере для заполнения таблицы с 10 000 000 строк потребовалось 304 секунды, из которых 297 секунд было потрачено на расчет узла ветвления.

Нагрузка на процессор в алгоритме итераций для расчета узла ветвления пропорциональна высоте дерева. В модели RI-дерева Кригеля, Потке и Зайдля используется вариант, при котором высота и диапазон дерева динамически расширяются в зависимости от добавляемых интервалов. Но при этом необходимо ввести дополнительные параметры для дерева и изменять некоторые из них при каждом добавлении интервала. В результате поддерживаются только однострочные вставки; кроме того, вставки выполняются медленно и часто приводят к возникновению узкого места.

Лоран Мартен предложил способ расчета узла ветвления с использованием скалярного выражения. В результате появилась возможность обрабатывать большое RI-дерево и задействовать очень эффективные многострочные вставки. Как показано на рисунке 3, узел ветвления для данного интервала — наименьший общий предок границ интервала, представленных значениями в столбцах lower (11) и upper (13).

Рисунок 3. Оптимизированный узел ветвления

Рассмотрите двоичное представление узлов на рисунке 3.

Для каждого данного узла примем L = ведущие разряды перед завершающими нулями; например, для узла 12 (01100), L = 011.

При данном узле X, ведущие разряды которого — L, все узлы в левом поддереве X имеют значение ведущих разрядов L-1 (например, для L = 011, L-1 = 010), а все узлы в правом поддереве X имеют значение ведущих разрядов L.

Для некоторого неконечного узла X и X-1 предок один и тот же, поэтому для расчета предка X значение X можно заменить на X-1.

Если Z — конечный узел, Z и Z-1 отличаются только последним разрядом; для Z это 1, а для Z-1 — 0.

Учитывая эти обстоятельства, узел ветвления можно рассчитать следующим образом: сопоставление префикса (lower — 1) и upper, соединенное с 1 и дополненное завершающими нулями.

Выполнить эти вычисления в SQL Server можно с помощью следующих действий (взяв в качестве примера интервал [11, 13] на рисунке 3):

Let A = (lower — 1) ^ upper
Let B = POWER(2, FLOOR(LOG(A, 2)))
Let C = upper % B
Let D = upper — C

На шаге 1 вычисляется значение (назовем его A), отмечающее разряды, различающиеся в (lower — 1) и upper, как «единицы». Чтобы добиться этого, выполняется побитовая операция XOR между (lower — 1) и upper. В нашем примере 11 ^ 13 в двоичном представлении — 01010 ^ 01101 = 00111.

На шаге 2 вычисляется значение (назовем его B), в котором крайний левый разряд, различающийся в (lower — 1) и upper, устанавливается в «единицу», а все остальные разряды устанавливаются в 0. Другими словами, этот шаг определяет крайний левый разряд в A, который установлен. Обратите внимание, что на основе приведенных выше соображений крайний левый разряд, различающийся в (lower — 1) и upper, будет равен 0 в (lower — 1) и 1 в upper. В нашем примере результат шага в двоичной форме — 00100.

На шаге 3 сохраняются завершающие разряды из upper, следующие после разряда, установленного в 1 в B. В нашем примере это 01101 % 00100 = 01.

На шаге 4 завершающим разрядам в upper после установленного разряда в B присваивается значение 0. В нашем примере: 01101 — 00001 = 01100. Готово — мы получили узел ветвления!

Все эти операции можно объединить в следующей формуле (представленной как выражение T-SQL в SQL Server 2012) для вычисления узла ветвления:

upper — upper % POWER(2, FLOOR(LOG((lower — 1) ^ upper, 2)))

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

Получив скалярное выражение для расчета узла ветвления на основе столбцов lower и upper, можно реализовать его как вычисляемый столбец (назовем его «узел») в таблице, содержащей интервалы. На основе модели RI-дерева потребуются два индекса: один для списка ключей (node, lower) и другой для списка ключей (node, upper). Обратите внимание, что в зависимости от ваших потребностей можно добавить ведущие столбцы в список ключей для фильтров на основе равенства в запросах, а также столбцы в список index include для полноты охвата.

Исходный текст в листинге 4 создает таблицу IntervalsRIT, заполняет ее тестовыми данными из промежуточной таблицы и создает ограничение первичного ключа и индексацию на основе модели RI-дерева.

Заполненная таблица IntervalsRIT и ее индексы — это представление интервалов на основе RI-дерева, которое заменяет прежнюю таблицу Intervals и ее индексы. Вспомните, что при использовании функции forkNode на моем компьютере потребовалось 297 секунд просто для того, чтобы рассчитать узлы ветвления для 10 000 000 интервалов. Благодаря оптимизированной формуле Мартена это заняло лишь 6 секунд.

Запросы к модели RI-дерева. В таблице IntervalsRIT интервалы хранятся, наряду с узлом ветвления, в столбце с именем node. Рассмотрим, как направить запрос к таблице, чтобы определить интервалы, пересекающиеся с некоторым входным интервалом [@l, @u]. В примерах в этой статье используется входной интервал [@l = 11, @u = 13].

В модели RI-дерева имеется три несвязанных группы интервалов, которые могут пересекаться с входным интервалом. Я называю их левой (left), средней (middle) и правой (right) группами.

Левая группа. Рассмотрим путь виртуального дерева, спускающегося из корня к @l, как показано на рисунке 4. Пусть leftNodes — набор всех узлов w, которые встречаются на пути и находятся слева от входного интервала.

Рисунок 4. Левые узлы

Для всех узлов w в leftNodes истинны следующие утверждения (см. рисунок 4).

• Интервал, зарегистрированный в узле d в левом поддереве w, не может пересекаться с входным интервалом. Если бы это произошло, он был бы зарегистрирован в предке d.
• Интервал, зарегистрированный в w, может принадлежать к одной из двух разновидностей: (1) если upper < @l, то очевидно интервал не пересекается с входным интервалом; (2) если upper >= @l, то интервал должен пересекаться с входным интервалом, поскольку уже известно, что lower <= @u (интервал, зарегистрированный в узле, который находится слева от входного интервала, очевидно начинается раньше, чем заканчивается входной интервал).

Поэтому интервалы, принадлежащие к левой группе, зарегистрированы в узле в leftNodes и имеют haveupper >= @l.

В листинге 5 содержится определение табличной функции с именем leftNodes, которая возвращает узлы в указанном выше наборе leftNodes.

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

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.leftNodes(@l, @u) AS L
ON I.node = L.node
AND I.upper >= @l;

Изучите план запроса на рисунке 5.

Рисунок 5. План запроса с левыми узлами

План выполняет поиск в индекс idx_upper для каждого узла в leftNodes. Важно, что теперь существует один предикат равенства и один предикат диапазона; и тот и другой можно применять как предикаты поиска.

Правая группа. Правая группа симметрична левой. Рассмотрите путь виртуального дерева, спускающегося от корня к @u, как показано на рисунке 6. Пусть rightNodes — набор всех узлов w, которые встречаются на пути и находятся справа от входного интервала.

Рисунок 6. Правые узлы

Для всех узлов w в rightNodes истинны следующие утверждения (см. рисунок 6).

• Интервал, зарегистрированный в узле d в правом поддереве w, не может пересекаться с входным интервалом. Если бы это произошло, он был бы зарегистрирован в предке d.
• Интервал, зарегистрированный в w, может принадлежать к одной из двух разновидностей: (1) если lower > @u, то очевидно интервал не пересекается с входным интервалом; (2) если lower <= @u, то интервал должен пересекаться с входным интервалом, поскольку уже известно, что upper >= @l (интервал, зарегистрированный в узле, который находится справа от входного интервала, очевидно заканчивается после того, как начинается входной интервал).

Поэтому интервалы, принадлежащие к правой группе, зарегистрированы в узле в rightNodes и имеют lower <= @u.

В листинге 5 содержится определение табличной функции, именуемой rightNodes, которая возвращает узлы в указанном выше наборе rightNodes.

Следующий запрос возвращает все интервалы в правой группе (зарегистрированные в узлах в rightNodes, которые пересекаются с входным интервалом):

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.rightNodes(@l, @u) AS R
ON I.node = R.node
AND I.lower <= @u;

На рисунке 7 показан план для этого запроса. Он симметричен плану на рисунке 5, но на этот раз используется индекс idx_lower.

Рисунок 7. План запроса с правыми узлами

Средняя группа. Пусть middleNodes — набор узлов w, находящихся во входном интервале, как показано на рисунке 8.

Рисунок 8. Средние узлы

Любой интервал, зарегистрированный в w, имеет lower <= @u и upper >= @l; поэтому он пересекается с входным интервалом. Используйте следующий запрос, чтобы вернуть все интервалы в средней группе:

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT id
FROM dbo.IntervalsRIT
WHERE node BETWEEN @l AND @u;

Оптимизатор может использовать как idx_upper, так и idx_lower для эффективной обработки запроса. На рисунке 9 мы видим, что в данном случае оптимизатор, похоже, предпочел использовать idx_upper.

Рисунок 9. План запроса для средних узлов

Листинг 6 содержит исходный текст на основе модели RI-дерева, объединяющий результаты запросов, возвращающих пересечения во всех трех группах (левой, средней и правой).

Для объединенного запроса была получена следующая статистика: 81 для IntervalsRIT + 2 для табличной переменной, возвращенной leftNodes + 2 для табличной переменной, возвращенной rightNodes; время процессора: 16 мс. Это намного лучше, чем у традиционного запроса, показанного в начале статьи; напомню статистику для традиционного запроса: операции логического считывания: 11256; время процессора: 482 мс.

Оптимизированный расчет предков. Недостаток реализации функций leftNodes и rightNodes в предшествующем разделе заключается в использовании итеративной логики, не отличающейся эффективностью в T-SQL. Представьте избыточные затраты для поиска пересечений не с единственным входным интервалом, а с целым набором входных интервалов.

Лоран Мартен предложил элегантное решение, в котором используется логика, основанная на наборах. В данной статье описана разновидность решения, на мой взгляд, более доступная для понимания. Основная логика примерно такая же, как в решении Мартена.

Если имеется входной интервал [@l, @u], то leftNodes — набор предков @l, которые находятся слева от входного интервала. Аналогично, rightNodes — набор предков @r, находящихся справа от входного интервала. Мартен сделал следующее наблюдение относительно предков любого данного узла @node. Предположим, @node = 13 (в двоичном формате 01101). Можно определить родителя узла, присвоив значение 0 самому правому разряду узла, а разряду слева от него — значение 1. Этот процесс можно повторять до тех пор, пока не будет достигнут корень, чтобы определить всех предков. Например, предки 13 — 14, 12, 8 и 16:

01101 (13)

01110 (14)

01100 (12)

01000 (8)

10000 (16)

Чтобы вычислить предков данного узла, используется вспомогательная таблица с именем BitMasks, похожая на таблицу 1 (значения в столбцах b1 и b3 представлены в двоичном формате).

Для виртуального дерева с высотой h таблицу следует заполнить строками, в которых n имеет значения между 1 и h-1. Например, программный код в Листинге 7 создает таблицу BitMasks и заполняет ее значениями для дерева с высотой h = 31 (n от 1 до 30).

Может возникнуть вопрос, почему в таблице BitMasks нет столбца b2. В данной разновидности решения используются только b1 и b3, но в первоначальном решении Мартена есть также столбец b2.

Обратите внимание на следующие особенности таблицы 1. Чтобы вычислить предков входного узла @node, направляют запрос к таблице BitMasks, применяя выражение @node & b1 | b3 на каждом уровне, что в сущности реализует описанную выше логику: на каждом уровне назначьте значение 0 разряду этого уровня и присвойте разряду слева от него значение 1. Однако необходимо отфильтровать только уровни, на которых существуют предки, а именно те, у которых самый правый разряд, установленный в 1 (просто b3), находится слева от самого правого установленного в 1 разряда в @node.

В SQL Server для представления целых чисел используется дополнительный код. Как отмечается в соответствующей статье Википедии, «простой способ ручного преобразования двоичного числа в дополнительный код — начать с наименьшего значащего разряда и скопировать все нули (двигаясь в направлении к наибольшему значащему разряду) до тех пор, пока не встретится первая 1, и инвертировать все оставшиеся разряды».

Это значит, что для данного значения @node самый правый установленный в 1 разряд можно вычислить с помощью выражения @node & -@node. Для фильтрации только уровней, представляющих предков положительного входного узла, следует использовать следующий предикат: b3 > @node & -@node.

В Листинге 8 содержится определение возвращающей табличное значение встроенной функции Ancestors, которая возвращает всех предков входного узла. Чтобы возвратить только левых предков данного узла, направляется запрос к функции и фильтруются только строки, в которых возвращенный узел меньше входного узла. Чтобы возвратить только правых предков, направляется запрос к функции и фильтруются только строки, в которых возвращенный узел больше входного узла.

Запрос в Листинге 9 используется вместо представленного в Листинге 6, чтобы возвратить интервалы, пересекающиеся с входным интервалом [@l, @u].

Обратите внимание на добавление фильтров, исключающих узлы из левого пути, которые меньше минимального узла в таблице, и узлы из правого пути, которые больше максимального узла в таблице. На рисунке 10 показан план запроса в Листинге 9.

Рисунок 10. План запроса с таблицей BitMasks и функцией Ancestors

Поскольку функция Ancestors встроенная, план просматривает таблицу BitMasks напрямую, без накладных расходов, связанных с самой функцией, как в предыдущем случае. Статистика этого запроса — операции логического считывания: 66 для IntervalsRIT + 2 для BitMasks; время процессора: 0 мс.

Возможности интеграции в SQL Server

Благодаря модели RI-дерева и оптимизации удается весьма эффективно обрабатывать интервалы в SQL Server. Но математические выкладки, необходимые для этого решения, могут оказаться слишком сложными для пользователей. Есть возможность встроить модель в ядро SQL Server, сделав ее прозрачной для пользователя. Достичь этого можно несколькими способами.

Один вариант — ввести новый тип индекса (назовем его индексом интервала), который пользователю необходимо создать с помощью довольно простого синтаксиса. SQL Server может рассчитать узел ветвления для каждого интервала и построить два двоичных индекса, таких как описанные выше idx_lower и idx_upper. Необходим также оптимизатор, чтобы обнаружить запросы интервалов на основе предикатов в фильтре запроса, а после обнаружения следует выполнить внутреннюю обработку запроса по методу, представленному в листинге 9 (или листинге на основе исходной модели). При таком подходе пользователю остается лишь создать индекс интервала, а ядро SQL Server сделает остальное. Исходные запросы остаются неизменными, и лишь выполняются быстрее.

Описанные ранее индексы idx_lower и idx_upper представляют самую простую форму необходимых индексов. Как описано в работе «Advanced interval queries with the Static Relational Interval Tree», все отношения Аллена для интервалов можно обработать на основе модели RI-дерева. Для некоторых требуется один индекс для списка ключей (node, lower, upper) и другой для (node, upper, lower). Для запросов, относящихся только к пересечениям, достаточно определить индексы для (node, lower) и (node, upper) соответственно (поэтому параметр INTERSECTS_ONLY в предложенном синтаксисе индекса). Кроме того, если запрос имеет дополнительные фильтры на основе равенства для других столбцов, необходимо добавить их к обоим индексам как начальные ключи. Наконец, если нужно возвратить дополнительные столбцы помимо указанных в списке ключей, и требуется, чтобы индексы покрывали запрос, необходимо добавить эти столбцы как включенные. Поэтому предложенный индекс интервала со всеми необязательными элементами будет выглядеть следующим образом:

CREATE INDEX myindex
ON dbo.Intervals[(fcol1, fcol2,. ..)] — начальные
equality-based filters
INTERVAL(lower, upper) — столбцы интервала
[INCLUDE(icol1, icol2,. ..)] — включенные столбцы
[WITH (INTERSECTS_ONLY = ON)]; — определяет список ключей

Во внутреннем механизме SQL Server будут созданы следующие два обычных B*tree-индекса:

CREATE INDEX myidx1 ON dbo.Intervals([fcol1, fcol2,. ..,]
node, lower[, upper]) [INCLUDE(icol1, icol2,. ..)];
CREATE INDEX myidx2 ON dbo.Intervals([fcol1, fcol2,. ..,]
node, upper[, lower]) [INCLUDE(icol1, icol2,. ..)];

Как отмечалось выше, оптимизатор обнаружит запросы интервалов на основе предикатов в фильтре запроса и воспользуется этими индексами.

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

Среди других потенциальных дополнений к SQL Server на основе этой модели — встроенные функции для расчета узла ветвления и предков, поддержки типов даты и времени, и опять же, их более эффективной реализации по сравнению с пользовательскими вычислениями. Кроме того, эти функции обеспечат индивидуальный подход для опытных пользователей. Как отмечалось выше, я подал соответствующее предложение о расширении функциональности в компанию Microsoft.

Ускоряем обработку запросов, работающих с интервалами

Традиционным методам, часто используемым для обработки запросов, работающих с интервалами, особенно типовых запросов пересечений, свойственны фундаментальные проблемы, снижающие производительность. Если в фильтре запроса имеется два предиката диапазона, только один можно использовать в качестве предиката поиска в индексе на основе двоичного дерева. Благодаря модели RI-дерева и дополнительной оптимизации удается получить индексный поиск на основе единственного предиката диапазона, что существенно ускоряет обработку запросов. Однако модель и ее оптимизация может оказаться излишне сложной для пользователей. Поскольку проблема — чисто техническая, и решение уже существует, его можно полностью интегрировать в ядро базы данных, сделав прозрачным для пользователей. В заключение я бы хотел поблагодарить Ганса-Питера Кригеля, Марко Потке и Томаса Зайдля за предложенную ими модель RI-дерева, а также Лорана Мартена за внесенные в нее дополнения.

SET NOCOUNT ON;
USE master;
IF DB_ID('IntervalsDB') IS NOT NULL DROP DATABASE IntervalsDB;
CREATE DATABASE IntervalsDB;
GO
USE IntervalsDB;
GO

@low and @high
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high — @low + 1) @low + rownum — 1 AS n
FROM Nums
ORDER BY rownum;
GO

CREATE TABLE dbo.Stage
(
id INT NOT NULL,
lower INT NOT NULL,
upper INT NOT NULL,
CONSTRAINT PK_Stage PRIMARY KEY(id),
CONSTRAINT CHK_Stage_upper_gteq_lower CHECK(upper >= lower)
);
DECLARE
@numintervals AS INT = 10000000,
@minlower AS INT = 1,
@maxupper AS INT = 10000000,
@maxdiff AS INT = 20;
WITH C AS
(
SELECT
n AS id,
@minlower + (ABS(CHECKSUM(NEWID())) %
(@maxupper — @minlower — @maxdiff + 1)) AS lower,
ABS(CHECKSUM(NEWID())) % (@maxdiff + 1) AS diff
FROM dbo.GetNums(1, @numintervals) AS Nums
)
INSERT INTO dbo.Stage WITH(TABLOCK) (id, lower, upper)
SELECT id, lower, lower + diff AS upper
FROM C;

CREATE TABLE dbo.Intervals
(
id INT NOT NULL,
lower INT NOT NULL,
upper INT NOT NULL,
CONSTRAINT PK_Intervals PRIMARY KEY(id),
CONSTRAINT CHK_Intervals_upper_gteq_lower CHECK(upper >= lower)
);
CREATE INDEX idx_lower ON dbo.Intervals(lower) INCLUDE(upper);
CREATE INDEX idx_upper ON dbo.Intervals(upper) INCLUDE(lower);
INSERT INTO dbo.Intervals WITH(TABLOCK) (id, lower, upper)
SELECT id, lower, upper
FROM dbo.Stage;

CREATE FUNCTION dbo.forkNode(@lower AS INT, @upper AS INT) RETURNS INT
WITH SCHEMABINDING
AS
BEGIN
DECLARE @node AS INT = 1073741824; — @node = 2^(h-1),
h = height of tree, #values: 2^h — 1
DECLARE @step AS INT = @node / 2;
WHILE @step >= 1
BEGIN
IF @upper < @node
SET @node -= @step;
ELSE IF @lower > @node
SET @node += @step;
ELSE
BREAK;
SET @step /= 2;
END;
RETURN @node;
END;
GO

CREATE TABLE dbo.IntervalsRIT
(
id INT NOT NULL,
node AS upper — upper % POWER(2, FLOOR(LOG((lower — 1) ^ upper, 2)))
PERSISTED NOT NULL,
lower INT NOT NULL,
upper INT NOT NULL,
CONSTRAINT PK_IntervalsRIT PRIMARY KEY(id),
CONSTRAINT CHK_IntervalsRIT_upper_gteq_lower CHECK(upper >= lower)
);
CREATE INDEX idx_lower ON dbo.IntervalsRIT(node, lower);
CREATE INDEX idx_upper ON dbo.IntervalsRIT(node, upper);
INSERT INTO dbo.IntervalsRIT WITH(TABLOCK) (id, lower, upper)
SELECT id, lower, upper
FROM dbo.Stage;

CREATE FUNCTION dbo.leftNodes(@lower AS INT, @upper AS INT)
RETURNS @T TABLE
(
node INT NOT NULL PRIMARY KEY
)
AS
BEGIN
DECLARE @node AS INT = 1073741824;
DECLARE @step AS INT = @node / 2;

WHILE @step >= 1
BEGIN

IF @lower < @node
SET @node -= @step;

ELSE IF @lower > @node
BEGIN
INSERT INTO @T(node) VALUES(@node);
SET @node += @step;
END

ELSE
BREAK;
SET @step /= 2;
END;
RETURN;
END;
GO

CREATE FUNCTION dbo.rightNodes(@lower AS INT, @upper AS INT)
RETURNS @T TABLE
(
node INT NOT NULL PRIMARY KEY
)
AS
BEGIN
DECLARE @node AS INT = 1073741824;
DECLARE @step AS INT = @node / 2;

WHILE @step >= 1
BEGIN

IF @upper > @node
SET @node += @step

ELSE IF @upper < @node
BEGIN
INSERT INTO @T(node) VALUES(@node);
SET @node -= @step
END

ELSE
BREAK;
SET @step /= 2;
END;
RETURN;
END;
GO

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.leftNodes(@l, @u) AS L
ON I.node = L.node
AND I.upper >= @l
UNION ALL
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.rightNodes(@l, @u) AS R
ON I.node = R.node
AND I.lower <= @u
UNION ALL
SELECT id
FROM dbo.IntervalsRIT
WHERE node BETWEEN @l AND @u
OPTION (RECOMPILE);

CREATE TABLE dbo.BitMasks
(
b1 INT NOT NULL,
b3 INT NOT NULL
);
INSERT INTO dbo.BitMasks(b1, b3)
SELECT -POWER(2, n), POWER(2, n)
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),
(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),
(21),(22),(23),(24),(25),(26),(27),(28),(29),(30)) AS Nums(n);

CREATE FUNCTION dbo.Ancestors(@node AS INT) RETURNS TABLE
AS
RETURN
SELECT @node & b1 | b3 as node
FROM dbo.BitMasks
WHERE b3 > @node & -@node;
GO

DECLARE @l AS INT = 5000000, @u AS INT = 5000020;
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.Ancestors(@l) AS L
ON L.node < @l
AND L.node >= (SELECT MIN(node) FROM dbo.IntervalsRIT)
AND I.node = L.node
AND I.upper >= @l
UNION ALL
SELECT I.id
FROM dbo.IntervalsRIT AS I
JOIN dbo.Ancestors(@u) AS R
ON R.node > @u
AND R.node <= (SELECT MAX(node) FROM dbo.IntervalsRIT)
AND I.node = R.node
AND I.lower <= @u
UNION ALL
SELECT id
FROM dbo.IntervalsRIT
WHERE node BETWEEN @l AND @u
OPTION (RECOMPILE);