[PATCH] kNN for btree

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