1

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

8
  • 2
    I don't understand. Isn't it the @> (containment) operator you are looking for? That is supported by the GiST index. Jun 16, 2022 at 20:26
  • @LaurenzAlbe no, I'm looking for operator which is supported by btree index
    – g4s8
    Jun 16, 2022 at 21:14
  • 3
    No, btree can't support that efficiently in the general case. What is the problem with using the constraint index? What does EXPLAIN (ANALYZE, BUFFERS) show (please turn track_io_timing on if it is not already). How much faster does it need to be?
    – jjanes
    Jun 16, 2022 at 22:34
  • Hi, and welcome to dba.se! Can some of the values be inside the range and some outside of the range? It would be good if you could provide a representative sample of your data at dbfiddle.uk along with your PostgreSQL version number. How many records do you have in total - approximately?
    – Vérace
    Jun 19, 2022 at 18:12
  • 1
    I would suggest you do NOT try to upload 500k rows in dbfiddle.uk. But as previous commenters asked, please explain why the performance of the current queries in not good enough (and add the EXPLAIN (ANALYZE, BUFFERS) output, when run with your 500k data). Jun 22, 2022 at 8:38

1 Answer 1

2

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:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.