Re: [PATCH] kNN for btree

On Wed, Mar 4, 2020 at 2:39 PM Alexander Korotkov
<a.korotkov@postgrespro.ru> wrote:
> On Wed, Mar 4, 2020 at 4:58 AM Peter Geoghegan <pg@bowt.ie> wrote:
> > On Mon, Mar 2, 2020 at 1:27 PM Alexander Korotkov
> > <a.korotkov@postgrespro.ru> wrote:
> > > I've rebased the patchset to the current master and made some
> > > refactoring.  I hope it would be possible to bring it to committable
> > > shape during this CF.  This need more refactoring though.
> >
> > This patch doesn't change anything about the B-Tree on-disk format -- right?
>
> Yes, this is correct.  No on-disk format changes, just new scanning strategy.

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.

So, I'm marking this patch RWF.  We should try re-implement this for v14.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company