On Thu, Nov 6, 2025 at 2:01 PM Michael Christofides
<[email protected]> wrote:
> I'm trying to understand the new Index Searches field in Postgres 18 explain
> analyze output. I've put together a super simple test case (below) expecting
> a skip scan with 2 Index Searches, one for each value in the leading
> (boolean) column of the index.
That's a good question. You're right that in this specific case, with
a boolean column, skip scan performs 4 index searches, when in
principle it only really needs to do 3.
> In reality, instead of 2 Index Searches, I got 4 (query plan below).
During work on skip scan (and on the 17 work), I went to quite a lot
of effort to build custom instrumentation that would show me exactly
what an index scan was doing. Including details of the scan's array
keys, and how they advance as the scan advances through the index.
Attached is its output when I run your test query. The issue here is
that skip scan thinks that there are 4 distinct skip array values that
it must use:
1. SK_BT_MINVAL
2. false
3. true
4. SK_ISNULL
SK_BT_MINVAL is a sentinel value that represents the lowest possible
value that can be stored by the data type. That's the same thing as
"false", which is a little bit unfortunate with a datatype like bool,
where the difference might actually matter -- here we waste an access
to the leftmost leaf page to "advance" the skip array from
SK_BT_MINVAL to false, instead of making false the lowest skip array
value directly, from the very start.
This is highly unlikely to matter with a data type like integer,
though: in practice it's very unlikely that the value INT_MIN is
actually stored in the index, so having 2 distinct representations for
the same thing (SK_BT_MINVAL and INT_MIN) is equally unlikely to
result in the scan reading any more leaf pages than strictly necessary
due to this implementation deficiency. We'll have to go to the
leftmost leaf page to determine what the real lowest value in the
index is either way -- doesn't matter if you start from SK_BT_MINVAL
or from INT_MIN (unless there really are hundreds of tuples that have
the value INT_MIN, when the difference between those 2 things starts
to matter, as with your bool test case).
I did actually think about making this work. In fact, there were
revisions of the skip scan patch where it actually did work.
Ultimately I judged that it wasn't worth the trouble of introducing
this special case. Better to have types with skip support (like
boolean and integer) behave exactly the same as all other types, by
also using these SK_BT_MINVAL/SK_BT_MAXVAL sentinels (we don't use
SK_BT_MAXVAL at all here because the highest skip array value is
SK_ISNULL, but we would if the index was declared NULLS FIRST).
That just leaves SK_ISNULL. We cannot assume that the index doesn't
have any NULLs (unless the query uses IS NOT NULL directly). We might
end up having to read the rightmost leaf page anyway, in which case
there won't be an extra search for SK_ISNULL, but we'll likely need an
extra search for this too (just like the leftmost leaf page, with
SK_BT_MINVAL). This isn't an implementation deficiency -- it's
strictly necessary for correctness.
--
Peter Geoghegan
pg@regression:5432 [1116003]=# SELECT boolean_field FROM example WHERE
integer_field = 5432;
LOG:
👾 btbeginscan to begin scan of index "bool_int_idx" in worker -1
♻️ btrescan
btrescan: BTScanPosInvalidate() called for markPos
_bt_preprocess_keys: scan->keyData[0]: [ strategy: = , attno:
2/"integer_field", func: int84eq, flags: [] ]
_bt_preprocess_keys: so->keyData[0]: [ strategy: = , attno:
1/"boolean_field", func: booleq, flags: [SK_SEARCHARRAY, SK_BT_REQFWD,
SK_BT_REQBKWD, SK_BT_SKIP] ]
so->keyData[1]: [ strategy: = , attno:
2/"integer_field", func: int84eq, flags: [SK_BT_REQFWD, SK_BT_REQBKWD] ]
_bt_preprocess_keys: scan->numberOfKeys is 1, so->numberOfKeys on output is 2,
so->numArrayKeys on output is 1
➕ ➕ ➕
_bt_first: sk could not be formed, so descending to leftmost leaf page in whole
index
_bt_readpage: 🍀 1 with 122 offsets/tuples (leftsib 0, rightsib 2) ➡️
_bt_readpage first: (boolean_field, integer_field)=(f, 0), TID='(171,68)',
0x7fffaeaa9fc8, from non-pivot offnum 2 started page
_bt_readpage pstate.startikey: 0, with 2 scan keys
_bt_checkkeys: comparing (boolean_field, integer_field)=(f, 0) with TID
(171,68), 0x7fffaeaa9fc8
_bt_advance_array_keys, sktrig (required): 0, tuple: (boolean_field,
integer_field)=(f, 0), 0x7fffaeaa9fc8
- sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: ?????
SK_BT_MINVAL <--
+ sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: f
_bt_readpage final: (boolean_field, integer_field)=(f, 0), TID='(171,68)',
0x7fffaeaa9fc8, from non-pivot offnum 2 set so->currPos.moreRight=false ➡️ 🛑
_bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
➕ ➕ ➕
_bt_first: sk_attno 1. val: f, func: btboolcmp, flags: [SK_SEARCHARRAY,
SK_BT_REQFWD, SK_BT_REQBKWD, SK_BT_SKIP]
sk_attno 2. val: 5432, func: btint84cmp, flags: [SK_BT_REQFWD,
SK_BT_REQBKWD]
with strat_total='= ', inskey.keys=2, inskey.nextkey=0,
inskey.backward=0
🔽 ==================== _bt_search begin at root 3 level 1 ====================
_bt_moveright: blk 3 is rightmost
_bt_search: sk > (boolean_field, integer_field)=(f, 5321), sk <=
(boolean_field, integer_field)=(f, 5443)
🔽 -------------------- descended to child blk 46 level 0 --------------------
_bt_moveright: (boolean_field, integer_field)=(f, 5443), high key no move right
⏹️ ==================== _bt_search end ==================== ➡️
_bt_readpage: 🍀 46 with 123 offsets/tuples (leftsib 45, rightsib 47) ➡️
_bt_readpage first: (boolean_field, integer_field)=(f, 5432), TID='(5,40)',
0x7fffaeaae770, from non-pivot offnum 113 started page
_bt_readpage pstate.startikey: 0, with 2 scan keys
_bt_checkkeys: comparing (boolean_field, integer_field)=(f, 5432) with TID
(5,40), 0x7fffaeaae770
_bt_checkkeys: comparing (boolean_field, integer_field)=(f, 5433) with TID
(68,20), 0x7fffaeaae758
_bt_advance_array_keys, sktrig (required): 1, tuple: (boolean_field,
integer_field)=(f, 5433), 0x7fffaeaae758
- sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: f
+ sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: t
_bt_readpage final: (boolean_field, integer_field)=(f, 5433), TID='(68,20)',
0x7fffaeaae758, from non-pivot offnum 114 set so->currPos.moreRight=false ➡️ 🛑
_bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 4, nmatching: 5 ✅
➕ ➕ ➕
_bt_first: sk_attno 1. val: t, func: btboolcmp, flags: [SK_SEARCHARRAY,
SK_BT_REQFWD, SK_BT_REQBKWD, SK_BT_SKIP]
sk_attno 2. val: 5432, func: btint84cmp, flags: [SK_BT_REQFWD,
SK_BT_REQBKWD]
with strat_total='= ', inskey.keys=2, inskey.nextkey=0,
inskey.backward=0
🔽 ==================== _bt_search begin at root 3 level 1 ====================
_bt_moveright: blk 3 is rightmost
_bt_search: sk > (boolean_field, integer_field)=(t, 5357), sk <=
(boolean_field, integer_field)=(t, 5481)
🔽 -------------------- descended to child blk 129 level 0 --------------------
_bt_moveright: (boolean_field, integer_field)=(t, 5481), high key no move right
⏹️ ==================== _bt_search end ==================== ➡️
_bt_readpage: 🍀 129 with 125 offsets/tuples (leftsib 128, rightsib 130) ➡️
_bt_readpage first: (boolean_field, integer_field)=(t, 5432), TID='(277,111)',
0x7fffaeab0fb0, from non-pivot offnum 77 started page
_bt_readpage pstate.startikey: 0, with 2 scan keys
_bt_checkkeys: comparing (boolean_field, integer_field)=(t, 5432) with TID
(277,111), 0x7fffaeab0fb0
_bt_checkkeys: comparing (boolean_field, integer_field)=(t, 5433) with TID
(54,172), 0x7fffaeab0f78
_bt_advance_array_keys, sktrig (required): 1, tuple: (boolean_field,
integer_field)=(t, 5433), 0x7fffaeab0f78
- sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: t
+ sk: 0, sk_attno: 1, cur_elem: -1, num_elems: -1, val: SK_ISNULL
_bt_readpage final: (boolean_field, integer_field)=(t, 5433), TID='(54,172)',
0x7fffaeab0f78, from non-pivot offnum 78 set so->currPos.moreRight=false ➡️ 🛑
_bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: 0, nmatching: 1 ✅
➕ ➕ ➕
_bt_first: sk_attno 1. val: NULL, flags: [SK_ISNULL, SK_SEARCHARRAY,
SK_SEARCHNULL, SK_BT_REQFWD, SK_BT_REQBKWD, SK_BT_SKIP]
sk_attno 2. val: 5432, func: btint84cmp, flags: [SK_BT_REQFWD,
SK_BT_REQBKWD]
with strat_total='= ', inskey.keys=2, inskey.nextkey=0,
inskey.backward=0
🔽 ==================== _bt_search begin at root 3 level 1 ====================
_bt_moveright: blk 3 is rightmost
_bt_search: sk > (boolean_field, integer_field)=(t, 9973), sk <=
(boolean_field, integer_field)=() , (<= separator is high key)
🔽 -------------------- descended to child blk 167 level 0 --------------------
_bt_moveright: blk 167 is rightmost
⏹️ ==================== _bt_search end ==================== ➡️
_bt_readpage: 🍀 167 with 28 offsets/tuples (leftsib 166, rightsib 0) ➡️
_bt_readpage first: none, offnum 29 is > maxoff of 28
_bt_readpage final: , (nil), continuescan high key check not performed on
rightmost page ➡️ 🛑
_bt_readpage stats: currPos.firstItem: 0, currPos.lastItem: -1, nmatching: 0 ❌
btendscan for index "bool_int_idx", ParallelWorkerNumber: -1, npages: 4,
nforcenonrequiredpages: 0, nwrongprecheckpages: 0, nsearches: 4
┌───────────────┐
│ boolean_field │
├───────────────┤
│ f │
│ f │
│ f │
│ f │
│ f │
│ t │
└───────────────┘
(6 rows)
