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

Matthias van de Meent <boekewurm+postgres@gmail.com>

From: Matthias van de Meent <boekewurm+postgres@gmail.com>

To: Peter Geoghegan <pg@bowt.ie>

Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Masahiro Ikeda <ikedamsh@oss.nttdata.com>, Tomas Vondra <tomas@vondra.me>, Masahiro.Ikeda@nttdata.com, pgsql-hackers@lists.postgresql.org, Masao.Fujii@nttdata.com

Date: 2025-04-01T21:56:13Z

Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

nbtree: Always set skipScan flag on rescan.
- 454c046094ab 19 (unreleased) landed
- bee763aea13f 18.0 landed
meson: Build numeric.c with -ftree-vectorize.
- 9016fa7e3bcd 19 (unreleased) cited
Fix "variable not found in subplan target lists" in semijoin de-duplication.
- b8a1bdc458e3 19 (unreleased) cited
Revert "nbtree: Remove useless row compare arg."
- dd2ce3792754 18.0 landed
nbtree: Remove useless row compare arg.
- 54c6ea8c81db 18.0 cited
Prevent premature nbtree array advancement.
- 5f4d98d4f371 18.0 landed
nbtree: tighten up array recheck rules.
- 7e25c9363a82 18.0 landed
Avoid treating nonrequired nbtree keys as required.
- 0f08df406822 18.0 landed
Adjust overstrong nbtree skip array assertion.
- 9d924dbb3710 18.0 landed
Make NULL tuple values always advance skip arrays.
- b75fedcab791 18.0 cited
Avoid extra index searches through preprocessing.
- b3f1a13f22f9 18.0 landed
Improve nbtree skip scan primitive scan scheduling.
- 21a152b37f36 18.0 landed
Further optimize nbtree search scan key comparisons.
- 8a510275dd6b 18.0 landed
Add nbtree skip scan optimization.
- 92fe23d93aa3 18.0 landed
Improve nbtree array primitive scan scheduling.
- 9a2e2a285a14 18.0 landed
nbtree: Make BTMaxItemSize into object-like macro.
- 426ea611171d 18.0 landed
Show index search count in EXPLAIN ANALYZE, take 2.
- 0fbceae841cb 18.0 landed
Make parallel nbtree index scans use an LWLock.
- 67fc4c9fd7fa 18.0 landed
Show index search count in EXPLAIN ANALYZE.
- 5ead85fbc811 18.0 landed
Avoid nbtree parallel scan currPos confusion.
- b5ee4e52026b 18.0 cited
nbtree: Remove useless 'strat' local variable.
- b6558e4f837e 18.0 landed
Normalize nbtree truncated high key array behavior.
- 79fa7b3b1a44 18.0 landed
Refactor handling of nbtree array redundancies.
- b524974106ac 18.0 landed
Fix nbtree pgstats accounting with parallel scans.
- c00c54a9ac1e 18.0 landed
- fb4f5e58af97 17.0 landed
Avoid parallel nbtree index scan hangs with SAOPs.
- d8adfc18bebf 18.0 landed
- a24bffc021d9 17.0 landed
Show Parallel Bitmap Heap Scan worker stats in EXPLAIN ANALYZE
- 5a1e6df3b84c 18.0 cited
Enhance nbtree ScalarArrayOp execution.
- 5bf748b86bc6 17.0 cited
Skip checking of scan keys required for directional scan in B-tree
- e0b1ee17dc3a 17.0 cited
Instead of using a numberOfRequiredKeys count to distinguish required
- 7ccaf13a06b8 8.2.0 cited

On Tue, 1 Apr 2025 at 04:02, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Fri, Mar 28, 2025 at 5:59 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > Attached is v32, which has very few changes, but does add a new patch:
> > a patch that adds skip-array-specific primitive index scan heuristics
> > to _bt_advance_array_keys (this is
> > v32-0003-Improve-skip-scan-primitive-scan-scheduling.patch).
>
> Attached is v33

0001:

I just realised we never check whether skip keys' high/low_compare
values generate valid quals, like what you'd see generated for WHERE a
> 5 AND a < 3 AND b = 2;

This causes a performance regression in the patched version:

   ->  Index Only Scan using test_a_b_idx on test  (cost=0.14..8.16
rows=1 width=0) (actual time=0.240..0.241 rows=0.00 loops=1)
         Index Cond: ((a > 5) AND (a < 3) AND (b = 2))
         Heap Fetches: 0
         Index Searches: 1
         Buffers: shared hit=1

As you can see in this explain, we're doing an index search, while the
index searches attribute before this patch would've been 0 due to
conflicting conditions.

(This came up while reviewing 0004, when I thought about doing this
key consistency check after the increment/decrement optimization of
that patch and after looking couldn't find the skipscan bounds
consistency check at all)

0002:

// nbtutils.c

> +             * (safe even when "key->sk_attno <= firstchangingattnum")

Typo: should be "key->sk_attno >= firstchangingattnum".

I'd also refactor the final segment to something like the following,
to remove a redundant compare when the attribute we're checking is
equal between firsttup and lasttup:

+        firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc,
&firstnull);
+
+        /* Test firsttup */
+        _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
+                                   firstdatum, firstnull, array, key,
+                                   &result);
+        if (result != 0)
+            break;                /* unsafe */
+
+        /* both attributes are equal, so no need to check lasttup */
+        if (key->sk_attno < firstchangingattnum)
+            continue;
+
+        lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull);
+
+        /* Test lasttup */
+        _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
+                                   lastdatum, lastnull, array, key,
+                                   &result);
+        if (result != 0)
+            break;                /* unsafe */
+
+        /* Safe, range skip array satisfied by every tuple */

0003: LGTM

0004: LGTM, but note the current bug in 0001, which is probably best
solved with a fix that keeps this optimization in mind, too.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)