Postgres Query Complexity when using hash index and b+ tree index

Question

My table (user_tran) has 3 fields "user_id", "transaction_id", "time_stamp"

I hash index user_id and transaction_id (as I need to do the exact match) and b+ tree index on time_stamp

The query is

select user_id from user_tran where transaction_id = 1 and time_stamp > now() - 3 days; 

select transaction_id from user_tran where user_id = 1 and time_stamp > now() - 3 days;

Does anyone know what is the complexity of this query? I know if we just filter by hash index column, it would be o(1) and b+ tree gives o(lgn). But what about combining them together?

Would that be o(lgn + 1)?

Also how would the table stored under the hood. Will the DBMS maintain 3 indexes (2 hash and 1 b+ tree) at the same time?

Googled around a little bit, but didn't find the answer.

Laurenz Albe · Accepted Answer · 2018-05-09 20:29:11Z

1

With three indexes like that, the complexity for a query that uses the indexes would be O(n) because the only way to combine multiple indexes is a bitmap and. Creating the bitmap requires reading the whole index, which is O(n).

So, unless none of the conditions alone is very selective, I'd assume that PostgreSQL would choose a regular index scan on the most selective of the indexes and use the other conditions as a filter. The complexity of such a query is proportional to the percentage of rows that match the index condition (say, O(1) if there is only a constant number of rows with user_id = 1 regardless of the table size).

The ideal indexes for these queries are:

CREATE INDEX ON user_tran (transaction_id, time_stamp);
CREATE INDEX ON user_tran (user_id, time_stamp);

answered May 9, 2018 at 20:29

Laurenz Albe

257k22 gold badges312 silver badges388 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Postgres Query Complexity when using hash index and b+ tree index

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related