Primary vs secondary indexes in DBMS Theory - Performance Comparison

Time Complexity: Primary vs secondary indexes

O(log n)

Understanding Time Complexity

Indexes help databases find data faster. We want to understand how using primary or secondary indexes affects the time it takes to search.

How does the choice of index change the work done as data grows?

Scenario Under Consideration

Analyze the time complexity of searching with primary and secondary indexes.

-- Searching with Primary Index
SELECT * FROM Employees WHERE EmployeeID = 12345;

-- Searching with Secondary Index
SELECT * FROM Employees WHERE Department = 'Sales';
    

The first query uses a primary index on EmployeeID, the second uses a secondary index on Department.

Identify Repeating Operations

Look at what repeats when searching:

• Primary index search: Uses a tree or sorted structure to find one record quickly.
• Secondary index search: Finds all matching records, may need extra steps to get full data.
• Dominant operation: Number of lookups in the index and data retrieval steps.

How Execution Grows With Input

As the number of records (n) grows, the work changes:

Input Size (n)	Primary Index Lookups	Secondary Index Lookups
10	About 3 steps	About 3 steps + fetching multiple rows
100	About 7 steps	About 7 steps + fetching multiple rows
1000	About 10 steps	About 10 steps + fetching multiple rows

Primary index search grows slowly with data size. Secondary index search also grows slowly for lookup but may fetch many rows, increasing work.

Final Time Complexity

Time Complexity: O(log n) for primary index search, O(log n + k) for secondary index search where k is matching rows.

This means finding one record by primary index is fast and grows slowly, but secondary index search can take longer if many records match.

Common Mistake

[X] Wrong: "Secondary indexes are always as fast as primary indexes."

[OK] Correct: Secondary indexes may return many records, so fetching all data can take more time than a single primary key lookup.

Interview Connect

Understanding how indexes affect search speed shows you know how databases handle data efficiently. This helps you explain choices in real projects clearly.

Self-Check

"What if the secondary index is on a unique column? How would the time complexity change?"

Practice

1. What is the main purpose of a primary index in a database?

easy

A. To provide unique and fast access to records using the primary key

B. To speed up searches on non-key columns

C. To store duplicate values for faster retrieval

D. To backup the database automatically

Solution

1. Step 1: Understand the role of primary index

   A primary index is created on the primary key of a table, which uniquely identifies each record.

2. Step 2: Identify its main function

   It ensures fast and unique access to records based on the primary key values.

3. Final Answer:

   To provide unique and fast access to records using the primary key -> Option A

4. Quick Check:

   Primary index = unique fast access [OK]

Hint: Primary index = unique key fast access [OK]

Common Mistakes:

• Confusing primary index with secondary index
• Thinking primary index allows duplicates
• Assuming primary index is for backup

2. Which of the following is the correct statement about creating a secondary index in SQL?

easy

A. CREATE INDEX idx_name ON table(column);

B. CREATE UNIQUE INDEX idx_name ON table(column);

C. CREATE PRIMARY INDEX idx_name ON table(column);

D. CREATE SECONDARY INDEX idx_name ON table(column);

Solution

1. Step 1: Recall SQL syntax for indexes

   Secondary indexes are created using the standard CREATE INDEX statement without the PRIMARY keyword.

2. Step 2: Identify the correct syntax

   CREATE INDEX idx_name ON table(column); uses the correct syntax: CREATE INDEX idx_name ON table(column);

3. Final Answer:

   CREATE INDEX idx_name ON table(column); -> Option A

4. Quick Check:

   Secondary index syntax = CREATE INDEX [OK]

Hint: Secondary index uses CREATE INDEX without PRIMARY [OK]

Common Mistakes:

• Using CREATE SECONDARY INDEX which is invalid
• Confusing with CREATE PRIMARY INDEX syntax
• Using UNIQUE keyword incorrectly for secondary index

3. Consider a table Employees(emp_id, name, department) where emp_id is the primary key. Which index type would speed up a query filtering by department?

medium

A. Primary index on department

B. Primary index on emp_id

C. Secondary index on department

D. No index needed

Solution

1. Step 1: Identify the primary key and its index

   The primary key is emp_id, so the primary index is on emp_id.

2. Step 2: Determine which index helps filter by department

   Since department is not the primary key, a secondary index on department speeds up queries filtering by it.

3. Final Answer:

   Secondary index on department -> Option C

4. Quick Check:

   Filter by non-key column = secondary index [OK]

Hint: Use secondary index for non-primary key columns [OK]

Common Mistakes:

• Assuming primary index helps filter by any column
• Trying to create primary index on non-key column
• Ignoring the benefit of secondary indexes

4. A developer created a secondary index on a column that contains many duplicate values. What is the likely problem?

medium

A. The database will reject the index creation

B. The primary index will be corrupted

C. The secondary index will enforce uniqueness

D. The secondary index will be inefficient due to low uniqueness

Solution

1. Step 1: Understand secondary index behavior with duplicates

   Secondary indexes can be created on columns with duplicates but may become less efficient because many records share the same key.

2. Step 2: Identify the impact on performance

   Low uniqueness means the index has many entries pointing to multiple rows, slowing down search performance.

3. Final Answer:

   The secondary index will be inefficient due to low uniqueness -> Option D

4. Quick Check:

   Duplicates in secondary index = inefficiency [OK]

Hint: Secondary index on duplicates slows searches [OK]

Common Mistakes:

• Thinking secondary index enforces uniqueness
• Believing primary index gets corrupted
• Expecting index creation to fail

5. You have a large table with a primary index on customer_id and a secondary index on city. You want to optimize queries filtering by both customer_id and city. What is the best indexing strategy?

hard

A. Drop the secondary index and rely only on primary index

B. Create a composite index on (customer_id, city)

C. Create a secondary index on customer_id only

D. Create two separate secondary indexes on customer_id and city

Solution

1. Step 1: Analyze current indexes and query filters

   Primary index exists on customer_id, secondary index on city. Queries filter by both columns.

2. Step 2: Understand composite index benefits

   A composite index on (customer_id, city) allows efficient filtering on both columns together, improving query speed.

3. Step 3: Evaluate other options

   Dropping indexes or creating separate secondary indexes won't optimize combined filtering as well as a composite index.

4. Final Answer:

   Create a composite index on (customer_id, city) -> Option B

5. Quick Check:

   Combined filter = composite index [OK]

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

Common Mistakes:

• Dropping useful indexes
• Creating redundant secondary indexes
• Ignoring composite index advantages