Database Indexing hard
In PostgreSQL, why can't an Index-Only Scan run without checking the Visibility Map?
- A The Visibility Map is used to perform the complex JOIN calculations that are required to synchronize data across several disparate nodes.
- B The index does not store MVCC Transaction IDs; the map identifies 'All-Visible' pages where it is safe to trust the index without checking the physical row.
- C The Visibility Map is used to ensure that all B-Tree indexes remain strictly ACID compliant during high-frequency concurrent update operations.
- D The database uses the map to ensure that the sequential Write-Ahead Log (WAL) is correctly synchronized with the B-Tree's internal page structures.
Answer: B. The index does not store MVCC Transaction IDs; the map identifies 'All-Visible' pages where it is safe to trust the index without checking the physical row.
In Postgres's MVCC implementation, the B-Tree index does *not* contain information about which transaction created or deleted a row (to keep the index lean). Consequently, an 'Index-Only Scan' could accidentally return a row that was deleted by another user. To avoid checking the main table (Heap) for every single row, Postgres uses a 'Visibility Map'. This map marks pages where every single row is definitely visible to all running transactions. If a page is marked as 'All-Visible', the database can safely return the index data without ever touching the disk for the main table.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- Z-Order Curves (Geohashing) map 2D data to 1D strings for indexing. What is their primary weakness?
- In-Memory databases (Hyper, HANA) often favor Adaptive Radix Trees (ART). Why?
- Log-Structured Merge (LSM) Trees (RocksDB, Cassandra) optimize for Write Throughput. How does their disk IO pattern differ from B-Trees?
- In LSM compaction strategies, 'Universal' (Tiered) compaction prioritizes what over 'Leveled' compaction?
- In LSM trees, what is 'Space Amplification'?
- Why is it generally ineffective to index a 'Low Cardinality' column like `Gender` ('Male'/'Female')?