postgres.email
❮

[PATCH] btree merge scan proposal

  • Jump to comment-1
    Alexandre Felipe<alexandre.felipe@tpro.io>
    Jan 30, 2026, 9:32 AM UTC
    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 idxtupread 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_scanidx_tup_readidx_tup_fetch
    -51010
    +5224224
    (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.iohttps://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]
    View in PostgreSQL Archives →