Comments 10
Есть официальная дока (более подробного материала навряд ли кто-то даст):
1) MS SQL
2) PostgreSQL
3) MySQL
https://use-the-index-luke.com/ детально описаны b-tree индексы с примерами для разных баз.
Что если вместо поля sha256 создать 2 поля: sha256_part_1 и sha256_part_2?
В поле sha256_part1 хранить первые 10 символов(например) и построить некластеризованный индекс по первой части включая вторую?
CREATE NONCLUSTERED INDEX IX_sha256_part_1_include_sha256_part_2 ON dbo.metadata (sha256_part_1) INCLUDE(sha256_part_2)
Он и место дополнительное не займёт и в случае коллизии перебирать не много. Нужно вычислить оптимальную длину первой части - чтобы и дерево индекса не раздувать и максимально избежать коллизий.
Длину подбирали опытным путём и получили, что именно bigint - самый оптимальный вариант (как описано в конце публикации), т е меньше и больше если брать массив байт, то будет медленнее искать.
Да, но вы завели дополнительное 8ми байтовое поле на строку, а это увеличение кол-во страниц, чтений и возможно увеличение промежуточных уровней дерева.
Я имею в виду создать таблицу:
CREATE TABLE dbo.metadata
(
id bigint NOT NULL,
sha256_part1 binary(8) NOT NULL,
sha256_part2 binary(24) NOT NULL,
CONSTRAINT pk_metadata PRIMARY KEY CLUSTERED (id)
)
CREATE NONCLUSTERED INDEX IX_sha256_part1_include_sha256_part2 ON dbo.metadata (sha256_part1) INCLUDE(sha256_part2)
Так дешевле хранить и дешевле искать - экономится 8 байт на строку. Так же поле фиксированной длины экономить по 2 байта на строку, поэтому рекомендую binary вместо varbinary
Varbinary как и целиком sha256 устоялись исторически. Однако, Ваше предложение выглядит как минимум теоретически более оптимальным. На тестовом стенде перепроверю и отпишусь. Правда там 1-2 млрд строк, но думаю для сравнения хватит. Спасибо!
Использовал как Вы описали выше, и на практике получилось лучше (правда здесь без нагрузки вставок) на миллиардной таблице (результат с 3-го раза после очистки кэша планов):
SQL Server parse and compile time:
CPU time = 672 ms, elapsed time = 745 ms.
При этом сам план идентичен выше описанным способам.
Детали поиска в индексе:
Если же взять по 16 байт поле разбить:
CREATE TABLE dbo.metadata
(
id bigint NOT NULL,
sha256_part1 binary(16) NOT NULL,
sha256_part2 binary(16) NOT NULL,
CONSTRAINT pk_metadata PRIMARY KEY CLUSTERED (id)
)
CREATE NONCLUSTERED INDEX IX_sha256_part1_include_sha256_part2 ON dbo.metadata (sha256_part1) INCLUDE(sha256_part2)То получается очень плохая картина, а именно:
Table 'metadata2'. Scan count 1, logical reads 759177760, 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 276880, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
(затронута одна строка)
SQL Server Execution Times:
CPU time = 60563 ms, elapsed time = 60644 ms.
Запрос выполнялся более 60 сек. Здесь также вызов был 3 раза и после каждого раза чистился кэш планов запросов. Взят результат 3-го раза.
Так что Ваш вариант лучше, спасибо!
Оптимизация поиска по большому полю