Database Indexing, Sargability & EXPLAIN Query Tuning

📖 Physical Storage & Database Indexing

When an application queries a database without an index, the engine must perform a Full Table Scan (Sequential Scan)—reading every single data page from disk into memory to evaluate predicates.

• Analogy: Library Card Catalog & Book Index.
  • Full Table Scan: Reading every page of every book in a 1,000,000-book library to locate references to "Quantum Computing".
  • Clustered Index: The physical shelf arrangement of the books themselves (arranged strictly by Dewey Decimal / Primary Key). Because physical books can only reside in one physical order on a shelf, a table can possess only ONE Clustered Index.
  • Non-Clustered (Secondary) Index: The alphabetized card catalog drawers at the library entrance. Each index card contains the search keyword and a pointer slip (RowID / Primary Key) directing you to the physical book shelf location.

                           Physical Storage Layout
                                      │
        ┌─────────────────────────────┴─────────────────────────────┐
        ▼                                                           ▼
Clustered Index (Table Data Pages)                     Non-Clustered Index (Secondary B-Tree)
Leaf pages ARE the actual physical table data rows      Leaf pages store Index Keys + RowID / PK Pointers
Strictly 1 allowed per table                           Multiple allowed per table

🌲 B-Tree Index Data Structure Mechanics

Relational database indexes predominantly utilize Balanced Trees (B-Trees) to guarantee logarithmic search, insertion, and deletion time complexity:

O(log_B N)

                                  [Root Node: K=50]
                                    /           \
               [Internal Node: K=20, K=35]     [Internal Node: K=70, K=85]
                 /          |         \          /          |         \
           [Leaf 10,15] [Leaf 20,30] [Leaf 35,45] [Leaf 50,65] [Leaf 70,80] [Leaf 85,99]

1. Root & Internal Nodes: Store key values and child page pointers to direct search navigation down the tree levels.
2. Leaf Pages: Store sorted index keys along with physical data pointers (RowID in heap tables or Primary Key value in clustered tables).
3. Logarithmic Depth: A 3-level B-Tree with a block fanout $B = 100$ can index up to $1,000,000$ tuples in just 3 I/O page reads!

🎯 Indexing Strategies & Advanced Index Types

1. Composite Indexes & The Leftmost Prefix Rule

A multi-column composite index CREATE INDEX idx_name ON users(last_name, first_name) sorts index entries primarily by last_name, and secondarily by first_name.

[!IMPORTANT] The Leftmost Prefix Rule:

• WHERE last_name = 'Smith' $\rightarrow$ USES INDEX
• WHERE last_name = 'Smith' AND first_name = 'John' $\rightarrow$ USES INDEX
• WHERE first_name = 'John' $\rightarrow$ CANNOT USE INDEX (Violates leftmost prefix boundary!)

2. Covering Indexes (INCLUDE Clause) & Index-Only Scans

A Covering Index includes non-search payload columns directly within the leaf nodes of the B-Tree index:

-- Creating a covering index containing payload column 'email'
CREATE INDEX idx_users_dept_covering ON users(dept_id) INCLUDE (email);

When executing SELECT email FROM users WHERE dept_id = 10;, the engine performs an Index-Only Scan—fetching data directly from the B-Tree leaf pages without executing expensive secondary heap table lookups!

3. Partial & Expression Indexes

• Partial Index: Indexes only a subset of table rows matching a WHERE condition, drastically reducing disk size:

  -- Indexes ONLY active unfulfilled orders
  CREATE INDEX idx_unfulfilled_orders ON orders(order_date) WHERE status = 'UNFULFILLED';

• Expression Index: Indexes the computed result of a function:

  -- Enables index lookups for case-insensitive email searches
  CREATE INDEX idx_lower_email ON users(LOWER(email));

⚡ Sargability: Writing Search Argumentable Queries

A query is Sargable (Search Argumentable) if the query engine can utilize a B-Tree index to perform a direct index range scan.

                           Sargable vs Non-Sargable
                                      │
        ┌─────────────────────────────┴─────────────────────────────┐
        ▼                                                           ▼
❌ Non-Sargable Anti-Pattern                                 ✅ Sargable Refactoring
Function wraps column; forces full scan                      Column evaluated raw against literal
WHERE LOWER(email) = '[email protected]'                         WHERE email = LOWER('[email protected]')

Sargability Anti-Pattern Hall of Shame:

🩺 Diagnostics: Deconstructing EXPLAIN ANALYZE

In PostgreSQL/MySQL, prefixing a query with EXPLAIN ANALYZE executes the plan and outputs real runtime diagnostic telemetry:

EXPLAIN ANALYZE
SELECT e.emp_name, d.dept_name
FROM employees e
JOIN departments d ON e.dept_id = d.dept_id
WHERE e.salary > 75000;

Reading Plan Operators:

1. Seq Scan: Full Table Scan. High I/O cost on large tables; candidates for indexing.
2. Index Scan: Navigates B-Tree index and performs secondary heap page lookups for data columns.
3. Index Only Scan: Optimal! All required query columns exist inside the B-Tree index leaf pages.
4. Bitmap Index Scan + Bitmap Heap Scan: Scans index to build an in-memory bitmask of matching page physical locations, then reads disk pages sequentially.

❓ Conceptual Quizzes

💻 Practice Problems

SELECT order_id, customer_id, order_total
FROM orders
WHERE DATE_TRUNC('year', order_date) = '2024-01-01'::DATE;