Улучшены ли уникальные индексы для эффективности поиска столбцов? (PGSQL и MySQL)

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

CREATE INDEX idx ON tbl (columns);

против.

CREATE UNIQUE INDEX idx ON tbl (columns);

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

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

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

Спасибо заранее!

^{1 Это вопрос чистой спекуляции для меня, поскольку я не знаком с внутренними компонентами RDBM.}

Ответ 1

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

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

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

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 (в отличие от a SEMI JOIN), если на othertable.othercol есть индекс UNIQUE.

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

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

Создание индекса UNIQUE

Ответ 2

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

Ответ 3

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

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