Becoming Interview-Ready for Data Engineering Roles

Data Engineering Interview Prep Challenge: Day 11 — Indexing in SQL

Continuing my interview prep challenge, I am laying the foundations to understand query performance optimisation better.

Welcome to Day 11 of my Data Engineering Interview Prep Challenge! After covering and mastering essential SQL concepts in the previous articles, I am now moving towards SQL query optimisation. To lay the groundwork for query optimisation, having a strong understanding of indexes is paramount. Another reason for dedicating this article towards indexing is that oftentimes, understanding how indexes work, when to use them, and the trade-offs turns out to be beneficial in interviews.

Indexes are nothing but a physical structure that allows the database engine to locate rows quickly without scanning the entire table. They act like a lookup system, playing a vital role in improving query performance by speeding up data retrieval.

Why Indexing Matters

Indexes are the backbone of query performance. Imagine that you have a table with millions of rows. Without indexes, SQL queries rely on full table scans, where the database has to check every single row in a table of million rows, which in turn makes the SQL query slow and inefficient.

With indexes, the database can jump directly to the relevant rows, like using the “Table of Contents” section of a book, instead of going through the entire book.

How Indexes Work Internally

Most databases use a B-Tree (Balanced Tree) structure for indexes. Here’s how it works:

Structure:

• The index is organised as a tree data structure with multiple levels.
• Each “node” in the tree contains multiple keys (the indexed column values) and pointers.
• The tree is balanced, meaning all paths from root to leaf have the same length.

Visual representation:

                    [50]
                   /    \
                  /      \
            [20, 35]    [70, 90]
            /  |  \      /  |  \
           /   |   \    /   |   \
    [10,15] [25,30] [40,45] [60,65] [75,80] [95,100]
       ↓      ↓      ↓       ↓       ↓       ↓
    (rows) (rows) (rows)  (rows)  (rows)  (rows)

B-Tree → Leaf → Row Pointer → Exact Row

How a lookup works:

Let’s say you’re searching for the value 65:

1. Start at the root: Is 65 less than 50? No. Go right.
2. Next Level: Is 65 less than 70? Yes. Go left from 70.
3. Leaf Found: Found the range [60,65]. Retrieve the pointer to the actual table row.

This takes only 3 steps, instead of potentially millions with a full table scan!

The Key Insight: Logarithmic Time

The magic of B-Tree is that, with each step, it eliminates roughly half (or more) of the remaining possibilities (like a binary search). With a million row table, you might only need to check 3–4 nodes to find your data. This is an O(log n) operation.

Why this matters:

• 1,000 rows: ~3 lookups
• 1,000,000 rows: ~ 6 lookups
• 1,000,000,000 rows: ~9 lookups

Judge yourself.

What Happens Behind the Scenes

When you create an index: 1. The database scans the table 2. Extracts the indexed column values 3. Sorts them 4. Builds the tree structure with pointers back to table rows 5. Stores this as a separate B-Tree structure on disk

**When you query with an indexed column:

1. **The query optimiser recognises that the index exists
2. Uses the index to quickly locate matching rows
3. Follows the pointer to retrieve the full row data from the table.

Consider the following query, which retrieves data from the employees table and the column department_id is the indexed column.

SELECT * FROM employees WHERE department_id = 10;

Starting from the root node, the query optimiser will look through the next levels in the tree, navigating efficiently with each level. Once the index is located, it’ll return the entire row with department_id=10.

Types of Indexes

Clustered Index

It dictates the physical order in which the data is stored on the disk. The order of the data is defined by the index key, and the data is organised accordingly. Because the data can be stored in one physical order in the disk, you can have only one clustered index per table (usually the Primary Key).

An analogy would be a telephone directory where people are physically listed alphabetically by last name.

It is best used for Range Queries (e.g., BETWEEN '2023-01-01' AND '2023-01-31') because the data is sitting right next to each other.

Non-Clustered Index

It is stored as a separate data structure from the data table rows. It contains the indexed columns and a pointer (like a physical address) to the actual row in the table.

An analogy would be the “Table of Contents” section in any book. The keyword is in it, but you have to jump to the page number to find the actual content.

It is best used for columns frequently used in WHERE clause but not used in sorting or grouping.

Composite Index

It’s an index formed by combining two or more columns together. The order of the columns matters a lot. If you index (last_name, first_name), then it’s useful for searching "Doe" or "Doe, John," but it’s useless for searching "John" alone. (Left-side Prefix Rule)

Internally Stored as:
(last_name, first_name)
(Doe, John)
(Smith, Alice)
(Roy, Frank)

Covering Index

It isn’t a “type” you create, but rather a state a non-clustered index achieves. It happens when an index contains all the columns requested in a SELECT statement. The database never has to look at the actual table; it gets everything it needs from the index. This is the fastest possible way to retrieve data.

It eliminates the “Bookmark Lookup” step.

Unique Index

It is a type of index which ensures that no two rows in a table have the same value in the indexed column(s). The database automatically creates a unique index when you define a PRIMARY KEY or a UNIQUE constraint. It serves as a performance tool (speeding up searches) and a data integrity tool (preventing duplicates).

Hash Index

A Hash Index uses a hash table structure. It takes the column value, runs it through a hash function, and maps it to a specific “bucket”. It is incredibly fast for equality checks (WHERE id = 105), but it is completely useless for ranges (WHERE id > 105) or sorting. These are common in memory-optimised tables (like in PostgreSQL or SQL Server’s In-Memory OLTP)

Comparison Summary:

Syntax

A simple way to create an index on a table is by using CREATE INDEX statement. While the syntax varies for different database systems, like MySQL, PostgreSQL, and SQL Server, the core logic remains standardised.

CREATE [UNIQUE] INDEX index_name
ON table_name (column1, [column2, ...]);

**index_name** is the internal label for your index. Best practice is to use a descriptive name (e.g., idx_employee_last_name) so other developers can easily identify its purpose.

**(column1, ...) are the specific fields you want to optimise. If only one column is listed, then the engine creates a simple index. If multiple columns are listed, then the database engine creates a Composite Index.**

Pitfalls and Trade-Offs

Indexes are a trade-off between read-intensive SQL queries and write-intensive SQL queries. They speed up reads but slow down writes. For every INSERET / UPDATE / DELETE the database must:

1. Modify the table heap
2. Update each relevant index
3. Rebalance B-Tree if needed.

Since they are stored separately, too many indexes cause an overhead on disk space, because, along with the data, storage space is required for indexes.

Wrong index choices can hurt performance. Here is a checklist you can use to make the right call.

When You SHOULD Index

• Primary Keys & Unique Constraints: Most databases do this automatically, but it’s worth noting because these are your most frequent lookup points.
• Foreign Keys: You almost always want an index on columns used in JOIN clauses. Without them, the database has to perform a "Full Table Scan" to find matching rows.
• High Cardinality Columns: These are columns with many unique values (e.g., email, user_id, phone_number). Indexes work best when they can quickly narrow down the search to a tiny fraction of the table.
• Columns in WHERE Clauses: If your application constantly runs SELECT * FROM orders WHERE status = 'pending', that status column is a prime candidate for an index.
• Columns in ORDER BY or GROUP BY: Since an index is a sorted structure, it allows the database to skip the expensive step of sorting the data in memory.

When You SHOULD NOT Index

• Small Tables: If a table only has a few hundred rows, the database can scan the whole thing faster than it can load and read an index file.
• Low Cardinality Columns: Avoid indexing columns with very few unique values (e.g., gender, is_active, or country). The index won't help enough to justify the cost.
• Frequently Updated Tables: If you have a table that handles thousands of INSERTs or UPDATEs per second (like a log or a real-time sensor feed), every index will significantly slow down those writes.
• Extremely Wide Columns: Indexing a VARCHAR(MAX) or a TEXT field (like a blog post body) is inefficient. Use Full-Text Search indexes for those instead.
• Over-Indexing: Don’t index every single column “just in case.” This leads to Index Bloat, where the metadata and index files take up more disk space than the actual data.

Conclusion

Indexing is one of the most powerful tools for improving SQL query performance, but it’s also one of the most misunderstood. Today I explored what happens behind the scenes when an index is created, the different types of indexes available, and the trade‑offs that come with using them. The key takeaway is that indexes are carefully designed data structures that speed up reads while adding overhead to writes. Knowing when to apply them, which type to choose, and how they interact with queries is exactly what is needed.

Tomorrow, on Day 12, I’ll build on this foundation by exploring SQL Query Performance Optimisation more broadly.

Today’s Resources:

• Fundamentals of Data Engineering
• Ace Data Engineering Interview
• SQL Course on Udemy: SQL and PostgreSQL The Complete Developer’s Guide (IMO this is the best course to learn SQL in-depth)
• What is Index in SQL? (One of the best articles I have read)
• Introduction to Indexing in SQL