Re: Adding skip scan (including MDAM style range skip scan) to nbtree
Masahiro Ikeda <ikedamsh@oss.nttdata.com>
Commits
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 2024-11-21 17:47, Masahiro Ikeda wrote:
>> On 2024-11-21 04:40, Peter Geoghegan wrote:
>> diff --git a/src/backend/access/nbtree/nbtutils.c
>> b/src/backend/access/nbtree/nbtutils.c
>> index b70b58e0c..ddae5f2a1 100644
>> --- a/src/backend/access/nbtree/nbtutils.c
>> +++ b/src/backend/access/nbtree/nbtutils.c
>> @@ -3640,7 +3640,7 @@ _bt_advance_array_keys(IndexScanDesc scan,
>> BTReadPageState *pstate,
>> * for skip scan, and stop maintaining the scan's skip arrays
>> until we
>> * reach the page's finaltup, if any.
>> */
>> - if (has_skip_array && beyond_end_advance &&
>> + if (has_skip_array && !all_required_satisfied &&
>> !has_required_opposite_direction_skip && pstate->finaltup)
>> pstate->beyondskip = true;
>>
>> However, a small number of my test cases now fail. And (I assume) this
>> approach has certain downsides on leaf pages where we're now too quick
>> to stop maintaining skip arrays.
>
> Since I've built with the above change and executed make check, I found
> that there is an assertion error, which may not be related to what you
> pointed
> out.
>
> * the reproducible simple query (you can see the original query in
> opr_sanity.sql).
> select * from pg_proc
> where proname in (
> 'lo_lseek64',
> 'lo_truncate',
> 'lo_truncate64')
> and pronamespace = 11;
>
> * the assertion error
> TRAP: failed Assert("sktrig_required && required"), File:
> "nbtutils.c", Line: 3375, PID: 362411
>
> While investigating the error, I thought we might need to consider
> whether key->sk_flags does not have SK_BT_SKIP. The assertion error
> occurs because
> requiredSameDir doesn't become true since proname does not have
> SK_BT_SKIP.
>
> + if (beyondskip)
> + {
> + /*
> + * "Beyond end advancement" skip scan optimization.
> + *
> + * Just skip over any skip array scan keys. Treat all other scan
> + * keys as not required for the scan to continue.
> + */
> + Assert(!prechecked);
> +
> + if (key->sk_flags & SK_BT_SKIP)
> + continue;
> + }
> + else if (((key->sk_flags & SK_BT_REQFWD) &&
> ScanDirectionIsForward(dir)) ||
> + ((key->sk_flags & SK_BT_REQBKWD) &&
> ScanDirectionIsBackward(dir)))
> requiredSameDir = true;
>
My previous investigation was incorrect, sorry. IIUC,
_bt_check_compare()
should return false as soon as possible with continuescan=true after the
tuple fails the key check when beyondskip=true, rather than setting
requiredSameDir to true. Because it has already been triggered to
perform
a full index scan for the page.
Though the change fixes the assertion error in 'make check', there are
still
cases where the number of return values is incorrect. I would also like
to
continue investigating.
Regards,
--
Masahiro Ikeda
NTT DATA CORPORATION