Multidimensional search strategies for composite B-Tree indexes
summary
Adds Postgres 18 nbtree skip scan that treats composite B‑tree indexes as multidimensional and turns some full index scans into a series of small index searches using skip arrays and runtime adaptive decisions. Example: with 10 distinct leading A values a query WHERE b=5000 does an index‑only scan with about 10 distinct A values / 12 index searches instead of scanning every leaf page. Works with IN lists and ranges, improves Planner OR handling versus BitmapOr and can preserve index order for LIMIT/ORDER BY.
AI-written summary · about
chapters (7)
- 0:00Introduction to skip scan
- 1:38Skip scan internals and benefits
- 10:19Skip scan examples and mechanics
- 21:24Architectural goals and adaptive skipping
- 28:10Related optimizer work in PostgreSQL 18
- 34:06Future improvements for complex ORs
- 45:19Conclusions and open questions
related talks
49mFlexible Indexing with Postgres
53mAdvanced Indexing Techniques in PostgreSQL
37mRules of Indexing in PostgreSQL
48mB-tree Indexes in Databases Illustrated by IndexedDB and PostgreSQL
01h 00mFlexible Indexing With Postgres
45mA Deep Dive into PostgreSQL Indexing
37mRules of Indexing in PostgreSQL
40mnbtree Indexes in PostgreSQL: Useful New Features