Composite index and column order in SQL - Time & Space Complexity

Time Complexity: Composite index and column order

O(log n)

Understanding Time Complexity

When using composite indexes in databases, the order of columns affects how fast queries run.

We want to understand how the query speed changes as data grows, depending on column order.

Scenario Under Consideration

Analyze the time complexity of this query using a composite index on (last_name, first_name):

SELECT * FROM employees
WHERE last_name = 'Smith' AND first_name = 'John';
    

This query looks up employees by last and first name using a composite index.

Identify Repeating Operations

Look at what repeats when searching with the composite index.

• Primary operation: Searching the index tree by matching last_name first, then first_name.
• How many times: The database narrows down matches step-by-step, scanning fewer rows as it goes.

How Execution Grows With Input

As the number of employees grows, the search stays fast because the index narrows results quickly.

Input Size (n)	Approx. Operations
10	About 3 steps to find matching names
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly, not directly with total data size, because the index guides the search.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as data grows, thanks to the index structure.

Common Mistake

[X] Wrong: "Changing the order of columns in the composite index does not affect query speed."

[OK] Correct: The database uses the first column to quickly narrow results; if the query filters on the second column first, the index is less effective.

Interview Connect

Understanding how composite indexes work and how column order affects query speed shows you know how databases handle large data efficiently.

Self-Check

What if we reversed the column order in the composite index to (first_name, last_name)? How would that change the time complexity for the same query?