Composite indexes in MySQL - Time & Space Complexity

Time Complexity: Composite indexes

O(log n)

Understanding Time Complexity

When we use composite indexes in a database, we want to know how they affect the speed of searching data.

We ask: How does the time to find data grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a composite index.

CREATE INDEX idx_name_age ON users(name, age);

SELECT * FROM users
WHERE name = 'Alice' AND age = 30;
    

This code creates a composite index on the columns name and age, then searches for users matching both.

Identify Repeating Operations

Look at what repeats when searching with this index.

• Primary operation: The database looks up entries in the index tree for name and then age.
• How many times: It follows a path down the index tree, which grows with the number of unique name and age pairs.

How Execution Grows With Input

As the table grows, the index tree grows slowly, so searching stays fast.

Input Size (n)	Approx. Operations
10	About 3 steps
100	About 5 steps
1000	About 7 steps

Pattern observation: The number of steps grows slowly, not directly with the number of rows.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the table gets bigger, making lookups efficient.

Common Mistake

[X] Wrong: "Adding more columns to the composite index always makes searches faster."

[OK] Correct: Adding columns that are not used in the query or in the wrong order can make the index less useful or slower.

Interview Connect

Understanding how composite indexes affect search speed shows you know how databases handle data efficiently, a useful skill for many projects.

Self-Check

What if we changed the query to search only by age without name? How would the time complexity change?

Practice

1. What is the main purpose of a composite index in MySQL?

easy

A. To create a backup of the database automatically

B. To speed up queries that filter or sort by multiple columns together

C. To store data in multiple tables simultaneously

D. To encrypt data in multiple columns

Solution

1. Step 1: Understand what an index does

   An index helps MySQL find data faster by organizing it for quick lookup.

2. Step 2: Understand composite index purpose

   A composite index uses multiple columns together to speed up queries that filter or sort by those columns combined.

3. Final Answer:

   To speed up queries that filter or sort by multiple columns together -> Option B

4. Quick Check:

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

Hint: Composite indexes speed up multi-column filters and sorts [OK]

Common Mistakes:

• Thinking composite indexes store data
• Confusing indexes with backups
• Assuming encryption is related to indexes

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

easy

A. CREATE INDEX idx_name ON users (first_name, last_name);

B. CREATE INDEX idx_name ON users first_name, last_name;

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

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

Solution

1. Step 1: Recall correct CREATE INDEX syntax

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

2. Step 2: Match syntax with options

   CREATE INDEX idx_name ON users (first_name, last_name); matches the correct syntax with parentheses around columns and ON keyword before table name.

3. Final Answer:

   CREATE INDEX idx_name ON users (first_name, last_name); -> Option A

4. Quick Check:

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

Hint: Use parentheses around columns after ON table_name [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 people, which query will use the index efficiently?

medium

A. SELECT * FROM people WHERE city = 'Paris' AND age = 30;

B. SELECT * FROM people WHERE age = 30;

C. SELECT * FROM people WHERE age BETWEEN 20 AND 40;

D. SELECT * FROM people WHERE city LIKE '%Paris%' ORDER BY age DESC;

Solution

1. Step 1: Understand composite index column order

   The index is on (city, age), so queries filtering city first then age use it best.

2. Step 2: Analyze queries for index usage

   SELECT * FROM people WHERE city LIKE '%Paris%' ORDER BY age DESC;: LIKE '%Paris%' prevents index use due to leading wildcard. SELECT * FROM people WHERE age = 30;: filters only age (second column), skips prefix. SELECT * FROM people WHERE age BETWEEN 20 AND 40;: range on age only, cannot use prefix. SELECT * FROM people WHERE city = 'Paris' AND age = 30;: city then age equality matches prefix perfectly.

3. Final Answer:

   SELECT * FROM people WHERE city = 'Paris' AND age = 30; -> Option A

4. Quick Check:

   Filter starts with first index column = SELECT * FROM people WHERE city = 'Paris' AND age = 30; [OK]

Hint: Filter starting with first index column uses composite index best [OK]

Common Mistakes:

• Assuming any column filter uses composite index fully
• Ignoring column order in composite index
• Thinking ORDER BY always uses composite index

4. You created a composite index on (department, salary) but your query SELECT * FROM employees WHERE salary > 50000; is slow. What is the likely problem?

medium

A. The table has no data

B. The index syntax was incorrect

C. Composite indexes cannot be used with numeric columns

D. The query does not filter on the first column of the composite index

Solution

1. Step 1: Recall composite index usage rules

   Composite indexes work best when queries filter starting from the first indexed column.

2. Step 2: Analyze the query and index

   The index is on (department, salary), but query filters only salary (second column), so index is not used efficiently, causing slowness.

3. Final Answer:

   The query does not filter on the first column of the composite index -> Option D

4. Quick Check:

   Filter must start with first index column [OK]

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

Common Mistakes:

• Assuming any column filter uses composite index
• Blaming syntax without checking query
• Thinking numeric columns can't be indexed

5. You have a table orders with columns customer_id, order_date, and status. You often run this query:
SELECT * FROM orders WHERE customer_id = 123 AND status = 'shipped' ORDER BY order_date DESC;
Which composite index will optimize this query best?

hard

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

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

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

D. CREATE INDEX idx_customer_order_date ON orders (customer_id, order_date);

Solution

1. Step 1: Identify query filter and order columns

   The query filters by customer_id and status, then orders by order_date descending.

2. Step 2: Choose index column order for best performance

   Index should start with columns used in WHERE filters in order: customer_id, then status, then order_date for ORDER BY.

3. Step 3: Match index options

   CREATE INDEX idx_customer_status_date ON orders (customer_id, status, order_date); matches this order exactly, so it optimizes filtering and ordering best.

4. Final Answer:

   CREATE INDEX idx_customer_status_date ON orders (customer_id, status, order_date); -> Option C

5. Quick Check:

   Index columns match WHERE then ORDER BY order [OK]

Hint: Index columns order: filter columns first, then order column [OK]

Common Mistakes:

• Putting ORDER BY column before filter columns
• Ignoring filter columns order
• Creating index missing important filter column