Why indexing strategy matters in PostgreSQL - Performance Analysis

Time Complexity: Why indexing strategy matters

O(log n + k)

Understanding Time Complexity

When we use indexes in a database, it changes how fast queries run.

We want to see how the choice of indexing affects the time a query takes as data grows.

Scenario Under Consideration

Analyze the time complexity of the following query using an index.

SELECT * FROM employees
WHERE department_id = 5;
    

This query finds all employees in one department using an index on department_id.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the index tree to find matching rows.
• How many times: The search goes down the index levels, which is a few steps regardless of total rows.

How Execution Grows With Input

As the table grows, the index search stays quick, but scanning all rows without an index gets slower.

Input Size (n)	Approx. Operations
10	About 3 steps in index + few rows
100	About 4 steps in index + few rows
1000	About 5 steps in index + few rows

Pattern observation: The index search grows very slowly, much better than checking every row.

Final Time Complexity

Time Complexity: O(log n + k)

This means the search time grows slowly with data size, plus time to return matching rows.

Common Mistake

[X] Wrong: "Adding an index always makes queries instantly fast regardless of data or query."

[OK] Correct: Some queries don't use indexes well, and indexes add overhead when writing data.

Interview Connect

Understanding how indexes affect query speed shows you know how databases handle data efficiently.

Self-Check

What if we changed the index to cover multiple columns? How would the time complexity change?

Practice

1. Why is having a good indexing strategy important in PostgreSQL?

easy

A. It helps the database find data faster, improving query speed.

B. It increases the size of the database without benefits.

C. It makes the database ignore queries.

D. It automatically fixes data errors.

Solution

1. Step 1: Understand what indexes do

   Indexes act like shortcuts to quickly locate data without scanning the whole table.

2. Step 2: Connect indexing to query speed

   Good indexes reduce the time to find data, making queries faster and more efficient.

3. Final Answer:

   It helps the database find data faster, improving query speed. -> Option A

4. Quick Check:

   Index = Faster data search [OK]

Hint: Indexes speed up searches by acting like shortcuts [OK]

Common Mistakes:

• Thinking indexes slow down queries
• Believing indexes fix data errors
• Assuming indexes increase query ignoring

2. Which of the following is the correct syntax to create a basic index on column email in PostgreSQL?

easy

A. CREATE INDEX ON users email;

B. CREATE INDEX idx_email ON users (email);

C. MAKE INDEX idx_email ON users email;

D. INDEX CREATE idx_email users (email);

Solution

1. Step 1: Recall PostgreSQL index creation syntax

   The correct syntax starts with CREATE INDEX, followed by index name, ON table name, and column list in parentheses.

2. Step 2: Match syntax to options

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

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Omitting parentheses around column name
• Using wrong keywords like MAKE or INDEX CREATE
• Missing ON keyword before table name

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

SELECT * FROM orders WHERE customer_id = 12345;

medium

A. The query will return no rows because indexes filter data.

B. The query will scan all rows, ignoring the index.

C. The query will fail due to missing index.

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

Solution

1. Step 1: Understand index usage in queries

   When a column is indexed, PostgreSQL uses the index to find matching rows quickly instead of scanning the whole table.

2. Step 2: Apply to the given query

   The query filters by customer_id, which is indexed, so the index helps find rows efficiently.

3. Final Answer:

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

4. Quick Check:

   Indexed column = faster search [OK]

Hint: Queries on indexed columns use indexes for speed [OK]

Common Mistakes:

• Thinking index is ignored automatically
• Assuming query fails without explicit index hint
• Believing indexes filter out rows

4. You created multiple indexes on a table, but your INSERT queries became slower. What is the most likely cause?

medium

A. Indexes slow down data changes because they must update on each insert.

B. Indexes cause syntax errors during INSERT.

C. Indexes delete rows automatically on insert.

D. Indexes prevent data from being inserted.

Solution

1. Step 1: Understand index impact on data modification

   Indexes must be updated every time data changes, so more indexes mean more work during INSERT, UPDATE, DELETE.

2. Step 2: Connect to slower INSERT queries

   Because indexes update on each insert, having many indexes slows down insert speed.

3. Final Answer:

   Indexes slow down data changes because they must update on each insert. -> Option A

4. Quick Check:

   More indexes = slower inserts [OK]

Hint: More indexes slow inserts due to update overhead [OK]

Common Mistakes:

• Thinking indexes cause syntax errors
• Believing indexes block inserts
• Assuming indexes delete data automatically

5. You have a table products with columns id, category, and price. You often run this query:

SELECT * FROM products WHERE category = 'books' AND price < 20;

Which indexing strategy will most improve query speed without slowing inserts too much?

hard

A. Create no indexes to keep inserts fast.

B. Create separate indexes on category and price.

C. Create a composite index on (category, price).

D. Create an index only on price.

Solution

1. Step 1: Analyze query filter conditions

   The query filters on both category and price together, so a composite index on both columns helps the database find matching rows efficiently.

2. Step 2: Compare indexing options

   Separate indexes may be less efficient because PostgreSQL might not combine them well; no index slows queries; indexing only price misses category filtering.

3. Final Answer:

   Create a composite index on (category, price). -> Option C

4. Quick Check:

   Composite index matches multi-column filters [OK]

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

Common Mistakes:

• Creating separate indexes expecting same speed
• Indexing only one column in multi-filter queries
• Avoiding indexes to keep inserts fast but hurting queries