11.13. Использование алгоритма k-NN для оптимизации запросов #
Postgres Pro Shardman может оптимизировать поиск k ближайших соседей (k-NN) для индексов B-дерево, GiST и SP-GiST. С этими индексами вы можете использовать операторы упорядочивания, которые возвращают строки в порядке, определённом предложением ORDER BY следующего вида:
ORDER BYстолбец_индексаоператорконстанта
Здесь оператор — это поддерживаемый оператор упорядочивания, например <->. В таком случае Postgres Pro Shardman использует специальную стратегию сканирования для поиска 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 Shardman использует при проходе по индексу приоритетную очередь, построенную с учётом расстояний. В зависимости от типа индекса алгоритмы поиска несколько различаются:
Для типов индексов GiST и SP-GiST приоритетная очередь базируется на структуре парной кучи, которую можно эффективно балансировать. Внутренние узлы дерева представляют минимальный охватывающий прямоугольник (MBR, Minimum Bounding Rectangle) для своих потомков. Собственно данные кортежей находятся в узлах-листьях. Postgres Pro Shardman использует эвристическую логику для поддержания упорядочивания по расстояниям между элементами в очереди и целевой точкой, задаваемой вторым аргументом. Для внутренних узлов вычисляется минимальное расстояние по дочерним узлам. Для узлов-листьев расстояние вычисляется по данным кортежа. В дереве узлы-листья располагаются в списке перед внутренними узлами, так что данные кортежей обрабатываются первыми. Когда из очереди возвращается очередной результат, он гарантированно будет ближайшим к целевой точке из оставшихся. Таким образом, нет необходимости сканировать все узлы. После того как из очереди получены требуемые k элементов, поиск можно остановить.
Для индексов B-деревьев применяется более простой алгоритм. Если целевая точка попадает в диапазон сканирования, Postgres Pro Shardman выполняет двунаправленное сканирование, начиная с этой точки, каждый раз продвигаясь в направлении, где оказывается очередная ближайшая точка. В противном случае используется простое однонаправленное сканирование в нужном направлении.
Быстродействие поиска 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. См. также #
| Типы индексов |
| Операторы упорядочивания |