Horton

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

Alena Rybakina <a.rybakina@postgrespro.ru>

View thread
From: Alena Rybakina <a.rybakina@postgrespro.ru>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Matthias van de Meent <boekewurm+postgres@gmail.com>, 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-03-27T22:03:53Z
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 →

  1. nbtree: Always set skipScan flag on rescan.

  2. meson: Build numeric.c with -ftree-vectorize.

  3. Fix "variable not found in subplan target lists" in semijoin de-duplication.

  4. Revert "nbtree: Remove useless row compare arg."

  5. nbtree: Remove useless row compare arg.

  6. Prevent premature nbtree array advancement.

  7. nbtree: tighten up array recheck rules.

  8. Avoid treating nonrequired nbtree keys as required.

  9. Adjust overstrong nbtree skip array assertion.

  10. Make NULL tuple values always advance skip arrays.

  11. Avoid extra index searches through preprocessing.

  12. Improve nbtree skip scan primitive scan scheduling.

  13. Further optimize nbtree search scan key comparisons.

  14. Add nbtree skip scan optimization.

  15. Improve nbtree array primitive scan scheduling.

  16. nbtree: Make BTMaxItemSize into object-like macro.

  17. Show index search count in EXPLAIN ANALYZE, take 2.

  18. Make parallel nbtree index scans use an LWLock.

  19. Show index search count in EXPLAIN ANALYZE.

  20. Avoid nbtree parallel scan currPos confusion.

  21. nbtree: Remove useless 'strat' local variable.

  22. Normalize nbtree truncated high key array behavior.

  23. Refactor handling of nbtree array redundancies.

  24. Fix nbtree pgstats accounting with parallel scans.

  25. Avoid parallel nbtree index scan hangs with SAOPs.

  26. Show Parallel Bitmap Heap Scan worker stats in EXPLAIN ANALYZE

  27. Enhance nbtree ScalarArrayOp execution.

  28. Skip checking of scan keys required for directional scan in B-tree

  29. Instead of using a numberOfRequiredKeys count to distinguish required

Hi!

On 26.03.2025 02:45, Peter Geoghegan wrote:
> On Sat, Mar 22, 2025 at 1:47 PM Peter Geoghegan<pg@bowt.ie>  wrote:
>> Attached is v30, which fully replaces the pstate.prechecked
>> optimization with the new _bt_skip_ikeyprefix optimization (which now
>> appears in v30-0002-Lower-nbtree-skip-array-maintenance-overhead.patch,
>> and not in 0003-*, due to my committing the primscan scheduling patch
>> just now).
> Attached is v31, which has a much-improved _bt_skip_ikeyprefix (which
> I've once again renamed, this time to _bt_set_startikey).
>
I reviewed your first patch and noticed that you added the ability to 
define new quals if the first column isn't usedin the query.

I replied an example like this:

CREATE TABLE sales ( id SERIAL PRIMARY KEY, region TEXT, product TEXT, 
year INT );

INSERT INTO sales (region, product, year) SELECT CASE WHEN i % 4 <= 1 
THEN 'North' WHEN i % 4 <= 2 THEN 'South' WHEN i % 4 <= 3 THEN 'East' 
ELSE 'West' END, CASE WHEN random() > 0.5 THEN 'Laptop' ELSE 'Phone' 
END, 2023 FROM generate_series(1, 100000) AS i;

vacuum analyze;

CREATE INDEX sales_idx ON sales (region, product, year);

EXPLAIN ANALYZE SELECT * FROM sales WHERE product = 'Laptop' AND year = 
2023;

master gives the query plan with SeqScan:

QUERY PLAN 
--------------------------------------------------------------------------------------------------------------- 
Seq Scan on sales (cost=0.00..2137.00 rows=49703 width=19) (actual 
time=0.035..31.438 rows=50212.00 loops=1) Filter: ((product = 
'Laptop'::text) AND (year = 2023)) Rows Removed by Filter: 49788 
Buffers: shared hit=637 Planning: Buffers: shared hit=35 Planning Time: 
0.695 ms Execution Time: 33.942 ms (8 rows)

Your patch sets fair costs for it and it helps take into account index 
scan path and in my opinion it is perfect!)

QUERY PLAN 
--------------------------------------------------------------------------------------------------------------------------------- 
Bitmap Heap Scan on sales (cost=652.46..2031.86 rows=49493 width=19) 
(actual time=18.039..33.723 rows=49767.00 loops=1) Recheck Cond: 
((product = 'Laptop'::text) AND (year = 2023)) Heap Blocks: exact=637 
Buffers: shared hit=642 read=50 -> Bitmap Index Scan on sales_idx 
(cost=0.00..640.09 rows=49493 width=0) (actual time=17.756..17.756 
rows=49767.00 loops=1) Index Cond: ((product = 'Laptop'::text) AND (year 
= 2023)) Index Searches: 4 Buffers: shared hit=5 read=50 Planning: 
Buffers: shared hit=55 read=1 Planning Time: 0.984 ms Execution Time: 
36.940 ms

I think it would be useful to show information that we used an index 
scan but at the same time we skipped the "region" column and I assume we 
should output how many distinct values the "region" column had.

For example it will look like this "*Skip Scan on region (4 distinct 
values)"*:

QUERY PLAN 
--------------------------------------------------------------------------------------------------------------------------------- 
Bitmap Heap Scan on sales (cost=652.46..2031.86 rows=49493 width=19) 
(actual time=18.039..33.723 rows=49767.00 loops=1) Recheck Cond: 
((product = 'Laptop'::text) AND (year = 2023)) Heap Blocks: exact=637 
Buffers: shared hit=642 read=50 -> Bitmap Index Scan on sales_idx 
(cost=0.00..640.09 rows=49493 width=0) (actual time=17.756..17.756 
rows=49767.00 loops=1) Index Cond: ((product = 'Laptop'::text) AND (year 
= 2023)) *Skip Scan on region (4 distinct values)* Index Searches: 4 
Buffers: shared hit=5 read=50 Planning: Buffers: shared hit=55 read=1 
Planning Time: 0.984 ms Execution Time: 36.940 ms

What do you think?

I didn't see any regression tests. Maybe we should add some tests? To be 
honest I didn't see it mentioned in the commit message but I might have 
missed something.

-- 
Regards,
Alena Rybakina
Postgres Professional