Сложность запроса Postgres при использовании хеш-индекса и индекса дерева b +

Question

Моя таблица (user_tran) имеет 3 поля: " user_id ", "action_id ", " time_stamp "

У меня хеш-индекс user_id и transaction_id (так как мне нужно сделать точное совпадение) и индекс b + tree на time_stamp

Запрос

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; 

Кто-нибудь знает, какова сложность этого запроса? Я знаю, если бы мы просто фильтровали по столбцу хеш-индекса, это было бы o (1) , а b + tree дает o (lgn) . Но как насчет их объединения?

Это будет o (lgn + 1) ?

Также как бы стол хранился под капотом. Будет ли СУБД поддерживать 3 индекса (2 хэша и 1 b + дерево) одновременно?

Погуглил немного, но не нашел ответа.

Answer 1

С такими тремя индексами сложность для запроса, использующего индексы, будет O (n) , потому что единственный способ объединить несколько индексов - это битовая карта и . Создание растрового изображения требует чтения всего индекса, который равен O (n) .

Итак, если только одно из условий не является очень избирательным, я бы предположил, что PostgreSQL выберет регулярное сканирование индекса по наиболее селективному из индексов и использует другие условия в качестве фильтра. Сложность такого запроса пропорциональна проценту строк, которые соответствуют условию индекса (скажем, O (1) , если существует только постоянное количество строк с user_id = 1 независимо от размера таблицы) .

Идеальными индексами для этих запросов являются:

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