SQL Indexes: Range Queries and Partitioning

At Boundev, we've optimized database layers across 31 dedicated team engagements where SQL performance was the primary scaling constraint. The pattern is consistent: teams that understand B-tree mechanics and partitioning strategy reduce query latency by 10x-100x without hardware upgrades.

Most SQL performance problems are not caused by too much data. They are caused by queries that access data inefficiently, indexes that are structured incorrectly for the query patterns, and maintenance strategies that let fragmentation accumulate until the database crawls. Understanding exactly how B-tree indexes serve range queries, why certain SQL patterns defeat the optimizer, and when partitioning helps versus hurts is the foundation of production-grade database engineering.

The difference between a query that reads 5 blocks and a query that reads 500,000 blocks is not hardware. It is how well the developer understands index mechanics.

How Covering Indexes Eliminate Table Reads

A covering index contains every column that a query needs: the columns in the WHERE clause, the JOIN conditions, and the SELECT list. When all required data lives in the index, the database engine never needs to jump back to the base table to fetch additional columns. This eliminates the most expensive operation in non-covering index usage: random I/O to the table for each matching index entry.

Consider a reservations system where you frequently query client names for a specific hotel and date range. Without a covering index, the database finds matching rows via the index, then performs a separate lookup to the base table for each row to retrieve the client name. With a covering index that includes the client name column, the query is satisfied entirely from the index.

-- Query: Find client names for a specific hotel and date range
SELECT c.ClientName
FROM Reservations r
JOIN Clients c ON r.ClientID = c.ClientID
WHERE r.DateFrom BETWEEN '2020-08-13' AND '2020-08-14'
  AND r.HotelID = 3;

-- Covering index on Reservations (HotelID, DateFrom, ClientID)
-- eliminates table lookups for the Reservations table entirely.
-- The database traverses only the index B-tree.

The Range Query Execution Model

Range queries are the most common use case for B-tree indexes. They restrict data based on conditions like "Column A must be between X and Y." The execution model for a properly indexed range query is remarkably efficient: the database traverses the B-tree to find the first matching entry, then reads sequentially through the sorted leaf pages until it passes the range boundary. The total number of disk blocks read is determined by a simple formula.

Why Functions on Indexed Columns Kill Performance

One of the most common indexing mistakes we see in staff augmentation engagements is wrapping indexed columns in functions within WHERE clauses. When you apply a function to an indexed column, the database cannot use the index's sorted order because the function transforms the column value into something the index does not contain. The optimizer falls back to scanning every entry in the index and applying the function to each one.

Here is the concrete example. Suppose you want all reservations where the check-in date falls on August 15, 2020, and the CheckInTime column stores a full timestamp. The instinctive query wraps the column in a date-extraction function:

-- BAD: Function on the indexed column prevents range scan
SELECT c.ClientName
FROM Reservations r
JOIN Clients c ON r.ClientID = c.ClientID
WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';
-- Execution: scans EVERY index entry, applies TO_DATE() to each

-- GOOD: Range condition on the raw column enables B-tree traversal
SELECT c.ClientName
FROM Reservations r
JOIN Clients c ON r.ClientID = c.ClientID
WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH24:MI:SS')
  AND r.CheckInTime <  TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH24:MI:SS');
-- Execution: navigates to first match, reads sequentially, stops at boundary

The rewritten query produces identical results but uses a completely different execution plan. The database locates the first entry where CheckInTime is midnight on August 15, reads forward through the sorted index, and stops as soon as it encounters midnight on August 16. The difference can be orders of magnitude: scanning 500,000 index entries versus reading 47 entries directly.

LIKE Patterns and Index Behavior

The position of the wildcard in a LIKE pattern determines whether the database can use the B-tree's sorted order. This distinction is critical for query design and is frequently misunderstood by developers who assume that any LIKE query benefits from an index on the filtered column.

-- Leading wildcard: full index scan, then table lookups (SLOW)
SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';
-- Reads every entry in IX_LastName, checks suffix for each

-- Trailing wildcard: B-tree range scan (FAST)
SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';
-- Navigates to 'Rob', reads forward, stops at 'Roc'
-- Equivalent to: WHERE LastName >= 'Rob' AND LastName < 'Roc'

B-tree Scaling: Why Table Size Is Rarely the Problem

When queries slow down as data volume grows, the instinctive reaction is to blame table size. This is almost always wrong for properly indexed range queries. The total blocks read for a range query using an index follows the formula B = D + 1 + R, where D is tree depth and R is rows returned. The only parameter that depends on total table size is D, and D grows logarithmically.

Growing from 10,000 rows to 1 billion rows adds at most 2 additional block reads to a 50-row range query. The execution time difference is unmeasurable. If your range queries are slowing down as data grows, the cause is almost certainly not increased tree depth. It is fragmentation, missing indexes, or queries that do not use range conditions effectively.

The Real Bottleneck: Index Fragmentation

B-tree indexes maintain sorted order by splitting blocks when they become full. When a new entry needs to be inserted into a full leaf block, the database splits it into two half-full blocks. Over time, with ongoing inserts, updates, and deletes, the physical order of blocks on disk diverges from the logical order of the index. This fragmentation means that "sequential" reads through the index actually involve random disk seeks between non-contiguous blocks.

-- SQL Server: Check fragmentation level
SELECT
    OBJECT_NAME(ips.object_id) AS TableName,
    i.name AS IndexName,
    ips.avg_fragmentation_in_percent,
    ips.page_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'LIMITED') ips
JOIN sys.indexes i ON ips.object_id = i.object_id AND ips.index_id = i.index_id
WHERE ips.avg_fragmentation_in_percent > 30
ORDER BY ips.avg_fragmentation_in_percent DESC;

-- Rebuild fragmented indexes
ALTER INDEX IX_Reservations_DateFrom ON Reservations REBUILD;

-- PostgreSQL equivalent
REINDEX INDEX ix_reservations_datefrom;

Table Partitioning: Maintenance Solution, Query Complexity

When tables grow to billions of rows, the operational challenge shifts from query speed to maintenance. Deleting old data row-by-row is prohibitively slow and leaves behind massive fragmentation. Reindexing a billion-row table can take hours. Table partitioning solves these maintenance problems by splitting the table into smaller, independently manageable chunks, typically by date ranges.

Partitioning and Index Strategy

The critical decision in a partitioned table is how indexes interact with partitions. The three approaches, global indexes, globally partitioned indexes, and local indexes, each have different trade-offs for query performance and maintenance.

-- Local index problem: query without partition key
-- must scan every partition's local index
SELECT DateFrom, DateTo
FROM Reservations
WHERE ClientID = 124 AND HotelID = 1;
-- With local IX_HotelID_ClientID, the RDBMS reads this index
-- from EVERY partition (Jan, Feb, Mar, Apr...) separately.
-- 12 monthly partitions = 12 separate index traversals.

-- Partition-aligned query: only reads relevant partition
SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo
FROM Reservations
WHERE DateFrom BETWEEN '2021-03-01' AND '2021-03-03';
-- Partition pruning: only the March partition is accessed.
-- Local index on DateFrom within that partition works efficiently.

Practical Index Design Checklist

Based on our work across software outsourcing projects with SQL-heavy workloads, here is the index design checklist our database engineers follow before any production deployment:

Frequently Asked Questions