Являются ли уникальные индексы лучшими для производительности поиска по столбцам? (PGSQL и MySQL)

Мне любопытно,

CREATE INDEX idx ON tbl (columns);

vs.

CREATE UNIQUE INDEX idx ON tbl (columns);

имеет значительный алгоритмический выигрыш в производительности в реализациях PostgreSQL или MySQL при сканировании индексированных столбцов, или если ключевое слово UNIQUE просто вводит уникальное ограничение рядом с индексом.

Я предполагаю, что будет справедливо сказать, что существует незначительное преимущество, поскольку индексы, вероятно, будут внутренне реализованы как некая структура, похожая на хэш1, а обработка коллизий по определению приводит к чему-то другому, чем O(1) производительность. Учитывая эту предпосылку, вполне вероятно, что если большой процент значений совпадает, то структура вырождается во что-то линейное.

Итак, для целей моего вопроса предположим, что распределение значений относительно дискретно и равномерно.

Заранее спасибо!

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


mysql postgresql indexing hash
person Alex Balashov    schedule 18.08.2009    source источник

Ответы (3)


arrow_upward
27
arrow_downward

Если ваши данные уникальны, вы должны создать для них индекс UNIQUE.

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

Например, в SQL Server и в PostgreSQL, если вы сортируете по ключу UNIQUE, оптимизатор игнорирует используемые после этого предложения ORDER BY (поскольку они не имеют значения), т.е. е. этот запрос:

SELECT  *
FROM    mytable
ORDER BY
        col_unique, other_col
LIMIT 10

будет использовать индекс по col_unique и не будет сортировать по other_col, потому что это бесполезно.

Этот запрос:

SELECT  *
FROM    mytable
WHERE   mycol IN
        (
        SELECT  othercol
        FROM    othertable
        )

также будет преобразован в INNER JOIN (в отличие от SEMI JOIN), если для othertable.othercol есть индекс UNIQUE.

Индекс всегда содержит какой-либо указатель на строку (ctid в PostgreSQL, указатель строки в MyISAM, первичный ключ/уникификатор в InnoDB), и листья упорядочены по этим указателям, поэтому на самом деле каждый лист индекса каким-то образом уникален ( хотя это может быть не очевидно).

Подробнее о производительности см. в этой статье в моем блоге:

person Quassnoi    schedule 18.08.2009

arrow_upward
4
arrow_downward

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

person Eric    schedule 21.01.2016
comment
К вашему сведению, он все равно должен сканировать btree, чтобы найти страницу для размещения проиндексированных данных, так что это в значительной степени промывка. - person xzilla; 31.07.2020

arrow_upward
2
arrow_downward

Что ж, обычно индексы представляют собой B-деревья, а не хэши (существуют индексы на основе хэшей, но наиболее распространенный индекс (по крайней мере, в PostgreSQL) основан на B-дереве).

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

person Community    schedule 18.08.2009