Database Design
Indexes and Query Performance
Database indexes are specialized data structures that provide a rapid lookup path to specific rows, dramatically reducing the amount of data the engine must scan. By minimizing I/O overhead, they transform slow linear scans into efficient logarithmic searches, which is critical for maintaining performance as tables grow to millions of records. You should reach for indexing when queries involving filtering, sorting, or joining become the primary bottleneck in your application's responsiveness.
Understanding the B-Tree Index
To understand why indexes improve performance, consider the alternative: a full table scan. Without an index, the database must read every single page of data from the disk to check if a row matches your criteria, which is an O(N) operation. B-Tree indexes restructure this data into a balanced, sorted tree. By storing values in a sorted hierarchy, the database can traverse the tree to find the specific pointer to your data in O(log N) time. This is analogous to looking up a term in the back of a textbook versus reading every single page of the book until you find the word. The 'balanced' aspect ensures that no matter which value you look for, the path taken through the tree is roughly the same length, providing predictable and consistent query execution times regardless of table size.
-- Create a standard B-Tree index on a column frequently used in WHERE clauses
CREATE INDEX idx_users_email ON users (email);
-- The query planner now uses the index to find the record instead of scanning the table
SELECT * FROM users WHERE email = 'dev@example.com';Clustered versus Non-Clustered Indexes
In a database, the physical order of data on the disk is defined by the clustered index. By default, the Primary Key often acts as the clustered index, meaning the actual rows are sorted according to this key. Because the data itself is stored in the leaf nodes of the B-Tree, retrieving a record via a clustered index is incredibly fast. A non-clustered index, however, is a separate structure that stores the indexed column value and a pointer back to the actual data row. When you query a non-clustered index, the engine must perform a 'key lookup' to go from the index page to the actual data page. This two-step process makes non-clustered indexes slightly more expensive than clustered ones, but allows you to create multiple search paths on a single table for various query patterns.
-- This clustered index defines the physical order of rows on disk
CREATE CLUSTERED INDEX idx_pk_orders ON orders (order_id);
-- This non-clustered index creates a separate map to find orders by date
CREATE NONCLUSTERED INDEX idx_orders_date ON orders (order_date);Optimizing Performance with Composite Indexes
A common mistake is assuming that indexing individual columns is sufficient for complex queries. When you have filters on multiple columns, such as 'WHERE status = 'active' AND created_at > '2023-01-01'', the database engine can only use one index per table per query in many scenarios, or it may struggle to merge multiple indexes efficiently. A composite index (or multi-column index) solves this by bundling multiple columns into a single index structure. The order of columns in a composite index is critical because the B-Tree sorts the data by the first column, then the second, and so on. This means you should order your columns by selectivity—placing the most unique or restrictive column first. A properly ordered composite index allows the engine to navigate the tree once and satisfy the entire predicate without needing additional lookups.
-- Composite index for queries filtering by both status and created_date
CREATE INDEX idx_orders_status_date ON orders (status, created_at);
-- This query benefits from the composite index because of the leftmost prefix rule
SELECT * FROM orders WHERE status = 'shipped' AND created_at > '2023-05-01';The Covering Index Strategy
A covering index occurs when an index contains every single column requested in a query's SELECT statement. When this condition is met, the database engine can retrieve all the required information directly from the index tree without ever accessing the underlying table heap or clustered index. This is a massive performance gain because it eliminates the expensive random I/O associated with fetching data pages from disk. In performance-critical systems, developers often add non-key columns to an index using the INCLUDE clause to 'cover' specific high-frequency queries. While this increases storage usage and maintenance overhead, the trade-off is often justified by the resulting reduction in disk latency and CPU usage. Always evaluate if the cost of the extra index size outweighs the gains of avoiding page lookups in your specific workload environment.
-- Adding include columns makes this a covering index for the select statement
CREATE INDEX idx_user_stats ON users (last_login) INCLUDE (user_id, status);
-- The engine satisfies this query entirely from the index leaf nodes
SELECT user_id, status FROM users WHERE last_login > '2023-01-01';Maintenance and the Cost of Indexes
Every index comes with a hidden cost: write amplification. Whenever you perform an INSERT, UPDATE, or DELETE operation, the database must not only update the table itself but also re-balance and update every index that contains the modified columns. If a table has twenty indexes, a single row insertion could trigger twenty additional write operations to update those trees. This overhead can significantly degrade the performance of write-heavy applications. Furthermore, indexes can become fragmented over time as rows are deleted and updated, leading to gaps in data pages and inefficient traversals. Database administrators must regularly monitor index usage to drop unused indexes and perform maintenance tasks like defragmentation or rebuilding to ensure the B-Tree remains efficient. Balancing read performance through indexing against write latency is the core challenge of database schema design.
-- Identify unused indexes to reduce write overhead
-- (Querying system statistics to find indexes with zero scans)
SELECT * FROM index_usage_stats WHERE user_scans = 0;
-- Rebuild a fragmented index to regain performance
ALTER INDEX idx_orders_status_date ON orders REBUILD;Key points
- Indexes use balanced B-Tree structures to convert linear O(N) searches into efficient logarithmic O(log N) operations.
- Clustered indexes define the physical order of data rows, while non-clustered indexes provide secondary search paths.
- The leftmost prefix rule requires that columns in a composite index must be used in order to utilize the full index structure.
- Covering indexes prevent expensive table lookups by including all requested columns directly within the index storage.
- Index selectivity is determined by the uniqueness of the data, and highly selective columns should appear first in composite indexes.
- Every index added to a table incurs a performance penalty on write operations due to the need to update index structures.
- Excessive indexing can lead to bloat and fragmentation, which degrades overall system performance over time.
- Regular maintenance, including removing unused indexes and defragmenting existing ones, is essential for long-term query health.
Common mistakes
- Mistake: Indexing every single column in a table. Why it's wrong: Indexes slow down write operations (INSERT, UPDATE, DELETE) and consume excessive disk space. Fix: Only index columns frequently used in WHERE clauses, JOIN conditions, or ORDER BY clauses.
- Mistake: Using functions on indexed columns in a WHERE clause. Why it's wrong: Functions like UPPER(column) or YEAR(date_column) prevent the database from using the index, leading to a full table scan. Fix: Keep columns raw and transform values on the right side of the operator.
- Mistake: Creating indexes that start with low-cardinality columns. Why it's wrong: Indexes are most effective when they narrow down results quickly; columns like 'gender' have few unique values. Fix: Lead composite indexes with high-cardinality columns that filter the most rows.
- Mistake: Ignoring the order of columns in composite indexes. Why it's wrong: Composite indexes are only utilized if the query matches the leftmost prefix of the index definition. Fix: Design composite indexes based on the specific order of columns used in common query filters.
- Mistake: Relying on indexes for small tables. Why it's wrong: Reading the entire table into memory is often faster than reading an index tree then performing a bookmark lookup. Fix: Only add indexes to tables large enough that the cost of an index scan is significantly lower than a full table scan.
Interview questions
What is a database index, and why does it improve query performance?
A database index is a data structure, typically a B-tree, that improves the speed of data retrieval operations on a table at the cost of additional writes and storage space. Without an index, SQL must perform a full table scan, checking every single row to find matches. With an index, the database engine can navigate the tree structure to locate specific rows in logarithmic time, significantly reducing the I/O required for queries that use filters or joins.
What is the difference between a clustered and a non-clustered index?
A clustered index determines the physical order of data in a table; therefore, a table can have only one because the data rows can only be sorted in one order. A non-clustered index is a separate structure that stores the key values and a pointer to the actual data rows. While a clustered index is highly efficient for range scans, non-clustered indexes allow for multiple ways to quickly find data based on different columns.
What is a composite index, and what is the 'leftmost prefix' rule?
A composite index is an index created on multiple columns in a single table. The 'leftmost prefix' rule dictates that for the index to be utilized by the query optimizer, the query must filter by the leftmost columns defined in the index. For example, if you create an index on (last_name, first_name), searching by last_name will use the index, but searching only by first_name will result in a full table scan because the index is not prefix-aligned.
Compare the performance impacts of using an index versus performing a table scan.
A table scan requires the database to read every data page from the disk, which is an O(N) operation that becomes extremely slow as data grows. In contrast, an index provides an O(log N) lookup path. For small tables, a scan might be faster due to the overhead of traversing an index; however, for large datasets, using an index is vital to prevent performance bottlenecks. SQL developers must balance this by ensuring queries are selective enough to justify index traversal.
What are 'covering indexes,' and how do they optimize performance?
A covering index is an index that includes all the columns requested by a specific SQL query, meaning the database engine can retrieve all the necessary data directly from the index structure without ever performing a look-up into the underlying table data pages. By eliminating the 'key lookup' or 'bookmark lookup' step, the engine drastically reduces disk I/O. For instance, in the query: SELECT email FROM users WHERE user_id = 10, an index on (user_id, email) would be a covering index.
Why can adding too many indexes degrade performance instead of improving it?
Adding indexes is not free because every time a row is inserted, updated, or deleted, the database engine must also update all associated indexes to maintain consistency. Excessive indexing incurs a high write penalty, slowing down Data Manipulation Language (DML) operations. Furthermore, the query optimizer must evaluate more potential execution plans, which increases the overhead of parsing and optimizing each query, potentially choosing suboptimal paths if the database statistics become bloated or outdated.
Check yourself
1. A query performs a full table scan even though an index exists on the 'status' column. Which query is most likely causing this?
- A.SELECT * FROM orders WHERE status = 'SHIPPED'
- B.SELECT * FROM orders WHERE status LIKE 'SHIP%'
- C.SELECT * FROM orders WHERE status + 1 = 2
- D.SELECT * FROM orders WHERE status IN ('SHIPPED', 'PENDING')
Show answer
C. SELECT * FROM orders WHERE status + 1 = 2
Applying math to a column in a WHERE clause makes the index unusable because the database must calculate the value for every row. The other options are SARGable (Search ARGumentable) and allow the engine to perform index seeks.
2. Which scenario best justifies the creation of a composite index on (last_name, first_name)?
- A.Frequent queries filtering by first_name only
- B.Queries searching for a specific first_name and sorting by last_name
- C.Frequent queries filtering by last_name, or both last_name and first_name
- D.Queries that perform an aggregate COUNT(*) on the entire table
Show answer
C. Frequent queries filtering by last_name, or both last_name and first_name
Composite indexes work on the leftmost prefix rule. It supports filtering by the first column alone or both, but not the second column alone. Option 1 and 2 violate the order, while option 4 is usually better handled by a single-column index or a primary key.
3. How does an excessive number of indexes impact database performance during DML operations?
- A.It increases the time required to perform INSERT and UPDATE operations
- B.It decreases the storage requirements of the database
- C.It speeds up SELECT queries by providing more access paths
- D.It eliminates the need for table locks
Show answer
A. It increases the time required to perform INSERT and UPDATE operations
Every index must be updated whenever data changes, which creates overhead. Options 1 is correct; option 2 is false as indexes take space, option 3 is misleading because the optimizer only picks the 'best' index, and option 4 is irrelevant.
4. When is a 'Covering Index' most beneficial for query performance?
- A.When the index contains all columns mentioned in the SELECT, JOIN, and WHERE clauses
- B.When the index is built on a column with many null values
- C.When the table is small enough to fit entirely in memory
- D.When the query requires a full table scan
Show answer
A. When the index contains all columns mentioned in the SELECT, JOIN, and WHERE clauses
A covering index allows the engine to retrieve all requested data directly from the index tree without fetching the actual table row, drastically reducing I/O. Other options are incorrect as they don't describe the benefit of data inclusion.
5. Why might an optimizer choose to perform a full table scan instead of using an existing index?
- A.The index is too small to be useful
- B.The query is retrieving a very large percentage of the total table rows
- C.The index was not recently defragmented
- D.The database is using a non-relational storage engine
Show answer
B. The query is retrieving a very large percentage of the total table rows
If a query returns a high percentage of rows, the overhead of performing index lookups (B-tree traversal plus heap fetching) is higher than just reading the entire table sequentially. The other choices are generally not primary factors for ignoring an index.