Если я правильно понял суть вопроса, вам подойдёт любая KV СУБД. Вынесите только эту таблицу в какой-нибудь Tarantool или Redis (я имею в виду использовать хранимые процедуры для вашей задачи). 1-3 млн записей - относительно немного. Даже если одна запись весит 4 КБ, все данные займут 4-12 ГБ ОЗУ, что не так уж и много. Если использовать батчинг, что Redis, что Tarantool дадут вам на 16 ядрах свыше 100к RPS на такие сложные запросы.
Можете так же глянуть AerospikeDB (хранит данные на диске, но с индексами в памяти, где один индекс стоит 64 байт), но я не уверен, что вам хватит его функционала. Если вы дадите больше контекста, возможно, я смогу предложить вам другие идеи.
UPD: AerospikeDB тоже позволяет сохранить готовые процедуры, так что его функционала хватит для вышеуказанной задачи.
