BRIN index for large sequential data in PostgreSQL - Time & Space Complexity

Time Complexity: BRIN index for large sequential data

O(n / block_size)

Understanding Time Complexity

We want to understand how the time to search data changes when using a BRIN index on large, ordered data.

How does the search speed grow as the data size grows?

Scenario Under Consideration

Analyze the time complexity of this BRIN index query.

CREATE TABLE measurements (
  id serial PRIMARY KEY,
  time_stamp timestamp NOT NULL,
  value numeric
);

CREATE INDEX brin_time_idx ON measurements USING brin (time_stamp);

SELECT * FROM measurements WHERE time_stamp BETWEEN '2023-01-01' AND '2023-01-31';
    

This code creates a BRIN index on a timestamp column and queries a date range.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Scanning index summary pages that cover ranges of rows.
• How many times: Number of index pages scanned grows with the number of data pages, but fewer than scanning all rows.

How Execution Grows With Input

As the table grows, the BRIN index scans fewer pages than the total rows.

Input Size (n rows)	Approx. Index Pages Scanned
10,000	~100 pages
100,000	~1,000 pages
1,000,000	~10,000 pages

Pattern observation: The number of pages scanned grows roughly proportional to the number of data pages, which is much smaller than total rows.

Final Time Complexity

Time Complexity: O(n / block_size)

This means the search time grows roughly with the number of data blocks, not the total rows, making it efficient for large sequential data.

Common Mistake

[X] Wrong: "BRIN indexes scan every row like a normal index."

[OK] Correct: BRIN indexes summarize ranges of rows, so they scan fewer pages, not every row, making them faster for big, ordered data.

Interview Connect

Knowing how BRIN indexes scale helps you explain efficient ways to handle huge time-series or sequential data in real projects.

Self-Check

"What if the data was not stored in order by time_stamp? How would the time complexity of using a BRIN index change?"