Поиск SQL в кластерном индексе SQL Server медленный для определенных диапазонов

Question

На моей работе в настоящее время у нас есть таблица с 50 миллионами строк, которая имеет индекс по двум столбцам Varbinary(16), которые являются ip_start и ip_end.

PRIMARY KEY CLUSTERED 
(
    [ip_end] ASC,
    [ip_start] ASC
)

Первые несколько строк в таблице выглядят так:

ip_start   ip_end      id
0x00000000  0x00000000  0
0x00000001  0x000000FF  1
0x00000100  0x00FFFFFF  2
0x01000000  0x010000FF  3

Запрос, который мы используем для поиска совпадений:

SELECT TOP 1 id
FROM dbo.ip_ranges WITH (NOLOCK)
WHERE @lookup <= ip_end AND @lookup >= ip_start

Когда я смотрю IP как 0x00000002 он мгновенно возвращает id 1, но если я ищу диапазон, который находится между 0x000000000000001 для возврата NULL требуется несколько секунд. Разве SQL Server не должен понимать, что индекс varbinary упорядочен и поэтому быстро возвращается, если нет совпадений?

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

Answer 1

Разве SQL Server не должен понимать, что индекс varbinary упорядочен и поэтому быстро возвращается, если нет совпадений?

SQL Server понимает, что индекс упорядочен, но не понимает, что диапазоны не перекрываются. Это условие @lookup >= ip_start Это верно для нескольких диапазонов IP-адресов (в среднем около половины), и это производительность, которую вы видите для несоответствия. Индекс B-Tree не использует второй ключ для поиска индекса, когда первый ключ имеет неравенство.

К сожалению, стандартные индексы B-Tree не оптимальны для этого типа поиска (неравенства по двум измерениям). R-дерево (которое я изначально изучил как RD-дерево) лучше подходит. Они используются в основном для пространственных индексов.

Я думаю, что у меня был успех с запросом, подобным этому:

SELECT ir.*
FROM (SELECT TOP 1 ir.*
      FROM dbo.ip_ranges ir
      WHERE @lookup >= ip_start
      ORDER BY ip_start
     ) ir
WHERE @lookup <= ir.ip_end ; 

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

Answer 2

Создать некластеризованный индекс на ip_start с включенным идентификатором столбца

Или обновите кластерный индекс для одного столбца ip_start и создайте некластеризованный на ip_end с идентификатором включаемого столбца