knngist rit2011

Эффективный поиск ближайших соседей в PostgreSQL

Абстракт доклада на РИТ-2011, 26 апреля 2011 года, Москва

С необходимостью эффективного поиска ближайших соседей можно встретиться в разных задачах, например, поиск ближайших, к заданной точке , объектов на карте. Задача, на непрограммистский взгляд кажущаяся тривиальной (действительно, человек довольно легко справляется с ней глядя на карту) , на самом деле не имеет общего и доступного решения, что приводит к головной боли разработчиков, которые придумывают ad hoc решения (вставляют костыли). Эти решения, обычно некрасивые, портят настроение творческой натуры программиста, которому требуется посещение пивной, чтобы пережить когнитивный диссонанс :)

Действительно, если у человека есть карта, у которой есть определенный масштаб, и характерный размер поля зрения, то у программиста есть только координаты заданной точки и множество точек, которых может быть очень много (миллиарды звезд !), и к которому может идти большое количество конкурентных запросов, причем не только на чтение. Язык SQL позволяет очень красиво записать запрос, но реальный план его выполнения удручает - требуется прочитать всю таблицу, вычислить все расстояния от заданной точки, отсортировать по убыванию и оставить требуемое количество записей. Наличие индексов не спасает, а только приводит к полному обходу поискового дерева и чтения всей таблицы в случайном порядке, что гораздо медленнее простого чтения таблицы.

Первый костыль, который приходит в голову - это попытка поиска в некой ограниченной области, которая гарантированно содержит требуемое количество ближайших точек. Однако, размер такой области заранее неизвестен и на помощь приходят другие костыли, например, давайте создадим карту плотности точек, по которой будем оценивать размер области, или, давайте начнем с бесконечности (с о-о-чень маленького радиуса) и будем делить (увеличивать) радиус окрестности до тех пор, когда поиск будет возвращать требуемое количество искомых точек. Понятно, что такие решения некрасивы и неэффективны, так как требуется поддерживать (актуализировать) карту плотности, возможно многомерную, что само по себе является нагрузочной задачей для изменяющихся данных в конкурентной среде, либо запускать большое количество запросов, что приводит к нагрузке базы данных и непредсказуемой производительности.

В действительности, класс задач, в которых требуется эффективный поиск ближайших соседей, гораздо шире задач пространственного поиска, например, задачи классификации, задачи поиска очепяток, кластеризации, дедупликации данных. Все они могут сильно выиграть от поддержки эффективного поиска ближайших соседей в СУБД, которые являются в настоящее время де-факто стандартом хранения данных. Эффективный поиск означает быстрый, конкурентный, масштабируемый поиск и поддержку различных типов данных (возможно, нестандартных).

Для самой продвинутой и открытой СУБД PostgreSQL нам удалось реализовать эффективный поиск ближайших соседей, который будет доступен пользователям уже в ближайшей версии 9.1, которая планируется к выпуску в этом году. Производительность поиска очень слабо (логарифмически) зависит от размера данных, поддерживаются все встроенные типы данных, а также любые пользовательские, для которых определено понятие расстояния. Поиск 10 ближайших точек среди 1 млн точек ускорился в сотни раз, что является гигантским успехом на фоне утомительной борьбы за проценты !