Indexing materialized views in PostgreSQL - Time & Space Complexity

Time Complexity: Indexing materialized views

O(log n)

Understanding Time Complexity

When we add indexes to materialized views, we want to know how it affects the speed of queries.

We ask: How does the time to find data change as the view grows?

Scenario Under Consideration

Analyze the time complexity of creating and using an index on a materialized view.

CREATE MATERIALIZED VIEW sales_summary AS
  SELECT product_id, SUM(quantity) AS total_quantity
  FROM sales
  GROUP BY product_id;

CREATE INDEX idx_sales_summary_product ON sales_summary(product_id);

SELECT * FROM sales_summary WHERE product_id = 123;
    

This code creates a summary view, adds an index on product_id, and queries by product_id.

Identify Repeating Operations

Look for repeated steps that affect time.

• Primary operation: Searching the index for matching product_id.
• How many times: Depends on the number of lookups; each lookup uses the index once.

How Execution Grows With Input

As the materialized view grows, the index helps keep search fast.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find data
100	About 7 steps to find data
1000	About 10 steps to find data

Pattern observation: The number of steps grows slowly as data grows, not one-by-one.

Final Time Complexity

Time Complexity: O(log n)

This means searching with the index takes a small number of steps even if the data grows large.

Common Mistake

[X] Wrong: "Adding an index makes queries instantly fast no matter what."

[OK] Correct: Indexes speed up searches but building and maintaining them takes time, and some queries may not use the index efficiently.

Interview Connect

Understanding how indexes affect query speed on materialized views shows you know how databases handle large data efficiently.

Self-Check

"What if we added a second index on total_quantity? How would that change the time complexity for queries filtering by total_quantity?"