Re: GiST multirange index scans can fail to return rows

From: Joao Rito <joaovictor(dot)rito(at)gmail(dot)com>
To: PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>, PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org>
Cc: Andrey Borodin <x4mmm(at)yandex-team(dot)ru>, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
Subject: Re: GiST multirange index scans can fail to return rows
Date: 2026-11-16 06:07:08
Message-ID: 20261116060708.776-1-joaovictor.rito@gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi Andrey, Alexander,

Thank you for the fix. I tested v4 on current master (5ffc8210377,
built with --enable-cassert and --enable-tap-tests, gcc 14.2, in a
Debian container). v4 applies cleanly, git apply --whitespace=error
and git diff --check report nothing, and the build has 0 warnings.

On master I could reproduce the report. With only the test hunks of
v4 applied, make check fails in multirangetypes (1 of 243): the new
query returns 500 instead of 501.

I also wrote a small table. Row 1 is '{[1,11),[21,31),[41,51)}', row 2
is '{[2,5),[22,25)}', row 3 is '{[1,51)}', row 4 is '{}', row 5 is
'{[3,4)}', row 6 is '{[1,11),[21,31),[41,52)}', row 7 is NULL, plus
2000 other rows and a GiST index on the column. For
mr <@ '{[1,11),[21,31),[41,51)}'::int4multirange, a seq scan returns
ids 1, 2, 4, 5. On master an index scan and a bitmap scan return only
4 and 5. With v4 both return 1, 2, 4, 5.

For a wider check I compared seq scan, index scan and bitmap scan
(enable_* settings; for one query per table, EXPLAIN showed the index
or bitmap scan in use) on random
multiranges with gaps, empty values, NULLs and infinite bounds. I used
int4, date and numeric multiranges. Each type had three tables: index
built after the load, index created first and rows inserted later, and
index built then 20 percent of rows deleted and new rows inserted.
The tables had 20000 rows (int4) and 6000 rows (date, numeric). There
were 13266 index scan comparisons and the same number of bitmap
comparisons per run; 9824 of each had a non-empty seq scan result.
The operators were @>, <@, &&, <<, >>, &<,
&>, -|- and = with a multirange on the right side, plus @>, <@, &&,
<<, >>, &<, &>, -|- with a range (including empty and (,)) and @>
with an element. Queries included the empty multirange, {(,)} and
values copied from table rows.

On master, 672 comparisons (index and bitmap together) differ from the
seq scan, all for <@ with a multirange on the right side, in all 9
tables. With a range or an element on the right, and with all
other operators, I saw no difference. With v4 there were 0
differences in all of them.

With v4, make check passes (243 tests, multirangetypes ok) and
make check in contrib/btree_gist passes (32 tests).

What I did not test: the TAP tests, check-world, other contrib
modules, the back branches (the commit message says back-patch to all
supported branches), other platforms or compilers (I ran one Linux
build), multirange types other than int4, date and numeric,
joins and other plans than a plain scan with one index condition,
concurrent inserts, GiST index checks with amcheck (the
function was not available in my build), and performance.

Small comments from reading the patch, not from tests. The v4 text of
the comment still says "Every multirange contains an infinite number
of empty multiranges, even an empty one."; Andrey's suggestion of "The
empty multirange is contained by every multirange." reads clearer to
me. The commit message still has the typo "multirage". The patch adds
two blank lines before the comment of multirange_gist_consistent(),
which pgindent may remove.

I have no objection to the change from what I could test.

Regards,
Joao Rito

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Joao Rito 2026-11-16 06:07:15 Re: [PATCH v2] Avoid carrying self lock-only xmax to updated tuple
Previous Message Joao Rito 2026-11-16 06:07:00 Re: [PATCH] contrib/fuzzystrmatch: improve test coverage