Since you have relatively few distinct values, there is an efficient solution with a B-tree index. Probably faster than a query based on the GiST index for more than a few result rows. The GiST solution will be faster for few result rows, approaching the task from the opposite direction.
Setup
Let's store separate integer columns for lower and upper bound instead of int4range
. Also only needs 8 bytes of storage instead of 14 (+ 4 bytes of alignment padding) for int4range
.
CREATE TABLE m_filter (
value bigint NOT NULL
, m_lo int4 NOT NULL -- incl. lower bound
, m_hi int4 NOT NULL -- excl. upper bound
, EXCLUDE USING gist (int4range(m_lo, m_hi) WITH &&, value WITH =)
);
Downside 1: the exclusion constraint is based on an expression and a bit slower.
Downside 2: the exclusion constraint creates a GiST index implicitly. So a query with the range containment operator @>
would work out of the box, no additional index needed.
For the B-tree solution, create this index:
CREATE INDEX m_filter_value_lo_hi_idx ON m_filter (value, m_lo DESC, m_hi);
We could also make it work with int4range
. Just more overhead and slower results.
Query 1 - with values table
Assuming there is also a table dist_values
with one row per distinct value
- something that's commonly present in one form or another:
CREATE TABLE dist_values (
value bigint PRIMARY KEY
);
Then it's fast:
SELECT v.value
FROM dist_values v
WHERE EXISTS (
SELECT FROM m_filter m
WHERE m.value = v.value
AND m.m_lo <= 55
AND m.m_hi > 55
);
db<>fiddle here
1 index(-only) lookup per value
. Makes always only 1000 of them in your case.
Query 2 - without values table
If there is no table dist_values
, we can still make it pop with an emulated index-skip scan:
WITH RECURSIVE cte AS (
( -- parentheses required
SELECT value, true AS hit
FROM m_filter v
WHERE EXISTS ( -- ①
SELECT FROM m_filter m
WHERE m.value = v.value
AND m.m_lo <= 55 -- $my_int
AND m.m_hi > 55 -- $my_int
)
ORDER BY 1
LIMIT 1
)
UNION ALL
SELECT v.*
FROM cte c
CROSS JOIN LATERAL (
SELECT v.value
, EXISTS ( -- ②
SELECT FROM m_filter m
WHERE m.value = v.value
AND m.m_lo <= 55 -- $my_int
AND m.m_hi > 55 -- $my_int
) AS hit
FROM m_filter v
WHERE v.value > c.value -- lateral reference
ORDER BY 1
LIMIT 1
) v
)
SELECT value
FROM cte
WHERE hit;
db<>fiddle here
Still fast, if not as fast.
① We can skip ahead in the initial term.
② But we need to keep all values in the recursive term, so not to terminate recursion.
See:
@>
(containment) operator you are looking for? That is supported by the GiST index.EXPLAIN (ANALYZE, BUFFERS)
show (please turn track_io_timing on if it is not already). How much faster does it need to be?EXPLAIN (ANALYZE, BUFFERS)
output, when run with your 500k data).