11.13. Использование алгоритма k-NN для оптимизации запросов
Postgres Pro Enterprise может оптимизировать поиск k ближайших соседей (k-NN) для индексов B-дерево, GiST и SP-GiST. С этими индексами вы можете использовать операторы упорядочивания, которые возвращают строки в порядке, определённом предложением ORDER BY следующего вида:
ORDER BYстолбец_индексаоператорконстанта
Здесь оператор — это поддерживаемый оператор упорядочивания, например <->. В таком случае Postgres Pro Enterprise использует специальную стратегию сканирования для поиска k-NN.
Для индексов B-дерево вы можете использовать только один оператор упорядочивания с первым столбцом индекса. Индексы GiST и SP-GiST не ограничивают число операторов упорядочивания, которые вы можете использовать для поиска k-NN. Для индексов GiST по нескольким столбцам вы можете использовать несколько операторов упорядочивания для любых столбцов, включённых в этот индекс. Например:
SELECT * FROM points ORDER BYcolumn1<-> '(0, 0)',column2<-> '(1, 1)'
Здесь column1 и column2 — столбцы индекса GiST, построенного по нескольким столбцам.
Вы можете выполнять поиск k-NN с любыми встроенными и расширенными типами данных, для которых определено понятие «расстояния». Поиск k-NN в запросах может давать выигрыш по скорости в различных сценариях использования, например: географические информационные системы (ГИС), задачи классификации (выбор большинством голосов), кластеризация, поиск подобных объектов или ближайших событий, выявление повторов или опечаток, сопоставление триграмм, поиск мультимедиа и т. д.
Для интегрированной реализации поиска k-NN Postgres Pro Enterprise использует при проходе по индексу приоритетную очередь, построенную с учётом расстояний. В зависимости от типа индекса алгоритмы поиска несколько различаются:
Для типов индексов GiST и SP-GiST приоритетная очередь базируется на структуре парной кучи, которую можно эффективно балансировать. Внутренние узлы дерева представляют минимальный охватывающий прямоугольник (MBR, Minimum Bounding Rectangle) для своих потомков. Собственно данные кортежей находятся в узлах-листьях. Postgres Pro Enterprise использует эвристическую логику для поддержания упорядочивания по расстояниям между элементами в очереди и целевой точкой, задаваемой вторым аргументом. Для внутренних узлов вычисляется минимальное расстояние по дочерним узлам. Для узлов-листьев расстояние вычисляется по данным кортежа. В дереве узлы-листья располагаются в списке перед внутренними узлами, так что данные кортежей обрабатываются первыми. Когда из очереди возвращается очередной результат, он гарантированно будет ближайшим к целевой точке из оставшихся. Таким образом, нет необходимости сканировать все узлы. После того как из очереди получены требуемые k элементов, поиск можно остановить.
Для индексов B-деревьев применяется более простой алгоритм. Если целевая точка попадает в диапазон сканирования, Postgres Pro Enterprise выполняет двунаправленное сканирование, начиная с этой точки, каждый раз продвигаясь в направлении, где оказывается очередная ближайшая точка. В противном случае используется простое однонаправленное сканирование в нужном направлении.
Быстродействие поиска k-NN находится в логарифмической зависимости от размера данных и в линейной зависимости от k. По мере приближения k к количеству строк в таблице время поиска k-NN постепенно достигает времени простейшего алгоритма: чтение всей таблицы, сортировка данных и выдача первых k элементов. Так как подход k-NN сокращает количество строк, подлежащих сортировке, вы можете получить значительный выигрыш по скорости, если общее число строк, возвращаемых запросом, велико либо строки имеют большой размер. В худшем случае, когда все точки примерно равноудалены от целевой точки, придётся просматривать весь индекс, но выигрыш в производительности всё же возможен, так как из таблицы может потребоваться прочитать только k случайных записей.
Другое преимущество алгоритма k-NN заключается в упрощении логики: вам не нужно знать «радиус» поиска заранее, и вы можете возобновить поиск, если требуется.
11.13.1. Примеры
Предположим, что у вас есть таблица spots, содержащая координаты нескольких точек. Чтобы найти 10 точек, ближайших к заданной, вы можете выполнить следующий запрос:
SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist
FROM spots ORDER BY dist ASC LIMIT 10;
coordinates | dist
-------------------------------------+------------------
(3.57192993164062,6.51727240153665) | 2.08362656457647
(3.49502563476562,6.49134782128243) | 2.11874164636854
(3.4393,6.4473) | 2.12848814420001
(3.31787109375,6.50089913799597) | 2.25438592075067
(2.6323,6.4779) | 2.79109148900569
(2.66349792480469,6.53159856871478) | 2.79374947392946
(1.84102535247803,6.27874198581057) | 3.4079762161672
(1.2255,6.1228) | 3.93796014327215
(1.22772216796875,6.15693947094637) | 3.94570513108469
(9.6977,4.044503) | 4.79388775494473
(10 строк)Если вам нужно найти 10 точек, ближайших к заданной и содержащих слово «mars» в названии, можно воспользоваться индексом по нескольким столбцам:
CREATE INDEX pt_fts_idx ON spots USING gist(point, to_tsvector('english',asciiname));
SELECT asciiname,point, (point <->'5.0,5.0'::point) AS dist
FROM spots WHERE to_tsvector('english', asciiname)
@@ to_tsquery('english','mars') ORDER BY dist ASC LIMIT 10;Предположим, что у вас есть таблица events, описывающая произвольные исторические события. Чтобы выбрать пять событий, ближайших к дате запуска первого искусственного спутника «Спутник-1», 4 октября 1957 г., выполните:
SELECT date, event, ('1957-10-04'::date <-> date) AS dist
FROM events ORDER BY dist ASC LIMIT 5;
date | event | dist
------------+-------------------------------------------+------
1957-10-04 | Gregory T Linteris, astronaut, is born | 0
| in New Jersey |
1957-10-04 | USSR launches the first artificial | 0
| Earth satellite Sputnik-1 |
1957-10-04 | "Leave It to Beaver" sitcom | 0
| debuts on CBS |
1957-10-03 | Lorinc Szabo, Hungarian poet, | 1
| dies aged 57 |
1957-10-05 | All-Stars beat Montreal in 11th | 1
| NHL All-Star Game |
(5 строк)Рассмотрим также пример нечёткого поиска по триграммам. Создадим индекс по триграммам в таблице events следующим образом:
CREATE INDEX events_trgm ON events USING gist(event gist_trgm_ops);
Теперь давайте найдём три события, наиболее подходящих для данного условия:
SELECT date, event, ('jeorge ewashington' <-> event ) AS dist
FROM events ORDER BY dist ASC LIMIT 3;
date | event | dist
------------+--------------------------------------------+---------
1732-02-11 | George Washington | 0.458333
1792-12-05 | George Washington is re-elected U.S. | 0.674419
| President |
1945-05-12 | Jayotis Washington is born | 0.714286
(3 строки)11.13.2. См. также
| Типы индексов |
| Операторы упорядочивания |
11.13. Using k-NN Algorithm for Optimizing Queries
Postgres Pro Enterprise can optimize k-nearest neighbors (k-NN) search for B-tree, GiST, and SP-GiST index types. With these index types, you can use ordering operators that return the rows in the order defined by the ORDER BY clause of the following type:
ORDER BYindex_columnoperatorconstant
where operator is the supported ordering operator, such as <->. In this case, Postgres Pro Enterprise uses a special scan strategy for k-NN search.
For B-tree indexes, you can use only one ordering operator on the first index column. GiST and SP-GiST do not limit the number of ordering operators you can use for k-NN search. For multicolumn GiST indexes, you can also use multiple ordering operators for each column included into the multicolumn index. For example:
SELECT * FROM points ORDER BYcolumn1<-> '(0, 0)',column2<-> '(1, 1)'
where column1 and column2 are index columns of the multicolumn GiST index.
You can run k-NN search for all built-in and custom data types that support the concept of distance. In database queries, k-NN search can provide performance benefits for various use cases: geographic information systems (GIS), classification problems (majority voting), clusterization, looking for similar objects or nearest events, detecting duplicates and typos, trigram matching, multimedia search, and more.
To natively implement k-NN search, Postgres Pro Enterprise uses distance-based priority queue for index traversal. Depending on the index type, the search algorithm will differ:
For GiST and SP-GiST index types, the priority queue is based on the pairing heap that can be effectively balanced. Inner nodes of the tree represent the minimum bounding rectangle (MBR) for their children. Leaf nodes store actual tuple entries. Postgres Pro Enterprise uses a heuristic to maintain the order by distance between the queue entries and the target point defined by the search argument. For inner nodes, the minimal distance for the child node is calculated. For leaf nodes, the distance to the tuple entry is used. In the tree nodes, leaf nodes are stored before the inner nodes in the list, so tuple entries are processed first. Each time a result is returned from the queue, it is guaranteed to be the closest one to the target point among the remaining entries. Thus, there is no need to scan all nodes. Once the required k entries are extracted from the queue, search can stop.
B-tree indexes use a simpler algorithm. If the target point falls into the scan range, Postgres Pro Enterprise performs bidirectional scan starting from this point, advancing at each step in the direction that includes the nearest point. Otherwise, a simple unidirectional scan in the right direction is used.
k-NN search performance has logarithmic dependence on the data size and linear dependence on k. As k tends to the number of rows in the table, the k-NN search time gradually tends to a naive algorithm that consecutively reads the whole table, sorts the data, and returns the first k entries. Since k-NN approach reduces the number of rows that need to be sorted, you can get significant performance benefits if the total number of rows returned by a query is big, or the rows are long. In the worst-case scenario, when all points are equally far from the target point, you have to traverse the whole index, but performance gain can still be achieved because only k entries need to be read from the table, at random.
Another benefit of using k-NN algorithm is simpler logic: you do not need to know the search “radius” in advance, and can resume the search if required.
11.13.1. Examples
Suppose you have the spots table containing coordinates of multiple points. To find ten closest points to the given target point, you can run the following query:
SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist
FROM spots ORDER BY dist ASC LIMIT 10;
coordinates | dist
-------------------------------------+------------------
(3.57192993164062,6.51727240153665) | 2.08362656457647
(3.49502563476562,6.49134782128243) | 2.11874164636854
(3.4393,6.4473) | 2.12848814420001
(3.31787109375,6.50089913799597) | 2.25438592075067
(2.6323,6.4779) | 2.79109148900569
(2.66349792480469,6.53159856871478) | 2.79374947392946
(1.84102535247803,6.27874198581057) | 3.4079762161672
(1.2255,6.1228) | 3.93796014327215
(1.22772216796875,6.15693947094637) | 3.94570513108469
(9.6977,4.044503) | 4.79388775494473
(10 rows)
If you need to find ten closest points that contain the word "mars" in their names, you can use a multi-column index:
CREATE INDEX pt_fts_idx ON spots USING gist(point, to_tsvector('english',asciiname));
SELECT asciiname,point, (point <->'5.0,5.0'::point) AS dist
FROM spots WHERE to_tsvector('english', asciiname)
@@ to_tsquery('english','mars') ORDER BY dist ASC LIMIT 10;
Suppose you have the events table that describes arbitrary historical events. To select five events that happened close to the launch of the first satellite Sputnik-1 on October 4, 1957, run:
SELECT date, event, ('1957-10-04'::date <-> date) AS dist
FROM events ORDER BY dist ASC LIMIT 5;
date | event | dist
------------+-------------------------------------------+------
1957-10-04 | Gregory T Linteris, astronaut, is born | 0
| in New Jersey |
1957-10-04 | USSR launches the first artificial | 0
| Earth satellite Sputnik-1 |
1957-10-04 | "Leave It to Beaver" sitcom | 0
| debuts on CBS |
1957-10-03 | Lorinc Szabo, Hungarian poet, | 1
| dies aged 57 |
1957-10-05 | All-Stars beat Montreal in 11th | 1
| NHL All-Star Game |
(5 rows)
Consider an example of fuzzy search on trigrams. Let's create a trigram index on the events table, as follows:
CREATE INDEX events_trgm ON events USING gist(event gist_trgm_ops);
Now let's find three events that best match the following search query:
SELECT date, event, ('jeorge ewashington' <-> event ) AS dist
FROM events ORDER BY dist ASC LIMIT 3;
date | event | dist
------------+--------------------------------------------+---------
1732-02-11 | George Washington | 0.458333
1792-12-05 | George Washington is re-elected U.S. | 0.674419
| President |
1945-05-12 | Jayotis Washington is born | 0.714286
(3 rows)
11.13.2. See Also
| Index Types |
| Ordering Operators |
