CODEWITHSUNDEEP
databasepostgresqlindexing
Jeff
Jeff

Reputation: 3

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

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.

Upvotes: 0

Views: 356

Answers (1)

Laurenz Albe
Laurenz Albe

Reputation: 246523

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);

Upvotes: 1

Related Questions