B-tree и порядок столбцов

В Brew завели один индекс на таблицу позиций меню — по (category, price) — и закрыли тему «поиск по меню». Запрос «капучино дешевле 500» летал. А отчёт «все позиции за 250 рублей по всем категориям» неожиданно полз: тот же индекс, тот же столбец price внутри него — но запрос его будто не видел. Дело в том, что порядок столбцов в составном индексе — не косметика. B-tree хранит строки отсортированными сначала по первому столбцу, и только внутри одинаковых значений первого — по второму. Спросить «по второму, не зная первого» — это как искать слово в словаре, отсортированном сперва по длине: знание второй буквы не помогает, пока не знаешь первую.

Цель юнита — правило левого префикса: какой запрос составной индекс ускоряет, а какой нет, и почему это зависит от порядка столбцов. И сразу — что в этой картине меняет PG18 skip-scan: он умеет вытащить индекс даже там, где раньше был только Seq Scan.

Правило левого префикса

Индекс по (a, b) физически отсортирован по a, затем по b. Из этого следует, какие запросы он обслуживает:

WHERE a = ... AND b = ... — идеально: спускаемся по a, внутри — по b. Оба условия попадают в Index Cond.
WHERE a = ... (только лидирующий столбец, левый префикс) — тоже работает: все строки с нужным a лежат в индексе подряд. Index Cond по a.
WHERE b = ... (только второй столбец) — классически не работает: строки с нужным b разбросаны по всему индексу (внутри каждого a — свой кусочек). Планировщику дешевле прочитать таблицу целиком (Seq Scan), чем прыгать по индексу.

Отсюда практическое правило: первым ставь столбец, по которому фильтруешь чаще и по равенству (а не по диапазону). Индекс (category, price) обслуживает поиск по категории и по «категория + цена»; для поиска «только по цене» он, в классическом мире, бесполезен — нужен отдельный индекс по (price) или другой порядок.

Что меняет PG18 skip-scan

Раньше «только по второму столбцу» означало однозначный Seq Scan. PostgreSQL 18 добавил skip-scan для B-tree: если у лидирующего столбца мало различных значений (наш случай — 4 категории), планировщик может перебрать их по очереди и внутри каждого нырнуть в индекс за нужным b. Получается серия маленьких поисков вместо чтения всей таблицы.

Увидеть skip-scan можно по полю Index Searches в EXPLAIN ANALYZE: для обычного индексного доступа оно равно 1, а для skip-scan — больше единицы (индекс «искали» по разу на каждое значение лидирующего столбца). В нашем демо Index Searches: 9 против Index Searches: 1 у обычных запросов — это и есть отпечаток skip-scan.

⚠️ Skip-scan смягчает правило левого префикса, но не отменяет его. Он выгоден только при низкой кардинальности лидирующего столбца: 4 категории перебрать дёшево, а 100 000 клиентов — уже дороже, чем Seq Scan. Планировщик решает по стоимости; полагаться на «PG18 сам разберётся» вместо правильного порядка столбцов — плохая ставка.

Как лежит составной индекс

Индекс (category, price) физически отсортирован сперва по category, и только внутри одной категории — по price. Отсюда вся механика левого префикса:

plaintext

Индекс (category, price): строки отсортированы по category (алфавит),
а внутри одной категории — по price.
 
  bakery │  1, 2, …, 503     ┐
  coffee │  1, 2, …, 503     │  WHERE category=… → весь блок подряд   ✓ левый префикс
  cold   │  1, 2, …, 503     │  WHERE price=250  → одна строка 250 в каждом
  tea    │  1, 2, …, 503     ┘  блоке, рассыпана по всему индексу      ✗

Это и есть «словарь по длине слова»: слова сгруппированы по длине (category), и лишь внутри длины — по алфавиту (price). Знаешь длину — открыл нужный блок сразу; знаешь только букву (price), но не длину — придётся листать все блоки. Три формы запроса к индексу (a, b):

Запрос к `(a, b)`	Что делает индекс `(category, price)`	`Index Searches`
`WHERE a = … AND b = …`	спуск по `category`, внутри — по `price`; оба в `Index Cond`	1
`WHERE a = …` (левый префикс)	строки с этим `category` лежат подряд; `Index Cond` по `category`	1
`WHERE b = …` (только второй)	строки рассыпаны по каждому `category`; классически `Seq Scan`, в PG18 skip-scan перебирает значения лидера	> 1 (у нас 9)

Что показывает наш код

demo.sql строит лабораторный стол menu_lab (200 000 строк, 4 категории, цены 1..503 — независимо от категории) с индексом (category, price) и объясняет три запроса:

sql

-- Q1: оба столбца → Index Cond по обоим, Index Searches: 1
SELECT * FROM menu_lab WHERE category = 'tea' AND price = 250;
-- Q2: левый префикс → Index Cond по category, Index Searches: 1
SELECT * FROM menu_lab WHERE category = 'tea';
-- Q3: только второй столбец → skip-scan, Index Searches: 9
SELECT * FROM menu_lab WHERE price = 250;

Все три используют один и тот же индекс menu_lab_cat_price_idx — но Q3 берёт его только благодаря skip-scan, и это видно по Index Searches.

Запуск

docker compose up -d
make lecture L=06-indexing-and-explain/06-02-btree-and-composite-column-order

Вывод:

plaintext

== Q1) фильтр по ОБОИМ столбцам (category=tea AND price=250) — оба в Index Cond ==
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Bitmap Heap Scan on menu_lab (actual rows=100.00 loops=1)
   Recheck Cond: ((category = 'tea'::text) AND (price = 250))
   Heap Blocks: exact=100
   ->  Bitmap Index Scan on menu_lab_cat_price_idx (actual rows=100.00 loops=1)
         Index Cond: ((category = 'tea'::text) AND (price = 250))
         Index Searches: 1
 
 
== Q2) левый префикс: только лидирующий столбец (category=tea) — индекс работает ==
                                    QUERY PLAN                                    
----------------------------------------------------------------------------------
 Bitmap Heap Scan on menu_lab (actual rows=50000.00 loops=1)
   Recheck Cond: (category = 'tea'::text)
   Heap Blocks: exact=1471
   ->  Bitmap Index Scan on menu_lab_cat_price_idx (actual rows=50000.00 loops=1)
         Index Cond: (category = 'tea'::text)
         Index Searches: 1
 
 
== Q3) только ВТОРОЙ столбец (price=250): до PG18 — Seq Scan, в PG18 — skip-scan ==
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Bitmap Heap Scan on menu_lab (actual rows=398.00 loops=1)
   Recheck Cond: (price = 250)
   Heap Blocks: exact=398
   ->  Bitmap Index Scan on menu_lab_cat_price_idx (actual rows=398.00 loops=1)
         Index Cond: (price = 250)
         Index Searches: 9

Q1 и Q2 берут индекс одним поиском (Index Searches: 1): и «оба столбца», и «только лидирующий» — это левый префикс. Q3 фильтрует по второму столбцу price без category — раньше тут был бы Seq Scan, но PG18 перебрал 4 категории через skip-scan, и Index Searches: 9 это выдаёт. Один и тот же индекс, разная цена доступа.

Заборчик

Что мы упростили:

category первым — ради демонстрации. Мы поставили его лидером, потому что skip-scan нужна низкая кардинальность лидера. В проде порядок столбцов выбирают под реальные запросы: первым — тот, по которому почти всегда фильтруют по равенству; диапазонный столбец (price > X, created_at BETWEEN ...) ставят последним — после диапазона индекс «расходится», и следующие столбцы уже не сужают поиск.
Skip-scan — страховка, не замена проектированию. При высокой кардинальности лидера он проигрывает Seq Scan. Полагаться на него вместо отдельного индекса по (price) не стоит.
У индекса есть цена записи и места. Каждый лишний индекс замедляет INSERT/UPDATE и занимает диск, поэтому «индекс на каждый случай» не бесплатен (про стоимость поддержки и CREATE INDEX CONCURRENTLY — в 06-06).

Какие именно индексы нужны кластеру под реальную нагрузку, как ловить неиспользуемые (pg_stat_user_indexes) и дубликаты — это приборная панель твоего DBA; твоя задача — подобрать порядок столбцов под свои запросы и проверить его в EXPLAIN.

Что забрать с собой

Составной индекс (a, b) отсортирован по a, затем по b — отсюда правило левого префикса.
Он обслуживает WHERE a и WHERE a AND b; WHERE b в одиночку — классически Seq Scan.
Порядок столбцов: первым — тот, по которому фильтруешь по равенству и почти всегда; диапазонный — последним.
PG18 skip-scan вытаскивает индекс и для одного второго столбца при низкой кардинальности лидера — виден по Index Searches > 1; смягчает правило, но не отменяет его.
Каждый индекс стоит записи и места — «индекс на всё» не бесплатен.

Дальше — 06-03 «Когда индексы не помогают»: почему индекс по email молчит при WHERE lower(email) = ..., что такое non-sargable условие и как это чинит индекс по выражению.