[PATCH] kNN for btree

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] kNN for btree

Nikita Glukhov
Hi hackers,

I'd like to present a series of patches that implements k-Nearest
Neighbors (kNN)
search forbtree, which can be usedto speed up ORDER BY distance queries
like this:
SELECT * FROM eventsORDER BY date <-> '2000-01-01'::date ASC LIMIT 100;
Now only GiST supports kNN, but kNN on btree can be emulated using
contrib/btree_gist.


Scanning algorithm
==================

Algorithm is very simple: we use bidirectional B-tree index scan
starting at the point
from which we measure the distance(target point).At each step, we advance
this scan in the directionthat has the nearest point.  Butwhen the
target point
does not fall into the scannedrange, we don't even need to
useabidirectional
scan here --- wecan use ordinaryunidirectional scaninthe right direction.


Performance results
===================

Test database istaken from original kNN-GiST presentation (PGCon2010).

Test query

SELECT * FROM events ORDER BY date <-> '1957-10-04'::date ASC LIMIT k;

can be optimizedto the next rather complicated UNION form, whichnolonger
requireskNN:

WITH
   t1 AS (SELECT * FROM events WHERE date >= '1957-10-04'::date ORDER BY
date ASC  LIMIT k),
   t2 AS (SELECT * FROM events WHERE date < '1957-10-04'::date ORDER BY
date DESC LIMIT k),
t  AS (SELECT * FROM t1 UNION SELECT * FROM t2)
SELECT * FROM t ORDER BY date <-> '1957-10-04'::date ASC LIMIT k;


In each cell of this table shown query execution time in milliseconds and
the number of accessed blocks:


    k   | kNN-btree   | kNN-GiST|  Opt. query   | Seq.scan
        |              | (btree_gist) |  withUNION |  with sort
-------|--------------|--------------|---------------|------------
      1 | 0.0414| 0.0794|   0.0608 |41.11824
     10 |  0.0487 |  0.0919 |   0.09717 |41.81824
    100 |  0.10747 |  0.192    52|   0.342104 |42.31824
   1000 |  0.735573 |  0.913   650 | 2.9701160 |43.51824
  10000 |  5.070 5622|  6.240 6760|  36.300 11031 |  54.1 1824
100000 | 49.600 51608| 61.900 64194 | 295.100 94980| 115.0 1824


As you can see, kNN-btree can be two times faster than kNN-GiST(btree_gist)
when k < 1000,but the number of blocks readis roughly the same.


Implementation details
======================

A brief description is given below for each of the patches:

1. Introduce amcanorderbyop() function

This patch transformsexisting boolean AMpropertyamcanorderbyop into a
method
(function pointer).This is necessarybecause, unlike GiST,kNN for
btreesupports
only a one ordering operator onthe first index column and we need a
different pathkey
matching logicfor btree (there was acorresponding comment
inmatch_pathkeys_to_index()).
GiST-specific logic has been moved from match_pathkeys_to_index() to
gistcanorderbyop().

2. Extract substructure BTScanState from BTScanOpaque

This refactoringis necessary for bidirectional kNN-scanimplementation. Now,
BTScanOpaque'ssubstructure BTScanState containing only thefields related
toscanpositionis passed to some functions where thewhole BTScanOpaque
waspassedpreviously.

3. Extract get_index_column_opclass(),
get_opclass_opfamily_and_input_type().

Extracted two simple common functions usedingistproperty() and
btproperty() (see the next patch).

4. Add kNN supportto btree

   * Added additional optional BTScanState to BTScanOpaque for
bidirectional kNN scan.
   * Implemented bidirectional kNN scan.
   * Implemented logic for selecting kNN strategy
* Implemented btcanorderbyop(), updated btproperty() and btvalidate()

B-tree user interface functions have not been altered because ordering
operators
are used directly.

5. Add distance operators for sometypes

These operators for integer, float, date, time, timestamp, interval,
cash and oidtypes
havebeencopied fromcontrib/btree_gistand added to the existing btree
opclasses
as ordering operators.  Their btree_gist duplicates areremoved in the
next patch.

6. Remove duplicate distance operators from contrib/btree_gist.

References to their own distance operators in btree_gist opclassesare
replaced
with references to the built-in operatorsand thanduplicate operators are
dropped.
But if the user is using somewhere these operators, upgrade of btree_gist
from 1.3 to 1.4 should fail.

7. Add regression tests for btree kNN.

Tests were added only after the built-in distance operators were added.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

0001-introduce-amcanorderby-function-v01.patch (14K) Download Attachment
0002-extract-structure-BTScanState-v01.patch (38K) Download Attachment
0003-extract-get_index_column_opclass-and-get_opclass_opfamily_and_input_type-v01.patch (5K) Download Attachment
0004-add-kNN-support-to-btree-v01.patch (39K) Download Attachment
0005-add-distance-operators-v01.patch (21K) Download Attachment
0006-remove-distance-operators-from-btree_gist-v01.patch (101K) Download Attachment
0007-add-regression-tests-for-kNN-btree-v01.patch (15K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Nikita Glukhov
Sorry for the broken formatting in my previous message.
Below is a corrected version of this message.


I'd like to present a series of patches that implements k-Nearest Neighbors
(kNN) search for btree, which can be used to speed up ORDER BY distance
queries like this:
SELECT * FROM events ORDER BY date <-> '2000-01-01'::date ASC LIMIT 100;

Now only GiST supports kNN, but kNN on btree can be emulated using
contrib/btree_gist.


Scanning algorithm
==================

Algorithm is very simple: we use bidirectional B-tree index scan starting at
the point from which we measure the distance (target point).  At each step,
we advance this scan in the direction that has the  nearest point.  But when
the target point does not fall into the scanned range, we don't even need to
use a bidirectional scan here --- we can use ordinary unidirectional scan
in the right direction.


Performance results
===================

Test database is taken from original kNN-GiST presentation (PGCon 2010).

Test query

SELECT * FROM events ORDER BY date <-> '1957-10-04'::date ASC LIMIT k;

can be optimized to the next rather complicated UNION form,
which no longer requires kNN:

WITH
     t1 AS (SELECT * FROM events WHERE date >= '1957-10-04'::date
            ORDER BY date ASC  LIMIT k),
     t2 AS (SELECT * FROM events WHERE date <  '1957-10-04'::date
            ORDER BY date DESC LIMIT k),
     t  AS (SELECT * FROM t1 UNION SELECT * FROM t2)
SELECT * FROM t ORDER BY date <-> '1957-10-04'::date ASC LIMIT k;


In each cell of this table shown query execution time in milliseconds and
the number of accessed blocks:


      k  |  kNN-btree   |  kNN-GiST    |  Opt. query   |  Seq. scan
         |              | (btree_gist) |  with UNION   |  with sort
--------|--------------|--------------|---------------|------------
       1 |  0.041     4 |  0.079     4 |   0.060     8 |  41.1 1824
      10 |  0.048     7 |  0.091     9 |   0.097    17 |  41.8 1824
     100 |  0.107    47 |  0.192    52 |   0.342   104 |  42.3 1824
    1000 |  0.735   573 |  0.913   650 |   2.970  1160 |  43.5 1824
   10000 |  5.070  5622 |  6.240  6760 |  36.300 11031 |  54.1 1824
  100000 | 49.600 51608 | 61.900 64194 | 295.100 94980 | 115.0 1824


As you can see, kNN-btree can be two times faster than kNN-GiST (btree_gist)
when k < 1000, but the number of blocks read is roughly the same.


Implementation details
======================

A brief description is given below for each of the patches:

1. Introduce amcanorderbyop() function

This patch transforms existing boolean AM property amcanorderbyop into a method
(function pointer).  This is necessary because, unlike GiST, kNN for btree
supports only a one ordering operator on the first index column and we need a
different pathkey matching logic for btree (there was a corresponding comment
in match_pathkeys_to_index()).  GiST-specific logic has been moved from
match_pathkeys_to_index() to gistcanorderbyop().

2. Extract substructure BTScanState from BTScanOpaque

This refactoring is necessary for bidirectional kNN-scan implementation.
Now, BTScanOpaque's substructure BTScanState containing only the fields
related to scan position is passed to some functions where the whole
BTScanOpaque was passed previously.

3. Extract get_index_column_opclass(), get_opclass_opfamily_and_input_type().

Extracted two simple common functions used in gistproperty() and
btproperty() (see the next patch).

4. Add kNN support to btree

   * Added additional optional BTScanState to BTScanOpaque for
     bidirectional kNN scan.
   * Implemented bidirectional kNN scan.
   * Implemented logic for selecting kNN strategy
   * Implemented btcanorderbyop(), updated btproperty() and btvalidate()

B-tree user interface functions have not been altered because ordering
operators are used directly.

5. Add distance operators for some types

These operators for integer, float, date, time, timestamp, interval, cash and
oid types have been copied from contrib/btree_gist and added to the existing
btree opclasses as ordering operators.  Their btree_gist duplicates are removed
in the next patch.

6. Remove duplicate distance operators from contrib/btree_gist.

References to their own distance operators in btree_gist opclasses are
replaced with references to the built-in operators and than duplicate
operators are dropped.  But if the user is using somewhere these operators,
upgrade of btree_gist from 1.3 to 1.4 would fail.

7. Add regression tests for btree kNN.

Tests were added only after the built-in distance operators were added.


--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company




--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Nikita Glukhov
Attached v02 version of patches (rebased onto HEAD).

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

0001-introduce-amcanorderby-function-v02.patch (14K) Download Attachment
0002-extract-structure-BTScanState-v02.patch (38K) Download Attachment
0003-extract-get_index_column_opclass-and-get_opclass_opfamily_and_input_type-v02.patch (5K) Download Attachment
0004-add-kNN-support-to-btree-v02.patch (39K) Download Attachment
0005-add-distance-operators-v02.patch (18K) Download Attachment
0006-remove-distance-operators-from-btree_gist-v02.patch (101K) Download Attachment
0007-add-regression-tests-for-kNN-btree-v02.patch (15K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
Hi, Nikita!

I have assigned as a reviewer for this patchset.  I took a fist look to these patches.
At first, I'd like to notice that it's very cool that you picked up this work.  I frequently hear people complains about lack of this feature.

     k  |  kNN-btree   |  kNN-GiST    |  Opt. query   |  Seq. scan
        |              | (btree_gist) |  with UNION   |  with sort
--------|--------------|--------------|---------------|------------
      1 |  0.041     4 |  0.079     4 |   0.060     8 |  41.1 1824
     10 |  0.048     7 |  0.091     9 |   0.097    17 |  41.8 1824
    100 |  0.107    47 |  0.192    52 |   0.342   104 |  42.3 1824
   1000 |  0.735   573 |  0.913   650 |   2.970  1160 |  43.5 1824
  10000 |  5.070  5622 |  6.240  6760 |  36.300 11031 |  54.1 1824
 100000 | 49.600 51608 | 61.900 64194 | 295.100 94980 | 115.0 1824

These results looks quite expected.  KNN-btree uses about half of blocks in comparison with UNION query, and it's more than twice faster.  In comparison with kNN-GiST there is still some win. 

1. Introduce amcanorderbyop() function

This patch transforms existing boolean AM property amcanorderbyop into a method
(function pointer).  This is necessary because, unlike GiST, kNN for btree
supports only a one ordering operator on the first index column and we need a
different pathkey matching logic for btree (there was a corresponding comment
in match_pathkeys_to_index()).  GiST-specific logic has been moved from
match_pathkeys_to_index() to gistcanorderbyop().

I'm not very excited about this design of amcanorderbyop callback.  Introducing new callback from index access method to the planner should imply quite good flexibility to the future.  In this particular signature of callback I see no potential future use-cases than your implementation for btree.  We could just add amcanorderbyonlyfisrtop property and that would give us same level of flexibility I think.
With existing index types, we could cover much more orderings that we currently do.  Some of possible cases:
1) "ORDER BY col" for btree_gist, SP-GiST text_ops
2) "ORDER BY col1, col2 <-> const" for btree_gist
3) "ORDER BY col1, col2 <-> const" for btree

I understand that #3 is quite hard task and I don't ask you to implement it now.  But it would be nice if some day we decide to add #3, we wouldn't have to change IndexAmRoutine definition.

My idea is that we need more general redesign of specifying ordering which index can produce.  Ideally, we should replace amcanorder, amcanbackward and amcanorderbyop with single callback.  Such callback should take a list of pathkeys and return number of leading pathkeys index could satisfy (with corresponding information for index scan).  I'm not sure that other hackers would agree with such design, but I'm very convinced that we need something of this level of extendability.  Otherwise we would have to hack our planner <-> index_access_method interface each time we decide to cover another index produced ordering.

6. Remove duplicate distance operators from contrib/btree_gist.

References to their own distance operators in btree_gist opclasses are
replaced with references to the built-in operators and than duplicate
operators are dropped.  But if the user is using somewhere these operators,
upgrade of btree_gist from 1.3 to 1.4 would fail.

The query in "btree_gist--1.3--1.4.sql" which directly touches system catalogue to update opfamilies looks too hackery.  I think we shouldn't use such queries until we have no other choice.
In this particular case we can update opfamilies using legal mechanism "ALTER OPERATOR FAMILY name USING index_method ADD/DROP ... " (note that operator name could be schema-qualified if needed).  This way wouldn't be that brief, but it is much more correct. 

Also this like catch my eyes.
info->amcanorderbyop = (void (*)()) amroutine->amcanorderbyop;
It's not necessary to use cast here.  For instance, we don't use cast for amcostestimate.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Robert Haas
On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
<[hidden email]> wrote:
> My idea is that we need more general redesign of specifying ordering which
> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
> amcanorderbyop with single callback.  Such callback should take a list of
> pathkeys and return number of leading pathkeys index could satisfy (with
> corresponding information for index scan).  I'm not sure that other hackers
> would agree with such design, but I'm very convinced that we need something
> of this level of extendability.  Otherwise we would have to hack our planner
> <-> index_access_method interface each time we decide to cover another index
> produced ordering.

Yeah.  I'm not sure if that's exactly the right idea.  But it seems
like we need something.

>> info->amcanorderbyop = (void (*)()) amroutine->amcanorderbyop;
>
> It's not necessary to use cast here.  For instance, we don't use cast for
> amcostestimate.

In fact, it's bad to use the cast here, because if in future the
signature of one of amroutine->amcanorderbyop is changed and
info->amcanorderbyop is not changed to match, then the cast will
prevent a compiler warning, but at runtime you may crash.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Tom Lane-2
Robert Haas <[hidden email]> writes:

> On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
> <[hidden email]> wrote:
>> My idea is that we need more general redesign of specifying ordering which
>> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
>> amcanorderbyop with single callback.  Such callback should take a list of
>> pathkeys and return number of leading pathkeys index could satisfy (with
>> corresponding information for index scan).  I'm not sure that other hackers
>> would agree with such design, but I'm very convinced that we need something
>> of this level of extendability.  Otherwise we would have to hack our planner
>> <-> index_access_method interface each time we decide to cover another index
>> produced ordering.

> Yeah.  I'm not sure if that's exactly the right idea.  But it seems
> like we need something.

That's definitely not exactly the right idea, because using it would
require the core planner to play twenty-questions trying to guess which
pathkeys the index can satisfy.  ("Can you satisfy some prefix of this
pathkey list?  How about that one?")  It could be sensible to have a
callback that's called once per index and hands back a list of pathkey
lists that represent interesting orders the index could produce, which
could be informed by looking aside at the PlannerInfo contents to see
what is likely to be relevant to the query.

But even so, I'm not convinced that that is a better design or more
maintainable than the current approach.  I fear that it will lead to
duplicating substantial amounts of code and knowledge into each index AM,
which is not an improvement; and if anything, that increases the risk of
breaking every index AM anytime you want to introduce some fundamentally
new capability in the area.  Now that it's actually practical to have
out-of-core index AMs, that's a bigger concern than it might once have
been.

Also see the discussion that led up to commit ed0097e4f.  Users objected
the last time we tried to make index capabilities opaque at the SQL level,
so they're not going to like a design that tries to hide that information
even from the core C code.

                        regards, tom lane


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Robert Haas
On Thu, Feb 16, 2017 at 10:59 AM, Tom Lane <[hidden email]> wrote:

> Robert Haas <[hidden email]> writes:
>> On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
>> <[hidden email]> wrote:
>>> My idea is that we need more general redesign of specifying ordering which
>>> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
>>> amcanorderbyop with single callback.  Such callback should take a list of
>>> pathkeys and return number of leading pathkeys index could satisfy (with
>>> corresponding information for index scan).  I'm not sure that other hackers
>>> would agree with such design, but I'm very convinced that we need something
>>> of this level of extendability.  Otherwise we would have to hack our planner
>>> <-> index_access_method interface each time we decide to cover another index
>>> produced ordering.
>
>> Yeah.  I'm not sure if that's exactly the right idea.  But it seems
>> like we need something.
>
> That's definitely not exactly the right idea, because using it would
> require the core planner to play twenty-questions trying to guess which
> pathkeys the index can satisfy.  ("Can you satisfy some prefix of this
> pathkey list?  How about that one?")  It could be sensible to have a
> callback that's called once per index and hands back a list of pathkey
> lists that represent interesting orders the index could produce, which
> could be informed by looking aside at the PlannerInfo contents to see
> what is likely to be relevant to the query.
>
> But even so, I'm not convinced that that is a better design or more
> maintainable than the current approach.  I fear that it will lead to
> duplicating substantial amounts of code and knowledge into each index AM,
> which is not an improvement; and if anything, that increases the risk of
> breaking every index AM anytime you want to introduce some fundamentally
> new capability in the area.  Now that it's actually practical to have
> out-of-core index AMs, that's a bigger concern than it might once have
> been.

Yeah, that's all true.  But I think Alexander is right that just
adding amcandoblah flags ad infinitum doesn't feel good either.  The
interface isn't really arm's-length if every new thing somebody wants
to do something new requires another flag.

> Also see the discussion that led up to commit ed0097e4f.  Users objected
> the last time we tried to make index capabilities opaque at the SQL level,
> so they're not going to like a design that tries to hide that information
> even from the core C code.

Discoverability is definitely important, but first we have to figure
out how we're going to make it work, and then we can work out how to
let users see how it works.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

David Steele
Hi Alexander,

On 2/16/17 11:20 AM, Robert Haas wrote:

> On Thu, Feb 16, 2017 at 10:59 AM, Tom Lane <[hidden email]> wrote:
>> Robert Haas <[hidden email]> writes:
>>> On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
>>> <[hidden email]> wrote:
>>>> My idea is that we need more general redesign of specifying ordering which
>>>> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
>>>> amcanorderbyop with single callback.  Such callback should take a list of
>>>> pathkeys and return number of leading pathkeys index could satisfy (with
>>>> corresponding information for index scan).  I'm not sure that other hackers
>>>> would agree with such design, but I'm very convinced that we need something
>>>> of this level of extendability.  Otherwise we would have to hack our planner
>>>> <-> index_access_method interface each time we decide to cover another index
>>>> produced ordering.
>>
>>> Yeah.  I'm not sure if that's exactly the right idea.  But it seems
>>> like we need something.
>>
>> That's definitely not exactly the right idea, because using it would
>> require the core planner to play twenty-questions trying to guess which
>> pathkeys the index can satisfy.  ("Can you satisfy some prefix of this
>> pathkey list?  How about that one?")  It could be sensible to have a
>> callback that's called once per index and hands back a list of pathkey
>> lists that represent interesting orders the index could produce, which
>> could be informed by looking aside at the PlannerInfo contents to see
>> what is likely to be relevant to the query.
>>
>> But even so, I'm not convinced that that is a better design or more
>> maintainable than the current approach.  I fear that it will lead to
>> duplicating substantial amounts of code and knowledge into each index AM,
>> which is not an improvement; and if anything, that increases the risk of
>> breaking every index AM anytime you want to introduce some fundamentally
>> new capability in the area.  Now that it's actually practical to have
>> out-of-core index AMs, that's a bigger concern than it might once have
>> been.
>
> Yeah, that's all true.  But I think Alexander is right that just
> adding amcandoblah flags ad infinitum doesn't feel good either.  The
> interface isn't really arm's-length if every new thing somebody wants
> to do something new requires another flag.
>
>> Also see the discussion that led up to commit ed0097e4f.  Users objected
>> the last time we tried to make index capabilities opaque at the SQL level,
>> so they're not going to like a design that tries to hide that information
>> even from the core C code.
>
> Discoverability is definitely important, but first we have to figure
> out how we're going to make it work, and then we can work out how to
> let users see how it works.

Reading through this thread I'm concerned that this appears to be a big
change making its first appearance in the last CF.  There is also the
need for a new patch and a general consensus of how to proceed.

I recommend moving this patch to 2017-07 or marking it RWF.

Thanks,
--
-David
[hidden email]


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
On Thu, Mar 2, 2017 at 5:57 PM, David Steele <[hidden email]> wrote:
Hi Alexander,

On 2/16/17 11:20 AM, Robert Haas wrote:
> On Thu, Feb 16, 2017 at 10:59 AM, Tom Lane <[hidden email]> wrote:
>> Robert Haas <[hidden email]> writes:
>>> On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
>>> <[hidden email]> wrote:
>>>> My idea is that we need more general redesign of specifying ordering which
>>>> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
>>>> amcanorderbyop with single callback.  Such callback should take a list of
>>>> pathkeys and return number of leading pathkeys index could satisfy (with
>>>> corresponding information for index scan).  I'm not sure that other hackers
>>>> would agree with such design, but I'm very convinced that we need something
>>>> of this level of extendability.  Otherwise we would have to hack our planner
>>>> <-> index_access_method interface each time we decide to cover another index
>>>> produced ordering.
>>
>>> Yeah.  I'm not sure if that's exactly the right idea.  But it seems
>>> like we need something.
>>
>> That's definitely not exactly the right idea, because using it would
>> require the core planner to play twenty-questions trying to guess which
>> pathkeys the index can satisfy.  ("Can you satisfy some prefix of this
>> pathkey list?  How about that one?")  It could be sensible to have a
>> callback that's called once per index and hands back a list of pathkey
>> lists that represent interesting orders the index could produce, which
>> could be informed by looking aside at the PlannerInfo contents to see
>> what is likely to be relevant to the query.
>>
>> But even so, I'm not convinced that that is a better design or more
>> maintainable than the current approach.  I fear that it will lead to
>> duplicating substantial amounts of code and knowledge into each index AM,
>> which is not an improvement; and if anything, that increases the risk of
>> breaking every index AM anytime you want to introduce some fundamentally
>> new capability in the area.  Now that it's actually practical to have
>> out-of-core index AMs, that's a bigger concern than it might once have
>> been.
>
> Yeah, that's all true.  But I think Alexander is right that just
> adding amcandoblah flags ad infinitum doesn't feel good either.  The
> interface isn't really arm's-length if every new thing somebody wants
> to do something new requires another flag.
>
>> Also see the discussion that led up to commit ed0097e4f.  Users objected
>> the last time we tried to make index capabilities opaque at the SQL level,
>> so they're not going to like a design that tries to hide that information
>> even from the core C code.
>
> Discoverability is definitely important, but first we have to figure
> out how we're going to make it work, and then we can work out how to
> let users see how it works.

Reading through this thread I'm concerned that this appears to be a big
change making its first appearance in the last CF.  There is also the
need for a new patch and a general consensus of how to proceed.
 
Yes, refactoring of amcanorder/amcanorderbyop should be very thoughtful.

I recommend moving this patch to 2017-07 or marking it RWF.

I agree. Done.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company 
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Nikita Glukhov
Attached 3rd version of the patches rebased onto the current master.

Changes from the previous version:
- Added support of INCLUDE columns to get_index_column_opclass() (1st patch).
- Added parallel kNN scan support.
- amcanorderbyop() was transformed into ammatchorderby() which takes a List of
  PathKeys and checks each of them with new function match_orderbyop_pathkey()
  extracted from match_pathkeys_to_index().  I think that this design can be
  used in the future to support a mix of ordinary and order-by-op PathKeys,
  but I am not sure.

On 09.03.2017 15:00, Alexander Korotkov wrote:
On Thu, Mar 2, 2017 at 5:57 PM, David Steele <[hidden email]> wrote:
Hi Alexander,

On 2/16/17 11:20 AM, Robert Haas wrote:
> On Thu, Feb 16, 2017 at 10:59 AM, Tom Lane <[hidden email]> wrote:
>> Robert Haas <[hidden email]> writes:
>>> On Thu, Feb 16, 2017 at 8:05 AM, Alexander Korotkov
>>> <[hidden email]> wrote:
>>>> My idea is that we need more general redesign of specifying ordering which
>>>> index can produce.  Ideally, we should replace amcanorder, amcanbackward and
>>>> amcanorderbyop with single callback.  Such callback should take a list of
>>>> pathkeys and return number of leading pathkeys index could satisfy (with
>>>> corresponding information for index scan).  I'm not sure that other hackers
>>>> would agree with such design, but I'm very convinced that we need something
>>>> of this level of extendability.  Otherwise we would have to hack our planner
>>>> <-> index_access_method interface each time we decide to cover another index
>>>> produced ordering.
>>
>>> Yeah.  I'm not sure if that's exactly the right idea.  But it seems
>>> like we need something.
>>
>> That's definitely not exactly the right idea, because using it would
>> require the core planner to play twenty-questions trying to guess which
>> pathkeys the index can satisfy.  ("Can you satisfy some prefix of this
>> pathkey list?  How about that one?")  It could be sensible to have a
>> callback that's called once per index and hands back a list of pathkey
>> lists that represent interesting orders the index could produce, which
>> could be informed by looking aside at the PlannerInfo contents to see
>> what is likely to be relevant to the query.
>>
>> But even so, I'm not convinced that that is a better design or more
>> maintainable than the current approach.  I fear that it will lead to
>> duplicating substantial amounts of code and knowledge into each index AM,
>> which is not an improvement; and if anything, that increases the risk of
>> breaking every index AM anytime you want to introduce some fundamentally
>> new capability in the area.  Now that it's actually practical to have
>> out-of-core index AMs, that's a bigger concern than it might once have
>> been.
>
> Yeah, that's all true.  But I think Alexander is right that just
> adding amcandoblah flags ad infinitum doesn't feel good either.  The
> interface isn't really arm's-length if every new thing somebody wants
> to do something new requires another flag.
>
>> Also see the discussion that led up to commit ed0097e4f.  Users objected
>> the last time we tried to make index capabilities opaque at the SQL level,
>> so they're not going to like a design that tries to hide that information
>> even from the core C code.
>
> Discoverability is definitely important, but first we have to figure
> out how we're going to make it work, and then we can work out how to
> let users see how it works.

Reading through this thread I'm concerned that this appears to be a big
change making its first appearance in the last CF.  There is also the
need for a new patch and a general consensus of how to proceed.
 
Yes, refactoring of amcanorder/amcanorderbyop should be very thoughtful.

I recommend moving this patch to 2017-07 or marking it RWF.

I agree. Done.

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

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

0001-Fix-get_index_column_opclass-v03.patch (1K) Download Attachment
0002-Introduce-ammatchorderby-function-v03.patch (21K) Download Attachment
0003-Extract-structure-BTScanState-v03.patch (44K) Download Attachment
0004-Add-kNN-support-to-btree-v03.patch (61K) Download Attachment
0005-Add-btree-distance-operators-v03.patch (79K) Download Attachment
0006-Remove-distance-operators-from-btree_gist-v03.patch (104K) Download Attachment
0007-Add-regression-tests-for-kNN-btree-v03.patch (29K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Dmitry Dolgov
> On Wed, Sep 26, 2018 at 5:41 PM Nikita Glukhov <[hidden email]> wrote:
>
> Attached 3rd version of the patches rebased onto the current master.
>
> Changes from the previous version:
> - Added support of INCLUDE columns to get_index_column_opclass() (1st patch).
> - Added parallel kNN scan support.
> - amcanorderbyop() was transformed into ammatchorderby() which takes a List of
>   PathKeys and checks each of them with new function match_orderbyop_pathkey()
>   extracted from match_pathkeys_to_index().  I think that this design can be
>   used in the future to support a mix of ordinary and order-by-op PathKeys,
>   but I am not sure.

Hi,

Unfortunately, the patch has some conflicts, could you rebase it? In the
meantime I'll move it to the next CF, hoping to have more reviewers for this
item.

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Nikita Glukhov

On 29.11.2018 18:24, Dmitry Dolgov wrote:

>> On Wed, Sep 26, 2018 at 5:41 PM Nikita Glukhov <[hidden email]> wrote:
>>
>> Attached 3rd version of the patches rebased onto the current master.
>>
>> Changes from the previous version:
>> - Added support of INCLUDE columns to get_index_column_opclass() (1st patch).
>> - Added parallel kNN scan support.
>> - amcanorderbyop() was transformed into ammatchorderby() which takes a List of
>>    PathKeys and checks each of them with new function match_orderbyop_pathkey()
>>    extracted from match_pathkeys_to_index().  I think that this design can be
>>    used in the future to support a mix of ordinary and order-by-op PathKeys,
>>    but I am not sure.
> Hi,
>
> Unfortunately, the patch has some conflicts, could you rebase it? In the
> meantime I'll move it to the next CF, hoping to have more reviewers for this
> item.
Attached 4th version of the patches rebased onto the current master.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

0001-Fix-get_index_column_opclass-v04.patch (1K) Download Attachment
0002-Introduce-ammatchorderby-function-v04.patch (22K) Download Attachment
0003-Extract-structure-BTScanState-v04.patch (45K) Download Attachment
0004-Add-kNN-support-to-btree-v04.patch (62K) Download Attachment
0005-Add-btree-distance-operators-v04.patch (82K) Download Attachment
0006-Remove-distance-operators-from-btree_gist-v04.patch (106K) Download Attachment
0007-Add-regression-tests-for-kNN-btree-v04.patch (30K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
Hi!

On Fri, Nov 30, 2018 at 3:02 PM Nikita Glukhov <[hidden email]> wrote:

> On 29.11.2018 18:24, Dmitry Dolgov wrote:
> >> On Wed, Sep 26, 2018 at 5:41 PM Nikita Glukhov <[hidden email]> wrote:
> >>
> >> Attached 3rd version of the patches rebased onto the current master.
> >>
> >> Changes from the previous version:
> >> - Added support of INCLUDE columns to get_index_column_opclass() (1st patch).
> >> - Added parallel kNN scan support.
> >> - amcanorderbyop() was transformed into ammatchorderby() which takes a List of
> >>    PathKeys and checks each of them with new function match_orderbyop_pathkey()
> >>    extracted from match_pathkeys_to_index().  I think that this design can be
> >>    used in the future to support a mix of ordinary and order-by-op PathKeys,
> >>    but I am not sure.
> > Hi,
> >
> > Unfortunately, the patch has some conflicts, could you rebase it? In the
> > meantime I'll move it to the next CF, hoping to have more reviewers for this
> > item.
>
> Attached 4th version of the patches rebased onto the current master.

I think this patchset in general has a good shape.  After some rounds
of review, it might be committed during January commitfest.

For now, I have following notes.

* 0002-Introduce-ammatchorderby-function-v04.patch

I think match_orderbyop_pathkey() and match_orderbyop_pathkeys()
deserve some high-level commends describing what these functions are
expected to do.

* 0004-Add-kNN-support-to-btree-v04.patch

+ <para>
+  FIXME!!!
+  To implement the distance ordered (nearest-neighbor) search, we only need
+  to define a distance operator (usually it called &lt;-&gt;) with a
correpsonding
+  operator family for distance comparison in the index's operator class.
+  These operators must satisfy the following assumptions for all non-null
+  values A,B,C of the datatype:
+
+  A &lt;-&gt; B = B &lt;-&gt; A symmetric law
+  if A = B, then A &lt;-&gt; C = B &lt;-&gt; C distance equivalence
+  if (A &lt;= B and B &lt;= C) or (A &gt;= B and B &gt;= C),
+  then A &lt;-&gt; B &lt;= A &lt;-&gt; C monotonicity
+ </para>

What exactly you're going to fix here?  I think you at least should
provide a proper formatting to this paragraph....

* 0006-Remove-distance-operators-from-btree_gist-v04.patch

I see you provide btree_gist--1.6.sql and remove btree_gist--1.2.sql.
Note, that in order to better checking of extension migrations, we're
now providing just migration script to new version.  So, everybody
installing new version will go through the migration.  However, in
this particular case we've mass deletion of former extension objects.
So, I think this case should be an exception to the rules.  And it's
good to provide new version of extension script in this case.  Other
opinions?

A see  btree_gist--1.5--1.6.sql contains a sophisticated query
updating extension operators to builtin operators.  However, what do
you think about just long sequence of ALTER OPERATOR FAMILY commands
removing old operators and adding new operators?  It would be longer,
but more predictable and easier for understanding.

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

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
On Thu, Dec 27, 2018 at 5:46 AM Alexander Korotkov
<[hidden email]> wrote:

> * 0006-Remove-distance-operators-from-btree_gist-v04.patch
>
> I see you provide btree_gist--1.6.sql and remove btree_gist--1.2.sql.
> Note, that in order to better checking of extension migrations, we're
> now providing just migration script to new version.  So, everybody
> installing new version will go through the migration.  However, in
> this particular case we've mass deletion of former extension objects.
> So, I think this case should be an exception to the rules.  And it's
> good to provide new version of extension script in this case.  Other
> opinions?

I also note that you've removed implementation of distance functions
from btree_gist.  But during pg_upgrade extensions are moved "as is".
Not just CREATE EXTENSION command is dumped, but the whole extension
content.  pg_upgrade'd instances would have old version of extension
metadata with new .so until ALTER EXTENSION UPDATE. So, user would get
errors about missed function in .so until updates the extension.

We're typically evade this by inclusion of old functions into new .so.
Then user can work normally before extension update.  In this
particular case, we can leave the distance functions in the .so, but
make them just wrappers over core functions.

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

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
On Sun, Dec 30, 2018 at 1:19 AM Alexander Korotkov
<[hidden email]> wrote:

> On Thu, Dec 27, 2018 at 5:46 AM Alexander Korotkov
> <[hidden email]> wrote:
> > * 0006-Remove-distance-operators-from-btree_gist-v04.patch
> >
> > I see you provide btree_gist--1.6.sql and remove btree_gist--1.2.sql.
> > Note, that in order to better checking of extension migrations, we're
> > now providing just migration script to new version.  So, everybody
> > installing new version will go through the migration.  However, in
> > this particular case we've mass deletion of former extension objects.
> > So, I think this case should be an exception to the rules.  And it's
> > good to provide new version of extension script in this case.  Other
> > opinions?
>
> I also note that you've removed implementation of distance functions
> from btree_gist.  But during pg_upgrade extensions are moved "as is".
> Not just CREATE EXTENSION command is dumped, but the whole extension
> content.  pg_upgrade'd instances would have old version of extension
> metadata with new .so until ALTER EXTENSION UPDATE. So, user would get
> errors about missed function in .so until updates the extension.
>
> We're typically evade this by inclusion of old functions into new .so.
> Then user can work normally before extension update.  In this
> particular case, we can leave the distance functions in the .so, but
> make them just wrappers over core functions.

I've run regression tests with patch applied and opr_sanity showed some errors:

1) date_dist_timestamptz(), timestamp_dist_timestamptz(),
timestamptz_dist_date(), timestamptz_dist_timestamp() should be
stable, not immutable.  These functions use timezone during
conversion.

2) date_dist_timestamp(), date_dist_timestamptz(),
timestamp_dist_date(), timestamp_dist_timestamptz(),
timestamptz_dist_date(), timestamptz_dist_timestamp() should be not
leafproof.  These functions perform conversion, which might fail in
corner case.  So, this error should be considered as a leak.

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

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Alexander Korotkov
Hi!

I've couple more notes regarding this patch.
1) There are two loops over scan key determining scan strategy:
existing loop in _bt_first(), and in new function
_bt_select_knn_search_strategy().  It's kind of redundant that we've
to process scan keys twice for knn searches.  I think scan keys
processing should be merged into one loop.
2) We're not supporting knn ordering only using the first key.
Supporting multiple knn keys would require significant reword of
B-tree traversal algorithm making it closer to GiST and SP-GiST.  So,
I think supporting only one knn key is reasonable restriction, at
least for now.  But we could support single-key knn ordering in more
cases.  For instance, knn search in "SELECT * FROM tbl WHERE a =
const1 ORDER BY b <-> const2" could benefit from (a, b) B-tree index.
So, we can support knn search on n-th key if there are equality scan
keys for [1, n-1] index keys.

I've already discussed these issues with Nikita personally.
Hopefully, new version will be published soon.

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

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] kNN for btree

Nikita Glukhov

Attached 5th version of the patches.

On 11.01.2019 2:21, Alexander Korotkov wrote:

Hi!

I've couple more notes regarding this patch.
1) There are two loops over scan key determining scan strategy:
existing loop in _bt_first(), and in new function
_bt_select_knn_search_strategy().  It's kind of redundant that we've
to process scan keys twice for knn searches.  I think scan keys
processing should be merged into one loop.
This redundant loop was removed and code from _bt_select_knn_search_strategy()
was moved into the new function _bt_emit_scan_key() extracted from
_bt_preprocess_keys().
2) We're not supporting knn ordering only using the first key.
Supporting multiple knn keys would require significant reword of
B-tree traversal algorithm making it closer to GiST and SP-GiST.  So,
I think supporting only one knn key is reasonable restriction, at
least for now.  But we could support single-key knn ordering in more
cases.  For instance, knn search in "SELECT * FROM tbl WHERE a =
const1 ORDER BY b <-> const2" could benefit from (a, b) B-tree index.
So, we can support knn search on n-th key if there are equality scan
keys for [1, n-1] index keys.
I will try to implement this in the next version of the patch.

I also note that you've removed implementation of distance functions
from btree_gist.  But during pg_upgrade extensions are moved "as is".
Not just CREATE EXTENSION command is dumped, but the whole extension
content.  pg_upgrade'd instances would have old version of extension
metadata with new .so until ALTER EXTENSION UPDATE. So, user would get
errors about missed function in .so until updates the extension.

We're typically evade this by inclusion of old functions into new .so.
Then user can work normally before extension update.  In this
particular case, we can leave the distance functions in the .so, but
make them just wrappers over core functions.

Wrappers over core functions were left in btree_gist.

I've run regression tests with patch applied and opr_sanity showed some errors:

1) date_dist_timestamptz(), timestamp_dist_timestamptz(),
timestamptz_dist_date(), timestamptz_dist_timestamp() should be
stable, not immutable.  These functions use timezone during
conversion.

Fixed.
2) date_dist_timestamp(), date_dist_timestamptz(),
timestamp_dist_date(), timestamp_dist_timestamptz(),
timestamptz_dist_date(), timestamptz_dist_timestamp() should be not
leafproof.  These functions perform conversion, which might fail in
corner case.  So, this error should be considered as a leak.
All new distance functions except oiddist() are not leakproof,
so I had to relax condition in opr_sanity.sql test:

- pp.proleakproof != po.proleakproof
+ (NOT pp.proleakproof AND po.proleakproof))


--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


0001-Fix-get_index_column_opclass-v05.patch (1K) Download Attachment
0002-Introduce-ammatchorderby-function-v05.patch (22K) Download Attachment
0003-Extract-structure-BTScanState-v05.patch (45K) Download Attachment
0004-Add-kNN-support-to-btree-v05.patch (66K) Download Attachment
0005-Add-btree-distance-operators-v05.patch (83K) Download Attachment
0006-Remove-distance-operators-from-btree_gist-v05.patch (105K) Download Attachment
0007-Add-regression-tests-for-kNN-btree-v05.patch (30K) Download Attachment