Re: [PATCH] kNN for btree

On Wed, Mar 4, 2020 at 2:39 PM Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> On Wed, Mar 4, 2020 at 4:58 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> > On Mon, Mar 2, 2020 at 1:27 PM Alexander Korotkov
> > <a(dot)korotkov(at)postgrespro(dot)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