Re: [PATCH] kNN for btree

From: "Anton A(dot) Melnikov" <a(dot)melnikov(at)postgrespro(dot)ru>
To: Peter Geoghegan <pg(at)bowt(dot)ie>, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
Cc: Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>, Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru>, Thomas Munro <thomas(dot)munro(at)gmail(dot)com>, David Steele <david(at)pgmasters(dot)net>, Anastasia Lubennikova <lubennikovaav(at)gmail(dot)com>, PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Re: [PATCH] kNN for btree
Date: 2024-01-15 08:11:55
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers


On 16.03.2020 16:17, Alexander Korotkov wrote:
> After another try to polish this patch I figured out that the way it's
> implemented is unnatural. I see the two reasonable ways to implement
> knn for B-tree, but current implementation matches none of them.
> 1) Implement knn as two simultaneous scans over B-tree: forward and
> backward. It's similar to what current patchset does. But putting
> this logic to B-tree seems artificial. What B-tree does here is still
> unidirectional scan. On top of that we merge results of two
> unidirectional scans. The appropriate place to do this high-level
> work is IndexScan node or even Optimizer/Executor (Merge node over to
> IndexScan nodes), but not B-tree itself.
> 2) Implement arbitrary scans in B-tree using priority queue like GiST
> and SP-GiST do. That would lead to much better support for KNN. We
> can end up in supporting interesting cases like "ORDER BY col1 DESC,
> col2 <> val1, col2 ASC" or something. But that's requires way more
> hacking in B-tree core.

I've rebased and fixed the 17th version of this patch to work
with current master as a starting point for further development.

At first i'm going to implement p.1). I think it's preferable for now
because it seems easier and faster to get a working version.

If there are any ideas pro and contra would be glad to discuss them.

With the best wishes!

Anton A. Melnikov
Postgres Professional:
The Russian Postgres Company

Attachment Content-Type Size
v18-0001-Introduce-IndexAmRoutine.ammorderbyopfirstcol.patch text/x-patch 9.1 KB
v18-0002-Allow-ordering-by-operator-in-ordered-indexes.patch text/x-patch 4.7 KB
v18-0003-Extract-BTScanState-from-BTScanOpaqueData.patch text/x-patch 49.6 KB
v18-0004-Move-scalar-distance-operators-from-btree_gist-to-co.patch text/x-patch 94.4 KB
v18-0005-Add-knn-support-to-btree-indexes.patch text/x-patch 128.6 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Bertrand Drouvot 2024-01-15 08:49:10 Re: Test slots invalidations in only if dead rows are removed
Previous Message Alexander Korotkov 2024-01-15 07:56:32 Re: POC: GROUP BY optimization