Skip to content

Commit ec98602

Browse files
petergeogheganpetergeoghegan
committed
Improve nbtree unsatisfiable RowCompare detection.
Move nbtree's detection of RowCompare quals that are unsatisfiable due to having a NULL in their first row element: rather than detecting these cases at the point where _bt_first builds its insertion scan key, do so earlier, during preprocessing proper. This brings the RowCompare case in line every other case involving an unsatisfiable-due-to-NULL qual. nbtree now consistently detects such unsatisfiable quals -- even when they happen to involve a key that isn't examined by _bt_first at all. Affected cases thereby avoid useless full index scans that cannot possibly return any matching rows. Author: Peter Geoghegan <pg@bowt.ie> Reviewed-By: Matthias van de Meent <boekewurm+postgres@gmail.com> Discussion: https://postgr.es/m/CAH2-WzmySVXst2hFrOATC-zw1Byg1XC-jYUS314=mzuqsNwk+Q@mail.gmail.com
1 parent 428a99b commit ec98602

File tree

6 files changed

+248
-16
lines changed

6 files changed

+248
-16
lines changed

‎src/backend/access/nbtree/nbtsearch.c

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1162,23 +1162,23 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
11621162
if (cur->sk_flags & SK_ROW_HEADER)
11631163
{
11641164
/*
1165-
* Row comparison header: look to the first row member instead.
1166-
*
1167-
* The member scankeys are already in insertion format (ie, they
1168-
* have sk_func = 3-way-comparison function), but we have to watch
1169-
* out for nulls, which _bt_preprocess_keys didn't check. A null
1170-
* in the first row member makes the condition unmatchable, just
1171-
* like qual_ok = false.
1165+
* Row comparison header: look to the first row member instead
11721166
*/
11731167
ScanKey subkey = (ScanKey) DatumGetPointer(cur->sk_argument);
11741168

1169+
/*
1170+
* Cannot be a NULL in the first row member: _bt_preprocess_keys
1171+
* would've marked the qual as unsatisfiable, preventing us from
1172+
* ever getting this far
1173+
*/
11751174
Assert(subkey->sk_flags & SK_ROW_MEMBER);
1176-
if (subkey->sk_flags & SK_ISNULL)
1177-
{
1178-
Assert(!so->needPrimScan);
1179-
_bt_parallel_done(scan);
1180-
return false;
1181-
}
1175+
Assert(subkey->sk_attno == cur->sk_attno);
1176+
Assert(!(subkey->sk_flags & SK_ISNULL));
1177+
1178+
/*
1179+
* The member scankeys are already in insertion format (ie, they
1180+
* have sk_func = 3-way-comparison function)
1181+
*/
11821182
memcpy(inskey.scankeys + i, subkey, sizeof(ScanKeyData));
11831183

11841184
/*

‎src/backend/access/nbtree/nbtutils.c

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3371,6 +3371,13 @@ _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
33713371
{
33723372
ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
33733373

3374+
if (subkey->sk_flags & SK_ISNULL)
3375+
{
3376+
/* First row member is NULL, so RowCompare is unsatisfiable */
3377+
Assert(subkey->sk_flags & SK_ROW_MEMBER);
3378+
return false;
3379+
}
3380+
33743381
for (;;)
33753382
{
33763383
Assert(subkey->sk_flags & SK_ROW_MEMBER);
@@ -3982,13 +3989,14 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
39823989
if (subkey->sk_flags & SK_ISNULL)
39833990
{
39843991
/*
3985-
* Unlike the simple-scankey case, this isn't a disallowed case.
3992+
* Unlike the simple-scankey case, this isn't a disallowed case
3993+
* (except when it's the first row element that has the NULL arg).
39863994
* But it can never match. If all the earlier row comparison
39873995
* columns are required for the scan direction, we can stop the
39883996
* scan, because there can't be another tuple that will succeed.
39893997
*/
3990-
if (subkey != (ScanKey) DatumGetPointer(skey->sk_argument))
3991-
subkey--;
3998+
Assert(subkey != (ScanKey) DatumGetPointer(skey->sk_argument));
3999+
subkey--;
39924000
if ((subkey->sk_flags & SK_BT_REQFWD) &&
39934001
ScanDirectionIsForward(dir))
39944002
*continuescan = false;

‎src/test/regress/expected/btree_index.out

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -142,6 +142,133 @@ SELECT b.*
142142
4500 | 2080851358
143143
(1 row)
144144

145+
--
146+
-- Add coverage of RowCompare quals whose row omits a column ("proargtypes")
147+
-- that's after the first column, but before the final column. The scan's
148+
-- initial positioning strategy must become >= here (it's not the > strategy,
149+
-- since the absence of "proargtypes" makes that tighter constraint unsafe).
150+
--
151+
explain (costs off)
152+
SELECT proname, proargtypes, pronamespace
153+
FROM pg_proc
154+
WHERE (proname, pronamespace) > ('abs', 0)
155+
ORDER BY proname, proargtypes, pronamespace LIMIT 1;
156+
QUERY PLAN
157+
-------------------------------------------------------------------------------
158+
Limit
159+
-> Index Only Scan using pg_proc_proname_args_nsp_index on pg_proc
160+
Index Cond: (ROW(proname, pronamespace) > ROW('abs'::name, '0'::oid))
161+
(3 rows)
162+
163+
SELECT proname, proargtypes, pronamespace
164+
FROM pg_proc
165+
WHERE (proname, pronamespace) > ('abs', 0)
166+
ORDER BY proname, proargtypes, pronamespace LIMIT 1;
167+
proname | proargtypes | pronamespace
168+
---------+-------------+--------------
169+
abs | 20 | 11
170+
(1 row)
171+
172+
--
173+
-- Similar to the previous test case, but this time it's a backwards scan
174+
-- using a < RowCompare. Must use the <= strategy (and not the < strategy).
175+
--
176+
explain (costs off)
177+
SELECT proname, proargtypes, pronamespace
178+
FROM pg_proc
179+
WHERE (proname, pronamespace) < ('abs', 1_000_000)
180+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC LIMIT 1;
181+
QUERY PLAN
182+
-------------------------------------------------------------------------------------
183+
Limit
184+
-> Index Only Scan Backward using pg_proc_proname_args_nsp_index on pg_proc
185+
Index Cond: (ROW(proname, pronamespace) < ROW('abs'::name, '1000000'::oid))
186+
(3 rows)
187+
188+
SELECT proname, proargtypes, pronamespace
189+
FROM pg_proc
190+
WHERE (proname, pronamespace) < ('abs', 1_000_000)
191+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC LIMIT 1;
192+
proname | proargtypes | pronamespace
193+
---------+-------------+--------------
194+
abs | 1700 | 11
195+
(1 row)
196+
197+
--
198+
-- Add coverage for RowCompare quals whose rhs row has a NULL that ends scan
199+
--
200+
explain (costs off)
201+
SELECT proname, proargtypes, pronamespace
202+
FROM pg_proc
203+
WHERE proname = 'abs' AND (proname, proargtypes) < ('abs', NULL)
204+
ORDER BY proname, proargtypes, pronamespace;
205+
QUERY PLAN
206+
-------------------------------------------------------------------------------------------------------------
207+
Index Only Scan using pg_proc_proname_args_nsp_index on pg_proc
208+
Index Cond: ((ROW(proname, proargtypes) < ROW('abs'::name, NULL::oidvector)) AND (proname = 'abs'::name))
209+
(2 rows)
210+
211+
SELECT proname, proargtypes, pronamespace
212+
FROM pg_proc
213+
WHERE proname = 'abs' AND (proname, proargtypes) < ('abs', NULL)
214+
ORDER BY proname, proargtypes, pronamespace;
215+
proname | proargtypes | pronamespace
216+
---------+-------------+--------------
217+
(0 rows)
218+
219+
--
220+
-- Add coverage for backwards scan RowCompare quals whose rhs row has a NULL
221+
-- that ends scan
222+
--
223+
explain (costs off)
224+
SELECT proname, proargtypes, pronamespace
225+
FROM pg_proc
226+
WHERE proname = 'abs' AND (proname, proargtypes) > ('abs', NULL)
227+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC;
228+
QUERY PLAN
229+
-------------------------------------------------------------------------------------------------------------
230+
Index Only Scan Backward using pg_proc_proname_args_nsp_index on pg_proc
231+
Index Cond: ((ROW(proname, proargtypes) > ROW('abs'::name, NULL::oidvector)) AND (proname = 'abs'::name))
232+
(2 rows)
233+
234+
SELECT proname, proargtypes, pronamespace
235+
FROM pg_proc
236+
WHERE proname = 'abs' AND (proname, proargtypes) > ('abs', NULL)
237+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC;
238+
proname | proargtypes | pronamespace
239+
---------+-------------+--------------
240+
(0 rows)
241+
242+
--
243+
-- Add coverage for recheck of > key following array advancement on previous
244+
-- (left sibling) page that used a high key whose attribute value corresponding
245+
-- to the > key was -inf (due to being truncated when the high key was created).
246+
--
247+
-- XXX This relies on the assumption that tenk1_thous_tenthous has a truncated
248+
-- high key "(183, -inf)" on the first page that we'll scan. The test will only
249+
-- provide useful coverage when the default 8K BLCKSZ is in use.
250+
--
251+
explain (costs off)
252+
SELECT thousand, tenthous
253+
FROM tenk1
254+
WHERE thousand IN (182, 183) AND tenthous > 7550;
255+
QUERY PLAN
256+
---------------------------------------------------------------------------------
257+
Index Only Scan using tenk1_thous_tenthous on tenk1
258+
Index Cond: ((thousand = ANY ('{182,183}'::integer[])) AND (tenthous > 7550))
259+
(2 rows)
260+
261+
SELECT thousand, tenthous
262+
FROM tenk1
263+
WHERE thousand IN (182, 183) AND tenthous > 7550;
264+
thousand | tenthous
265+
----------+----------
266+
182 | 8182
267+
182 | 9182
268+
183 | 8183
269+
183 | 9183
270+
(4 rows)
271+
145272
--
146273
-- Add coverage for optimization of backwards scan index descents
147274
--

‎src/test/regress/expected/create_index.out

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2428,6 +2428,19 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 < (-1)::bigint
24282428
---------
24292429
(0 rows)
24302430

2431+
explain (costs off)
2432+
SELECT unique1 FROM tenk1 WHERE (thousand, tenthous) > (NULL, 5);
2433+
QUERY PLAN
2434+
-----------------------------------------------------------------
2435+
Index Scan using tenk1_thous_tenthous on tenk1
2436+
Index Cond: (ROW(thousand, tenthous) > ROW(NULL::integer, 5))
2437+
(2 rows)
2438+
2439+
SELECT unique1 FROM tenk1 WHERE (thousand, tenthous) > (NULL, 5);
2440+
unique1
2441+
---------
2442+
(0 rows)
2443+
24312444
--
24322445
-- Check elimination of constant-NULL subexpressions
24332446
--

‎src/test/regress/sql/btree_index.sql

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -110,6 +110,85 @@ SELECT b.*
110110
FROM bt_f8_heap b
111111
WHERE b.seqno = '4500'::float8;
112112

113+
--
114+
-- Add coverage of RowCompare quals whose row omits a column ("proargtypes")
115+
-- that's after the first column, but before the final column. The scan's
116+
-- initial positioning strategy must become >= here (it's not the > strategy,
117+
-- since the absence of "proargtypes" makes that tighter constraint unsafe).
118+
--
119+
explain (costs off)
120+
SELECT proname, proargtypes, pronamespace
121+
FROM pg_proc
122+
WHERE (proname, pronamespace) > ('abs', 0)
123+
ORDER BY proname, proargtypes, pronamespace LIMIT 1;
124+
125+
SELECT proname, proargtypes, pronamespace
126+
FROM pg_proc
127+
WHERE (proname, pronamespace) > ('abs', 0)
128+
ORDER BY proname, proargtypes, pronamespace LIMIT 1;
129+
130+
--
131+
-- Similar to the previous test case, but this time it's a backwards scan
132+
-- using a < RowCompare. Must use the <= strategy (and not the < strategy).
133+
--
134+
explain (costs off)
135+
SELECT proname, proargtypes, pronamespace
136+
FROM pg_proc
137+
WHERE (proname, pronamespace) < ('abs', 1_000_000)
138+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC LIMIT 1;
139+
140+
SELECT proname, proargtypes, pronamespace
141+
FROM pg_proc
142+
WHERE (proname, pronamespace) < ('abs', 1_000_000)
143+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC LIMIT 1;
144+
145+
--
146+
-- Add coverage for RowCompare quals whose rhs row has a NULL that ends scan
147+
--
148+
explain (costs off)
149+
SELECT proname, proargtypes, pronamespace
150+
FROM pg_proc
151+
WHERE proname = 'abs' AND (proname, proargtypes) < ('abs', NULL)
152+
ORDER BY proname, proargtypes, pronamespace;
153+
154+
SELECT proname, proargtypes, pronamespace
155+
FROM pg_proc
156+
WHERE proname = 'abs' AND (proname, proargtypes) < ('abs', NULL)
157+
ORDER BY proname, proargtypes, pronamespace;
158+
159+
--
160+
-- Add coverage for backwards scan RowCompare quals whose rhs row has a NULL
161+
-- that ends scan
162+
--
163+
explain (costs off)
164+
SELECT proname, proargtypes, pronamespace
165+
FROM pg_proc
166+
WHERE proname = 'abs' AND (proname, proargtypes) > ('abs', NULL)
167+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC;
168+
169+
SELECT proname, proargtypes, pronamespace
170+
FROM pg_proc
171+
WHERE proname = 'abs' AND (proname, proargtypes) > ('abs', NULL)
172+
ORDER BY proname DESC, proargtypes DESC, pronamespace DESC;
173+
174+
--
175+
-- Add coverage for recheck of > key following array advancement on previous
176+
-- (left sibling) page that used a high key whose attribute value corresponding
177+
-- to the > key was -inf (due to being truncated when the high key was created).
178+
--
179+
-- XXX This relies on the assumption that tenk1_thous_tenthous has a truncated
180+
-- high key "(183, -inf)" on the first page that we'll scan. The test will only
181+
-- provide useful coverage when the default 8K BLCKSZ is in use.
182+
--
183+
explain (costs off)
184+
SELECT thousand, tenthous
185+
FROM tenk1
186+
WHERE thousand IN (182, 183) AND tenthous > 7550;
187+
188+
SELECT thousand, tenthous
189+
FROM tenk1
190+
WHERE thousand IN (182, 183) AND tenthous > 7550;
191+
113192
--
114193
-- Add coverage for optimization of backwards scan index descents
115194
--

‎src/test/regress/sql/create_index.sql

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -931,6 +931,11 @@ SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 < (-1)::bigint
931931

932932
SELECT unique1 FROM tenk1 WHERE unique1 IN (1, 42, 7) and unique1 < (-1)::bigint;
933933

934+
explain (costs off)
935+
SELECT unique1 FROM tenk1 WHERE (thousand, tenthous) > (NULL, 5);
936+
937+
SELECT unique1 FROM tenk1 WHERE (thousand, tenthous) > (NULL, 5);
938+
934939
--
935940
-- Check elimination of constant-NULL subexpressions
936941
--

0 commit comments

Comments
 (0)