Covering index concept in SQL - Time & Space Complexity

Time Complexity: Covering index concept

O(n)

Understanding Time Complexity

When we use a covering index in a database query, it can change how fast the query runs.

We want to see how the number of steps grows as the data gets bigger when using a covering index.

Scenario Under Consideration

Analyze the time complexity of this SQL query using a covering index.

SELECT order_id, order_date, customer_id
FROM orders
WHERE customer_id = 12345;
-- Assume a covering index exists on (customer_id, order_id, order_date)

This query fetches orders for one customer using a covering index that includes all needed columns.

Identify Repeating Operations

Look for repeated steps in the query execution.

• Primary operation: Scanning the index entries for the matching customer_id.
• How many times: Once for each matching order for that customer.

How Execution Grows With Input

As the number of orders for the customer grows, the work grows too.

Input Size (n)	Approx. Operations
10	About 10 index entries scanned
100	About 100 index entries scanned
1000	About 1000 index entries scanned

Pattern observation: The work grows directly with the number of matching rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line with the number of matching orders.

Common Mistake

[X] Wrong: "Using a covering index makes the query run in constant time no matter how many rows match."

[OK] Correct: Even with a covering index, the database must still look at each matching row, so time grows with the number of matches.

Interview Connect

Understanding how covering indexes affect query speed helps you explain real database performance in simple terms.

Self-Check

What if the query requested columns not included in the covering index? How would the time complexity change?

Practice

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

easy

A. It contains all columns needed by a query, avoiding table lookups.

B. It compresses data to save disk space.

C. It automatically backs up the database.

D. It encrypts data for security.

Solution

1. Step 1: Understand what a covering index stores

   A covering index includes all columns that a query needs, so the database can get results from the index alone.

2. Step 2: Identify the benefit of avoiding table lookups

   By not accessing the main table, queries run faster because less data is read and fewer disk operations occur.

3. Final Answer:

   It contains all columns needed by a query, avoiding table lookups. -> Option A

4. Quick Check:

   Covering index = all needed columns [OK]

Hint: Covering index has all query columns, no table needed [OK]

Common Mistakes:

• Thinking it compresses data
• Confusing with backup or encryption
• Assuming it stores only keys

2. Which of the following is the correct syntax to create a covering index on columns name and age in a table users?

easy

A. CREATE INDEX idx_users_name ON users(name, age);

B. CREATE INDEX idx_users_name_age ON users(name, age);

C. CREATE INDEX idx_users ON users WHERE name, age;

D. CREATE INDEX idx_users_name_age ON users USING name, age;

Solution

1. Step 1: Recall the syntax for creating an index on multiple columns

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

2. Step 2: Identify the option matching this syntax with both columns

   CREATE INDEX idx_users_name_age ON users(name, age); correctly names the index and lists both columns in parentheses separated by a comma.

3. Final Answer:

   CREATE INDEX idx_users_name_age ON users(name, age); -> Option B

4. Quick Check:

   CREATE INDEX with columns in parentheses [OK]

Hint: Use parentheses with columns separated by commas [OK]

Common Mistakes:

• Using WHERE instead of column list
• Missing parentheses around columns
• Incorrect keyword usage like USING

3. Given the table orders(order_id, customer_id, order_date, total) and an index on (customer_id, order_date, total), what will the query below use to speed up retrieval?

SELECT customer_id, order_date, total FROM orders WHERE customer_id = 5;

medium

A. The index covers all needed columns, so no table access is needed.

B. The index is ignored because it lacks order_id.

C. The query will scan the entire table ignoring the index.

D. The index is used only for filtering, then table rows are accessed.

Solution

1. Step 1: Check if the index includes all columns in SELECT and WHERE

   The index has customer_id, order_date, and total, which are all requested in SELECT and filtered in WHERE.

2. Step 2: Understand covering index usage

   Since the index has all needed columns, the database can answer the query using only the index without accessing the main table.

3. Final Answer:

   The index covers all needed columns, so no table access is needed. -> Option A

4. Quick Check:

   Index covers SELECT and WHERE columns [OK]

Hint: If index has all SELECT columns, no table needed [OK]

Common Mistakes:

• Thinking order_id is required in SELECT
• Assuming index is ignored if not all table columns included
• Believing table scan always happens

4. You created an index on (product_id, price) but your query SELECT product_id, price, stock FROM products WHERE product_id = 10; is slow. What is the likely reason?

medium

A. The index columns are in wrong order.

B. The index should be on stock only.

C. The query syntax is incorrect.

D. The index is not covering because stock is missing, causing table lookups.

Solution

1. Step 1: Identify columns used in SELECT and index

   The query selects product_id, price, and stock, but the index only has product_id and price.

2. Step 2: Understand why missing columns slow query

   Because stock is missing from the index, the database must access the main table to get stock values, slowing the query.

3. Final Answer:

   The index is not covering because stock is missing, causing table lookups. -> Option D

4. Quick Check:

   Missing SELECT column in index causes table access [OK]

Hint: Covering index must include all SELECT columns [OK]

Common Mistakes:

• Thinking column order affects covering
• Blaming query syntax without error
• Assuming index on stock only helps

5. You want to optimize this query:

SELECT user_id, last_login, status FROM users WHERE status = 'active' AND last_login > '2024-01-01';

Which covering index will best speed up this query?

hard

A. CREATE INDEX idx_users_userid ON users(user_id);

B. CREATE INDEX idx_users_login_status ON users(last_login, status);

C. CREATE INDEX idx_users_status_login ON users(status, last_login, user_id);

D. CREATE INDEX idx_users_status ON users(status);

Solution

1. Step 1: Identify columns used in WHERE and SELECT

   The query filters by status and last_login, and selects user_id, last_login, and status.

2. Step 2: Choose index covering all these columns

   CREATE INDEX idx_users_status_login ON users(status, last_login, user_id); includes status, last_login, and user_id, covering all needed columns for filtering and selection.

3. Step 3: Confirm column order for filtering

   Status is first in the index, matching the equality filter, then last_login for range filter, optimizing index usage.

4. Final Answer:

   CREATE INDEX idx_users_status_login ON users(status, last_login, user_id); -> Option C

5. Quick Check:

   Covering index with WHERE and SELECT columns in filter order [OK]

Hint: Include all WHERE and SELECT columns in index, filter columns first [OK]

Common Mistakes:

• Ignoring SELECT columns in index
• Wrong column order reducing index efficiency
• Creating index on only one filter column