Multi-Entry Generalized Search Trees
summary
PostgreSQL extensions implement MGiST/MSP-GiST to split each tuple into multiple index entries (like GIN but for GiST/SP-GiST) and add an extract_value method plus duplication handling; applied to multi-range types and MobilityDB trajectories. Index size grows (about 3× in one test) but reduces false positives and rechecks, giving about 20× speedup on a multi-range contains query (1.7 ms → 0.08 ms) and roughly 10× on trajectory spatial queries; extract_query support and multicolumn coordination remain work in progress, code on GitHub.
AI-written summary · about
chapters (12)
- 0:00Introduction and background
- 1:30Postgres index overview
- 4:00Multi-range types and limitations
- 8:57Mist index design explained
- 13:09Performance benefits of Mist
- 16:39When Mist outperforms Gist
- 17:25Mobility DB trajectories
- 21:46Trajectory indexing with Mist
- 24:18Other data types benefiting from Mist
- 28:59Extract query and path types
- 31:47Implementation and extensions
- 37:12Q&A session
