Database Indexing medium
For query `SELECT * FROM tbl ORDER BY A ASC, B DESC`, what index is required to avoid a sort operation?
- A A standard individual index on column A followed by a secondary individual index on column B to allow for independent directional scans.
- B A composite index defined with mixed directions: `Index (A ASC, B DESC)` to match the query's required ordering exactly.
- C Two strictly independent indexes on A and B that the database optimizer can merge in real-time using a specialized 'Sort Intersection' algorithm.
- D A reverse-order composite index `Index (B, A)` that allows the database to perform a backward scan of the entire B-Tree from the final leaf node.
Answer: B. A composite index defined with mixed directions: `Index (A ASC, B DESC)` to match the query's required ordering exactly.
Standard B-Trees can be scanned in forward or reverse order. However, if you are sorting by two different directions (A up, B down), a standard `Index (A, B)` will fail. For every value of A, the values of B are stored sorted ASC. To find the highest B for the lowest A, the database would have to perform thousands of random seek-jumps. A mixed-direction index pre-sorts the data exactly how you need it, enabling a perfectly smooth sequential scan.
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')?