Как индекс определяет, какую запись отдать при поиске по таблице

Что проверяют

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

Как отвечать

Разберите на примере B-tree в PostgreSQL, это индекс по умолчанию:

• структура: сбалансированное дерево страниц. Внутренние узлы хранят границы ключей, листья хранят ключ и указатель на строку в таблице (ctid: номер страницы и позиция в ней). Листья связаны между собой, поэтому диапазон читается подряд;
• поиск: спуск от корня к листу за логарифм от числа строк, дерево неглубокое даже на миллионах записей. Для id = 10 находится лист, из него берётся ctid, по нему читается сама строка;
• видимость: индекс не знает, видна ли версия строки вашей транзакции. Это проверяется по xmin и xmax в самой строке, поэтому после индекса почти всегда идёт чтение таблицы. Исключение: Index Only Scan, когда все нужные колонки есть в индексе, а страница отмечена в visibility map;
• много совпадений: вместо поштучного чтения база строит битовую карту страниц (Bitmap Heap Scan) или вовсе выбирает Seq Scan;
• выбор плана: решает планировщик по статистике ANALYZE и оценке селективности, а не сам факт наличия индекса.

Для контраста: в MySQL InnoDB таблица сама кластерный индекс по первичному ключу, а вторичный индекс хранит значение этого ключа, и поиск идёт по двум деревьям.

Из Go план проверяйте через EXPLAIN (ANALYZE, BUFFERS). Учтите, что pgx по умолчанию отправляет подготовленные выражения, и после нескольких выполнений PostgreSQL может перейти на общий план, не зависящий от значения параметра.

Где спотыкаются

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

Путают B-tree с бинарным поиском по массиву. Дерево широкое и читается страницами, в этом и экономия обращений к диску.

Не смотрят план, а утверждают «индекс же есть». Приведение типов, функция над колонкой или устаревшая статистика легко переводят запрос в Seq Scan.