[PATCH] btree merge scan proposal

Hello hackers,

I am proposing a new access method, that combines skip index scan and K-way merge sort, query data from a limited distinct prefixes of the index that within each prefix is sorted.

The attached patch adds a test case for the upcoming implementation, and gives proofs that the access method can work efficiently.

It will

SELECT * FROM table(with N)
WHERE filter(leading_columns)
ORDER BY natural order after dropping leading columns
LIMIT BY M

The idx_tup_read currently O(N), my proposal is to make it O(M).

I am showing an example with a grid
WHERE indexrelname = 'btree_merge_test_idx';

idx_scan | idx_tup_read | idx_tup_fetch
----------+--------------+---------------
- 5 | 10 | 10
+ 5 | 224 | 224
(1 row)

I have brought this up in 2022, at the time after reading about how demanding the review process could be I gave up on the idea. I have not worked much on database related stuff since then. But I would say that I learned a lot about the internals of postgres with Vinicius Schmidt that joined our team recently.

Loosely, this is how the algorithm should work

Until M live tuples are retrieved
Until M tuples are retrieved: Begin Fetch index
For each distinct prefix, read 1 page of index tuples
Filter the index tuples
Merge index tuples for the obtained pages
Begin fetch heap
Read the rows as required, filter out dead tuples
Fetch next page of each prefix

Using as baseline commit bb26a81ee28c9d9c64e6f233fafa2792768ece1b.

Kind Regards,

Alexandre Felipe

Research & Development Engineer

Phone: +353 (0) 1 9696 400

Visit: <https://info.tpro.io/> https://info.tpro.io<https://info.tpro.io/>

Talk to our team: <https://info.tpro.io/> https://info.tpro.io/contact/book-a-demo

[cid:1b0a8822-5677-4656-8709-4424ae24bb92]