Check int4range includes number using B-tree index

Question

I have a table with two important columns: value and m_range, where value:

CREATE TABLE m_filter (                                                  
    value     BIGINT NOT NULL,
    m_range   int4range NOT NULL,
    EXCLUDE   USING GIST (m_range WITH &&, value WITH =)
);

The usage scenario is following:

1. It's not frequently updated, but it can contain a quite large amount of data.
2. It's queries very frequently by searching for values, which are in m_range.

So I'm supposing to use BTree index for m_range column instead of Gist for better query performance:

CREATE INDEX i_m_filter_range ON m_filter USING BTREE (m_range);

But according to docs https://www.postgresql.org/docs/current/indexes-types.html BTree indexes supports only these operators: < <= = >= >.

Is it possible to select all values where int4range columnt contains some integer using BTree? Like I can do with ranges using @> and <@ operators.

---

Update:

In this table m_range values could be int values from 0 to 9999, each value has about 500 non-overlaping m_range records average, and there are about 1_000 values, so it's about 500_000 m_range values.

PostgreSQL version is 13.5

Answer 1

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:

• Best performance to get distinct values for a given key from a big table
• Optimize GROUP BY query to retrieve latest row per user