Why indexes matter in SQL - Performance Analysis

Time Complexity: Why indexes matter

O(n) without index, O(log n) with index

Understanding Time Complexity

We want to understand how using indexes changes the speed of searching data in a database.

How does the time to find data grow as the database gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL queries.

-- Query without index
SELECT * FROM employees WHERE last_name = 'Smith';

-- Create index on last_name
CREATE INDEX idx_last_name ON employees(last_name);

-- Query with index on last_name
SELECT * FROM employees WHERE last_name = 'Smith';
    

The first query searches without an index, scanning all rows. The second uses an index to find matches faster.

Identify Repeating Operations

Look at what repeats when searching for data.

• Primary operation: Checking each row's last_name in the table scan (no index) or searching the index tree.
• How many times: Without index, once per row (n times). With index, fewer steps following tree branches (logarithmic steps).

How Execution Grows With Input

As the table grows, the search time changes differently with and without an index.

Input Size (n)	Approx. Operations Without Index	Approx. Operations With Index
10	10 checks	About 3 steps
100	100 checks	About 7 steps
1000	1000 checks	About 10 steps

Pattern observation: Without index, operations grow directly with data size. With index, operations grow slowly even as data grows large.

Final Time Complexity

Time Complexity: O(n) without index, O(log n) with index

This means searching without an index takes longer as data grows, but with an index, search stays fast even for big data.

Common Mistake

[X] Wrong: "Adding an index always makes queries faster no matter what."

[OK] Correct: Indexes speed up searches but can slow down data changes like inserts or updates because the index must be updated too.

Interview Connect

Understanding how indexes affect search speed helps you explain how databases handle large data efficiently, a useful skill in many real projects.

Self-Check

"What if the index was on a column with many repeated values? How would that affect the time complexity?"

Practice

1. Why do indexes matter in a database?

easy

A. They increase the size of the database without any benefit.

B. They automatically fix data errors in tables.

C. They slow down all queries regardless of type.

D. They make searching data faster by creating a quick lookup structure.

Solution

1. Step 1: Understand what indexes do

   Indexes create a special structure that helps the database find data quickly, like a book's index.

2. Step 2: Identify the main benefit

   This structure speeds up searching and filtering operations, making queries faster.

3. Final Answer:

   They make searching data faster by creating a quick lookup structure. -> Option D

4. Quick Check:

   Indexes improve search speed = B [OK]

Hint: Indexes speed up searches by acting like a book's index [OK]

Common Mistakes:

• Thinking indexes slow down all queries
• Believing indexes fix data errors
• Assuming indexes only increase database size

2. Which SQL statement correctly creates an index on the column email in the users table?

easy

A. CREATE INDEX users ON idx_email(email);

B. MAKE INDEX idx_email ON users(email);

C. CREATE INDEX idx_email ON users(email);

D. INDEX CREATE idx_email ON users(email);

Solution

1. Step 1: Recall correct SQL syntax for creating an index

   The correct syntax is CREATE INDEX index_name ON table_name(column_name);.

2. Step 2: Match the syntax with options

   CREATE INDEX idx_email ON users(email); matches the correct syntax exactly, others have wrong keywords or order.

3. Final Answer:

   CREATE INDEX idx_email ON users(email); -> Option C

4. Quick Check:

   Correct CREATE INDEX syntax = C [OK]

Hint: Remember: CREATE INDEX index_name ON table(column) [OK]

Common Mistakes:

• Using wrong keywords like MAKE or INDEX CREATE
• Swapping table and index names
• Missing ON keyword

3. Given a table orders with 1 million rows and an index on customer_id, what is the expected result of this query?

SELECT * FROM orders WHERE customer_id = 123;

medium

A. The query will use the index to quickly find matching rows.

B. The query will return no rows because indexes hide data.

C. The query will fail because indexes cannot be used in WHERE clauses.

D. The query will scan all 1 million rows, taking a long time.

Solution

1. Step 1: Understand index usage in WHERE clause

   An index on customer_id helps the database quickly locate rows matching that value.

2. Step 2: Predict query behavior

   The database uses the index to avoid scanning all rows, speeding up the query.

3. Final Answer:

   The query will use the index to quickly find matching rows. -> Option A

4. Quick Check:

   Index speeds WHERE search = D [OK]

Hint: Indexes speed up WHERE filters on indexed columns [OK]

Common Mistakes:

• Thinking indexes cause full table scans
• Believing indexes prevent queries from running
• Assuming indexes hide data from results

4. You created an index on the username column, but your query is still slow:

SELECT * FROM users WHERE username LIKE '%admin%';

What is the most likely reason?

medium

A. The index was created on the wrong table.

B. Indexes cannot speed up LIKE queries with a leading wildcard '%'.

C. The query syntax is incorrect and causes errors.

D. Indexes always slow down SELECT queries.

Solution

1. Step 1: Analyze the LIKE pattern

   A LIKE pattern starting with '%' means the search can match anywhere in the string, preventing index use.

2. Step 2: Understand index limitations

   Indexes work best when the search starts from the beginning of the string, so leading wildcards disable index usage.

3. Final Answer:

   Indexes cannot speed up LIKE queries with a leading wildcard '%'. -> Option B

4. Quick Check:

   Leading '%' disables index use = A [OK]

Hint: Leading '%' in LIKE disables index use [OK]

Common Mistakes:

• Assuming all LIKE queries use indexes
• Thinking index on wrong table causes this
• Believing indexes always slow SELECT

5. You have a table sales with columns sale_id, product_id, and sale_date. You often run this query:

SELECT * FROM sales WHERE product_id = 101 AND sale_date >= '2024-01-01';

Which indexing strategy will likely improve query speed the most?

hard

A. Create a composite index on (product_id, sale_date).

B. Create separate indexes on product_id and sale_date.

C. Create a single index on sale_date only.

D. Do not create any index to keep inserts fast.

Solution

1. Step 1: Understand query filters

   The query filters by product_id and a range on sale_date.

2. Step 2: Choose best index type

   A composite index on both columns helps the database quickly find rows matching both conditions together.

3. Step 3: Compare with other options

   Separate indexes may help but are less efficient than a composite index for combined filters.

4. Final Answer:

   Create a composite index on (product_id, sale_date). -> Option A

5. Quick Check:

   Composite index matches multi-column filter = A [OK]

Hint: Use composite index for multi-column WHERE filters [OK]

Common Mistakes:

• Creating index on only one column
• Using separate indexes instead of composite
• Avoiding indexes to speed inserts without reason