Covering indexes with INCLUDE in PostgreSQL - Time & Space Complexity

Time Complexity: Covering indexes with INCLUDE

O(log n + k)

Understanding Time Complexity

We want to understand how using covering indexes with INCLUDE affects query speed as data grows.

How does the query time change when the index holds extra columns to avoid looking up the main table?

Scenario Under Consideration

Analyze the time complexity of this index and query.

CREATE INDEX idx_orders_customer_date ON orders (customer_id) INCLUDE (order_date);

SELECT order_date FROM orders WHERE customer_id = 123;
    

This creates an index on customer_id and stores order_date inside it to speed up queries that select order_date by customer_id.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the index tree for matching customer_id entries.
• How many times: Once per query, but may scan multiple matching entries depending on how many orders a customer has.

How Execution Grows With Input

As the number of orders grows, the index helps find matching rows faster without scanning the whole table.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find matches
100	About 5-6 steps to find matches
1000	About 7-8 steps to find matches

Pattern observation: The number of steps grows slowly, not directly with total rows, because the index tree is balanced.

Final Time Complexity

Time Complexity: O(log n + k)

This means the query time grows slowly with total rows (log n) plus the number of matching rows (k) to read.

Common Mistake

[X] Wrong: "Adding INCLUDE columns makes the index size and search time grow a lot."

[OK] Correct: INCLUDE columns add data only to leaf nodes, so the search steps stay about the same; it just avoids extra table lookups.

Interview Connect

Understanding how covering indexes affect query speed shows you know how databases keep queries fast as data grows. This skill helps you design efficient data access.

Self-Check

What if we removed the INCLUDE clause and selected order_date in the query? How would the time complexity change?

Practice

1. What is the main purpose of using INCLUDE in a PostgreSQL index?

easy

A. To change the data type of indexed columns

B. To create a unique constraint on the indexed columns

C. To delete columns from the index

D. To add extra columns to the index for faster SELECT queries without searching on them

Solution

1. Step 1: Understand the role of INCLUDE in indexes

   INCLUDE adds extra columns to the index that are not used for searching but can be returned in queries.

2. Step 2: Identify the benefit of these extra columns

   These extra columns help avoid reading the main table, speeding up SELECT queries that need those columns.

3. Final Answer:

   To add extra columns to the index for faster SELECT queries without searching on them -> Option D

4. Quick Check:

   INCLUDE adds columns for SELECT speed [OK]

Hint: INCLUDE adds columns to speed SELECT, not for searching [OK]

Common Mistakes:

• Thinking INCLUDE creates unique constraints
• Believing INCLUDE removes columns
• Assuming INCLUDE changes data types

2. Which of the following is the correct syntax to create a covering index on table users for column email and include last_login?

easy

A. CREATE INDEX idx_email ON users(email) INCLUDE (last_login);

B. CREATE INDEX idx_email ON users(email, last_login);

C. CREATE INDEX idx_email ON users INCLUDE (email, last_login);

D. CREATE INDEX idx_email ON users(email) WITH (last_login);

Solution

1. Step 1: Recall the syntax for INCLUDE in PostgreSQL indexes

   The correct syntax is to specify indexed columns first, then use INCLUDE for extra columns.

2. Step 2: Match the syntax to the options

   CREATE INDEX idx_email ON users(email) INCLUDE (last_login); correctly uses CREATE INDEX idx_email ON users(email) INCLUDE (last_login);

3. Final Answer:

   CREATE INDEX idx_email ON users(email) INCLUDE (last_login); -> Option A

4. Quick Check:

   Indexed columns first, INCLUDE for extras [OK]

Hint: Indexed columns before INCLUDE clause [OK]

Common Mistakes:

• Putting all columns inside parentheses without INCLUDE
• Using WITH instead of INCLUDE
• Including columns in wrong order

3. Given the index CREATE INDEX idx_name ON employees(last_name) INCLUDE (first_name, department);, what will the query SELECT last_name, first_name FROM employees WHERE last_name = 'Smith'; most likely do?

medium

A. Use the index but still access the table to get first_name

B. Use the index to find rows and return both last_name and first_name without accessing the table

C. Scan the whole table because first_name is not indexed

D. Return an error because first_name is not indexed

Solution

1. Step 1: Understand what INCLUDE columns do in the index

   INCLUDE columns are stored in the index to avoid accessing the main table for those columns.

2. Step 2: Analyze the query and index usage

   The query filters on last_name (indexed) and selects first_name (included). The index covers both, so no table access needed.

3. Final Answer:

   Use the index to find rows and return both last_name and first_name without accessing the table -> Option B

4. Quick Check:

   INCLUDE columns avoid table access [OK]

Hint: INCLUDE columns can be returned without table access [OK]

Common Mistakes:

• Assuming INCLUDE columns are not stored in the index
• Thinking table scan is always needed
• Confusing INCLUDE with indexed columns

4. You wrote this index: CREATE INDEX idx_order ON orders(order_date) INCLUDE (customer_id; but get a syntax error. What is the problem?

medium

A. INCLUDE cannot be used with order_date

B. You must list customer_id before order_date

C. Missing closing parenthesis after customer_id

D. INCLUDE requires at least two columns

Solution

1. Step 1: Check the syntax of the CREATE INDEX statement

   The statement has an opening parenthesis after INCLUDE but no closing parenthesis.

2. Step 2: Identify the syntax error

   Missing closing parenthesis causes the syntax error.

3. Final Answer:

   Missing closing parenthesis after customer_id -> Option C

4. Quick Check:

   Parentheses must be balanced [OK]

Hint: Check parentheses carefully in INCLUDE clause [OK]

Common Mistakes:

• Forgetting closing parenthesis
• Misordering columns
• Thinking INCLUDE needs multiple columns

5. You want to speed up this query: SELECT product_id, price, stock FROM products WHERE product_id = 123; by creating a covering index. Which index is best?

hard

A. CREATE INDEX idx_product ON products(product_id) INCLUDE (price, stock);

B. CREATE INDEX idx_product ON products(price, stock) INCLUDE (product_id);

C. CREATE INDEX idx_product ON products(product_id, price, stock);

D. CREATE INDEX idx_product ON products(product_id);

Solution

1. Step 1: Identify the filtering and selected columns in the query

   The query filters on product_id and selects price and stock.

2. Step 2: Choose an index that filters on product_id and includes price and stock

   CREATE INDEX idx_product ON products(product_id) INCLUDE (price, stock); indexes product_id and includes price and stock, covering the query efficiently.

3. Step 3: Compare other options

   CREATE INDEX idx_product ON products(price, stock) INCLUDE (product_id); indexes price and stock, not filtering column; CREATE INDEX idx_product ON products(product_id, price, stock); indexes all columns but includes unnecessary columns in index key; CREATE INDEX idx_product ON products(product_id); lacks included columns, so table access needed.

4. Final Answer:

   CREATE INDEX idx_product ON products(product_id) INCLUDE (price, stock); -> Option A

5. Quick Check:

   Filter column indexed, others included [OK]

Hint: Index filter column, INCLUDE others for covering [OK]

Common Mistakes:

• Including filter columns instead of indexing them
• Indexing all columns as keys unnecessarily
• Not including selected columns causing table access