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?

Practice

1. What is the main benefit of using a composite index in a database?

easy

A. It encrypts the data for security.

B. It reduces the size of the database file.

C. It automatically backs up the database.

D. It speeds up queries filtering on multiple columns together.

Solution

1. Step 1: Understand what a composite index does

   A composite index is created on multiple columns to help the database find rows faster when queries filter on those columns together.

2. Step 2: Compare options to the definition

   Only It speeds up queries filtering on multiple columns together. correctly describes the benefit of speeding up queries using multiple columns. Other options describe unrelated features.

3. Final Answer:

   It speeds up queries filtering on multiple columns together. -> Option D

4. Quick Check:

   Composite index = speeds up multi-column queries [OK]

Hint: Composite index helps multi-column filters run faster [OK]

Common Mistakes:

• Thinking it reduces database size
• Confusing indexing with backup or encryption
• Assuming it speeds up single-column queries only

2. Which of the following is the correct syntax to create a composite index on columns last_name and first_name in a table employees?

easy

A. CREATE INDEX idx_name ON employees last_name, first_name;

B. CREATE INDEX idx_name ON employees (last_name, first_name);

C. CREATE INDEX idx_name (last_name, first_name) ON employees;

D. CREATE INDEX idx_name ON employees WHERE last_name, first_name;

Solution

1. Step 1: Recall correct CREATE INDEX syntax

   The correct syntax is: CREATE INDEX index_name ON table_name (column1, column2);

2. Step 2: Match options to syntax

   CREATE INDEX idx_name ON employees (last_name, first_name); matches the correct syntax exactly. Options A, C, and D have syntax errors or misplaced keywords.

3. Final Answer:

   CREATE INDEX idx_name ON employees (last_name, first_name); -> Option B

4. Quick Check:

   CREATE INDEX ... ON table (columns) [OK]

Hint: Use parentheses around columns after ON table [OK]

Common Mistakes:

• Omitting parentheses around columns
• Placing columns before ON keyword
• Using WHERE instead of column list

3. Given a composite index on (city, age) in a table users, which query will use the index efficiently?

medium

A. SELECT * FROM users WHERE age = 25 AND city = 'Boston';

B. SELECT * FROM users WHERE age > 30;

C. SELECT * FROM users WHERE city = 'Boston' AND age > 30;

D. SELECT * FROM users WHERE city = 'Boston' ORDER BY age DESC;

Solution

1. Step 1: Understand index column order usage

   A composite index on (city, age) can be used efficiently if the query filters on city first, then age.

2. Step 2: Analyze each query

   SELECT * FROM users WHERE city = 'Boston' AND age > 30; filters on city and age, matching index order. SELECT * FROM users WHERE age > 30; filters only on age (second column), so index is less useful. SELECT * FROM users WHERE age = 25 AND city = 'Boston'; filters age first, then city, which is less efficient. SELECT * FROM users WHERE city = 'Boston' ORDER BY age DESC; filters city but only orders by age, which may use index partially.

3. Final Answer:

   SELECT * FROM users WHERE city = 'Boston' AND age > 30; -> Option C

4. Quick Check:

   Index (city, age) best for city then age filters [OK]

Hint: Filter on first index column before others [OK]

Common Mistakes:

• Assuming index works well if filtering only second column
• Ignoring column order in composite index
• Thinking ORDER BY always uses index fully

4. You created a composite index on (department, salary) but your query filtering only on salary is slow. What is the likely cause?

medium

A. The index column order starts with department, so filtering only salary can't use it well.

B. The index is corrupted and needs rebuilding.

C. The salary column data type is incompatible with indexing.

D. The database does not support composite indexes.

Solution

1. Step 1: Recall how composite index column order affects usage

   Composite indexes work best when filtering starts with the first column. Filtering only on the second column (salary) won't use the index efficiently.

2. Step 2: Evaluate options

   The index column order starts with department, so filtering only salary can't use it well. correctly explains the cause. Options A, B, and D are unlikely or incorrect because the index exists and salary can be indexed normally.

3. Final Answer:

   The index column order starts with department, so filtering only salary can't use it well. -> Option A

4. Quick Check:

   Filter must start with first index column [OK]

Hint: Filter on first index column to use composite index [OK]

Common Mistakes:

• Assuming any column in index can be filtered efficiently alone
• Blaming index corruption without checking usage
• Ignoring column order importance

5. You have a table orders with columns customer_id, order_date, and status. You often run queries filtering by customer_id and sorting by order_date. Which composite index will optimize these queries best?

hard

A. CREATE INDEX idx_customer_date ON orders (customer_id, order_date);

B. CREATE INDEX idx_date_customer ON orders (order_date, customer_id);

C. CREATE INDEX idx_status_customer ON orders (status, customer_id);

D. CREATE INDEX idx_order ON orders (order_date);

Solution

1. Step 1: Identify query filter and sort columns

   Queries filter by customer_id and sort by order_date, so index should start with customer_id and include order_date next.

2. Step 2: Match index column order to query pattern

   CREATE INDEX idx_customer_date ON orders (customer_id, order_date); matches this order (customer_id, order_date), allowing efficient filtering and sorting. CREATE INDEX idx_date_customer ON orders (order_date, customer_id); reverses order, less efficient for filtering. Options A, B, and C do not match query needs.

3. Final Answer:

   CREATE INDEX idx_customer_date ON orders (customer_id, order_date); -> Option A

4. Quick Check:

   Index columns match filter then sort order [OK]

Hint: Index columns in filter then sort order [OK]

Common Mistakes:

• Reversing column order in composite index
• Indexing unrelated columns
• Using single-column index when composite needed