Re: Adding skip scan (including MDAM style range skip scan) to nbtree

From: Peter Geoghegan <pg(at)bowt(dot)ie>
To: Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com>
Cc: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, Masahiro Ikeda <ikedamsh(at)oss(dot)nttdata(dot)com>, Tomas Vondra <tomas(at)vondra(dot)me>, Masahiro(dot)Ikeda(at)nttdata(dot)com, pgsql-hackers(at)lists(dot)postgresql(dot)org, Masao(dot)Fujii(at)nttdata(dot)com, Mark Dilger <mark(dot)dilger(at)enterprisedb(dot)com>
Subject: Re: Adding skip scan (including MDAM style range skip scan) to nbtree
Date: 2025-04-29 22:51:38
Message-ID: CAH2-Wz=2WgQwyM=S_+e_oKEqNcUuZoriw+mwNUp++KsawMnS4g@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Tue, Apr 1, 2025 at 7:02 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> Though I think it should be "" safe even when "key->sk_attno >
> firstchangingattnum" "", to highlight that the rule here is
> significantly more permissive than even the nearby range skip array
> case, which is still safe when (key->sk_attno == firstchangingattnum).

Mark Dilger reported a bug in commit 8a510275 on Saturday, which I
fixed in commit b75fedca from Monday. Mark's repro was a little bit
complicated, though.

Attached is a Python script that performs fuzz testing of nbtree skips
scan. It is capable of quickly finding the same bug as the one that
Mark reported. The script generates random, complicated multi-column
index scans on a (a, b, c, d) index on a test table, and verifies that
each queries gives the same answer as an equivalent sequential scan
plan. This works quite well as a general smoke test. I find that if I
deliberately add somewhat plausible bugs to the code in
_bt_set_startikey, the fuzz testing script is usually able to identify
wrong answers to queries in under a minute.

I don't expect that this script will actually discover any real bugs
-- I ran it for long enough to get the sense that that was unlikely.
But it seemed like a worthwhile exercise.

--
Peter Geoghegan

Attachment Content-Type Size
fuzz_skip_scan.py text/x-python-script 20.9 KB

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message jian he 2025-04-30 00:00:00 expand on_error ignore error handling scope
Previous Message Nathan Bossart 2025-04-29 21:54:38 Re: alphabetize long options in pg_dump[all] docs