Оптимизация поиска по числовому диапазону (интервалу) в SQL Server

Этот вопрос похож на Оптимизацию поиска диапазона IP-адресов? но этот ограничен SQL Server 2000.

Предположим, у меня есть 10 миллионов диапазонов, предварительно сохраненных в таблице, структурированной и заполненной, как показано ниже.

CREATE TABLE MyTable
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX IX1 (RangeFrom,RangeTo),
INDEX IX2 (RangeTo,RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO MyTable
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(1)
FROM   RandomNumbers 

Мне нужно знать все диапазоны, содержащие значение 50,000,000. Я пытаюсь следующий запрос

SELECT *
FROM MyTable
WHERE 50000000 BETWEEN RangeFrom AND RangeTo

SQL Server показывает, что было выполнено 10 951 логическое чтение и было прочитано около 5 миллионов строк, чтобы вернуть 12 подходящих.

Могу ли я улучшить эту производительность? Любая реструктуризация таблицы или дополнительных индексов в порядке.

Columnstore очень полезен по сравнению с некластеризованным индексом, который сканирует половину таблицы. Некластеризованный индекс columnstore обеспечивает большую часть преимуществ, но вставка упорядоченных данных в кластеризованный индекс columnstore еще лучше.

DROP TABLE IF EXISTS dbo.MyTableCCI;

CREATE TABLE dbo.MyTableCCI
(
Id        INT PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX CCI CLUSTERED COLUMNSTORE
);

INSERT INTO dbo.MyTableCCI
SELECT TOP (987654321) *
FROM dbo.MyTable
ORDER BY RangeFrom ASC
OPTION (MAXDOP 1);

По своей структуре я могу получить исключение группы строк в RangeFromстолбце, что исключит половину моих групп строк. Но из-за характера данных я также получаю исключение группы строк в RangeToстолбце:

Table 'MyTableCCI'. Segment reads 1, segment skipped 9.

Для больших таблиц с более переменными данными существуют разные способы загрузки данных, чтобы гарантировать наилучшее исключение группы строк в обоих столбцах. В частности, для ваших данных запрос занимает 1 мс.

Пол Уайт указал на ответ на аналогичный вопрос, содержащий ссылку на интересную статью Ицик Бен Ган . Здесь описывается модель «Статического дерева реляционных интервалов», которая позволяет сделать это эффективно.

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

Исходя из этого, я реструктурировал таблицу, как показано ниже.

CREATE TABLE dbo.MyTable3
(
  Id        INT IDENTITY PRIMARY KEY,
  RangeFrom INT NOT NULL,
  RangeTo   INT NOT NULL,   
  node  AS RangeTo - RangeTo % POWER(2, FLOOR(LOG((RangeFrom - 1) ^ RangeTo, 2))) PERSISTED NOT NULL,
  CHECK (RangeTo > RangeFrom)
);

CREATE INDEX ix1 ON dbo.MyTable3 (node, RangeFrom) INCLUDE (RangeTo);
CREATE INDEX ix2 ON dbo.MyTable3 (node, RangeTo) INCLUDE (RangeFrom);

SET IDENTITY_INSERT MyTable3 ON

INSERT INTO MyTable3
            (Id,
             RangeFrom,
             RangeTo)
SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable

SET IDENTITY_INSERT MyTable3 OFF 

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

DECLARE @value INT = 50000000;

;WITH N AS
(
SELECT 30 AS Level, 
       CASE WHEN @value > POWER(2,30) THEN POWER(2,30) END AS selected_left_node, 
       CASE WHEN @value < POWER(2,30) THEN POWER(2,30) END AS selected_right_node, 
       (SIGN(@value - POWER(2,30)) * POWER(2,29)) + POWER(2,30)  AS node
UNION ALL
SELECT N.Level-1,   
       CASE WHEN @value > node THEN node END AS selected_left_node,  
       CASE WHEN @value < node THEN node END AS selected_right_node,
       (SIGN(@value - node) * POWER(2,N.Level-2)) + node  AS node
FROM N 
WHERE N.Level > 0
)
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS L
    ON I.node = L.selected_left_node
    AND I.RangeTo >= @value
    AND L.selected_left_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS R
    ON I.node = R.selected_right_node
    AND I.RangeFrom <= @value
    AND R.selected_right_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
WHERE node = @value;

Обычно это выполняется 1msна моем компьютере, когда все страницы находятся в кеше - со статистикой ввода-вывода.

Table 'MyTable3'. Scan count 24, logical reads 72, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 4, logical reads 374, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

и планировать

NB. Источник использует многоэтапные TVF, а не рекурсивный CTE, чтобы заставить узлы объединяться, но в интересах сделать мой ответ самодостаточным, я выбрал последнее. Для производственного использования я бы, вероятно, использовал TVF.

Мне удалось найти подход в режиме строк, который конкурирует с подходом N / CCI, но вам нужно кое-что знать о своих данных. Предположим , что у вас есть столбец , который содержал разницу RangeFromи RangeToи вы индексируется его вместе с RangeFrom:

ALTER TABLE dbo.MyTableWithDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableWithDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

Если бы вы знали все различные значения, DiffOfColumnsто вы могли бы выполнить поиск каждого значения DiffOfColumnsс включенным фильтром диапазона, RangeToчтобы получить все соответствующие данные. Например, если мы знаем, что DiffOfColumns= 2, то единственными допустимыми значениями для RangeFromявляются 49999998, 49999999 и 50000000. Рекурсию можно использовать для получения всех различных значений, DiffOfColumnsи она хорошо работает для вашего набора данных, поскольку их всего 256. Запрос ниже занимает около 6 мс на моей машине:

WITH RecursiveCTE
AS
(
    -- Anchor
    SELECT TOP (1)
        DiffOfColumns
    FROM dbo.MyTableWithDiff AS T
    ORDER BY
        T.DiffOfColumns

    UNION ALL

    -- Recursive
    SELECT R.DiffOfColumns
    FROM
    (
        -- Number the rows
        SELECT 
            T.DiffOfColumns,
            rn = ROW_NUMBER() OVER (
                ORDER BY T.DiffOfColumns)
        FROM dbo.MyTableWithDiff AS T
        JOIN RecursiveCTE AS R
            ON R.DiffOfColumns < T.DiffOfColumns
    ) AS R
    WHERE
        -- Only the row that sorts lowest
        R.rn = 1
)
SELECT ca.*
FROM RecursiveCTE rcte
CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableWithDiff mt
    WHERE mt.DiffOfColumns = rcte.DiffOfColumns
    AND mt.RangeFrom >= 50000000 - rcte.DiffOfColumns AND mt.RangeFrom <= 50000000
) ca
OPTION (MAXRECURSION 0);

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

Недостаток этого подхода в том, что он начинает работать медленно, когда слишком много различных значений для DiffOfColumns. Давайте сделаем тот же тест, но используем CRYPT_GEN_RANDOM(2)вместо CRYPT_GEN_RANDOM(1).

DROP TABLE IF EXISTS dbo.MyTableBigDiff;

CREATE TABLE dbo.MyTableBigDiff
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO dbo.MyTableBigDiff
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(2) -- note the 2
FROM   RandomNumbers;


ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableBigDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

Теперь тот же запрос находит 65536 строк из рекурсивной части и занимает 823 мс процессора на моем компьютере. PAGELATCH_SH ждет, и происходят другие неприятности. Я могу улучшить производительность, объединяя значения различий, чтобы держать под контролем число уникальных значений, и настраивая их на CROSS APPLY. Для этого набора данных я попробую 256 блоков:

ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns_bucket256 AS CAST(CEILING((RangeTo-RangeFrom) / 256.) AS INT);

CREATE INDEX [IXDIFF😎] ON dbo.MyTableBigDiff (DiffOfColumns_bucket256, RangeFrom) INCLUDE (RangeTo);

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

CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableBigDiff mt
    WHERE mt.DiffOfColumns_bucket256 = rcte.DiffOfColumns_bucket256
    AND mt.RangeFrom >= 50000000 - (256 * rcte.DiffOfColumns_bucket256)
    AND mt.RangeFrom <= 50000000
    AND mt.RangeTo >= 50000000
) ca

Полный запрос теперь занимает 6 мс на моей машине.

Один из альтернативных способов представления диапазона - это точки на линии.

Ниже приведен перенос всех данных в новую таблицу с диапазоном, представленным в виде geometryтипа данных.

CREATE TABLE MyTable2
(
Id INT IDENTITY PRIMARY KEY,
Range GEOMETRY NOT NULL,
RangeFrom AS Range.STPointN(1).STX,
RangeTo   AS Range.STPointN(2).STX,
CHECK (Range.STNumPoints() = 2 AND Range.STPointN(1).STY = 0 AND Range.STPointN(2).STY = 0)
);

SET IDENTITY_INSERT MyTable2 ON

INSERT INTO MyTable2
            (Id,
             Range)
SELECT ID,
       geometry::STLineFromText(CONCAT('LINESTRING(', RangeFrom, ' 0, ', RangeTo, ' 0)'), 0)
FROM   MyTable

SET IDENTITY_INSERT MyTable2 OFF 


CREATE SPATIAL INDEX index_name   
ON MyTable2 ( Range )  
USING GEOMETRY_GRID  
WITH (  
BOUNDING_BOX = ( xmin=0, ymin=0, xmax=110000000, ymax=1 ),  
GRIDS = (HIGH, HIGH, HIGH, HIGH),  
CELLS_PER_OBJECT = 16); 

Эквивалентный запрос для поиска диапазонов, содержащих значение, 50,000,000приведен ниже.

SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable2
WHERE  Range.STContains(geometry::STPointFromText ('POINT (50000000 0)', 0)) = 1 

Показания для этого показывают улучшение по сравнению 10,951с исходным запросом.

Table 'MyTable2'. Scan count 0, logical reads 505, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'extended_index_1797581442_384000'. Scan count 4, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Однако нет существенного улучшения по сравнению с оригиналом с точки зрения прошедшего времени . Типичные результаты выполнения составляют 250 мс против 252 мс.

План выполнения является более сложным, как показано ниже

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

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

Как дань уважения нашим новым повелителям роботов, я решил посмотреть, может ли какая-нибудь новая функциональность R и Python помочь нам здесь. Ответ - нет, по крайней мере, для сценариев, которые я мог заставить работать и возвращать правильные результаты. Если кто-то с лучшими знаниями придет, ну, не стесняйтесь шлепать меня. Мои ставки разумны.

Для этого я настроил виртуальную машину с 4 ядрами и 16 ГБ оперативной памяти, полагая, что этого будет достаточно для работы с набором данных ~ 200 МБ.

Давайте начнем с языка, которого нет в Бостоне!

р

EXEC sp_execute_external_script 
@language = N'R', 
@script = N'
tweener = 50000000
MO = data.frame(MartinIn)
MartinOut <- subset(MO, RangeFrom <= tweener & RangeTo >= tweener, select = c("Id","RangeFrom","RangeTo"))
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

Это было плохое время.

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3219 ms,  elapsed time = 5349 ms.

План выполнения довольно неинтересен, хотя я не знаю, почему средний оператор должен называть нас по именам.

Далее, кодирование с карандашами!

питон

EXEC sp_execute_external_script 
@language = N'Python', 
@script = N'
import pandas as pd
MO = pd.DataFrame(MartinIn)
tweener = 50000000
MartinOut = MO[(MO.RangeFrom <= tweener) & (MO.RangeTo >= tweener)]
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

Просто, когда вы думали, что это не может быть хуже, чем R:

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3797 ms,  elapsed time = 10146 ms.

Еще один нечестный план казни :

Хм и Хммер

Пока что я не впечатлен. Я не могу дождаться, чтобы удалить эту ВМ.

Я нашел довольно хорошее решение с использованием вычисляемого столбца, однако оно подходит только для одного значения. При этом, если у вас есть волшебная ценность, может быть, этого достаточно.

Начиная с заданного вами образца, затем модифицируя таблицу:

ALTER TABLE dbo.MyTable
    ADD curtis_jackson 
        AS CONVERT(BIT, CASE 
                            WHEN RangeTo >= 50000000
                            AND RangeFrom < 50000000
                            THEN 1 
                            ELSE 0 
                        END);

CREATE INDEX IX1_redo 
    ON dbo.MyTable (curtis_jackson) 
        INCLUDE (RangeFrom, RangeTo);

Запрос просто становится:

SELECT *
FROM MyTable
WHERE curtis_jackson = 1;

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

Table 'MyTable'. Scan count 1, logical reads 3...

SQL Server Execution Times:
  CPU time = 0 ms,  elapsed time = 0 ms.

И вот план запроса :

Мое решение основано на том наблюдении , что интервал имеет известную максимальную ширину W . Для данных примера это один байт или 256 целых чисел. Следовательно , для заданного значения параметра поиска P мы знаем наименьшее RangeFrom , что может быть в наборе результатов P - W . Добавление этого к предикату дает

declare @P int = 50000000;
declare @W int = 256;

select
    *
from MyTable
where @P between RangeFrom and RangeTo
and RangeFrom >= (@P - @W);

Исходя из первоначальной настройки и запроса моего компьютера (64-битная Windows 10, 4-ядерная гиперпоточная i7, 2,8 ГГц, 16 ГБ ОЗУ), возвращается 13 строк. Этот запрос использует параллельный поиск индекса по индексу (RangeFrom, RangeTo). Пересмотренный запрос также выполняет параллельный поиск по тому же индексу.

Измерения для исходного и пересмотренного запросов

                          Original  Revised
                          --------  -------
Stats IO Scan count              9        6
Stats IO logical reads       11547        6

Estimated number of rows   1643170  1216080
Number of rows read        5109666       29
QueryTimeStats CPU             344        2
QueryTimeStats Elapsed          53        0

Для исходного запроса количество прочитанных строк равно количеству строк, которые меньше или равны @P. Оптимизатор запросов (QO) не имеет альтернативы, но читает их все, поскольку не может заранее определить, будут ли эти строки удовлетворять предикату. Многостолбцовый индекс в (RangeFrom, RangeTo) бесполезен при удалении строк, которые не соответствуют RangeTo, поскольку нет никакой корреляции между первым ключом индекса и вторым, который может быть применен. Например, первая строка может иметь небольшой интервал и быть исключенной, тогда как вторая строка имеет большой интервал и возвращается, или наоборот.

В одной неудачной попытке я попытался обеспечить эту достоверность через ограничение проверки:

alter table MyTable with check
add constraint CK_MyTable_Interval
check
(
    RangeTo <= RangeFrom + 256
);

Это не имело никакого значения.

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

В зеркальном аргумента верхний предел RangeTo является P + W . Однако это бесполезно, потому что нет никакой корреляции между RangeFrom и RangeTo, которая позволила бы конечному столбцу многоколоночного индекса удалять строки. Следовательно, нет смысла добавлять этот пункт в запрос.

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

Я прошу прощения за любые ошибки, которые могут возникнуть в этом ответе.