![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Еще раз про поиск ближайших соседей
Как всегда это бывает, чем ближе к докладу, тем меньше оказывается есть что рассказать :)
Так и с поиском ближайших соседей, про который я уже писал, который мы (я и Федя Сигаев) должны представить на конференции разработчиков PostgreSQL в Оттаве (Канада). Конференция ежегодная, мы на ней уже выступали много раз, нам дают там обычно 1 час выступления перед всеми ведущими разработчиками, которые все имеют приличное образование и большой experience. Я практически уверен, что им будет достаточно сказать только одну фразу "Вместо использования стека для обхода поискового дерева, мы используем очередь с приоритетами (priority queue)" и дальше только обсудить тонкости конкретной реализации.
Однако, придут много интересующихся и для них нужно устроить нечто лекции с освещением вопросов:
Итак: В зависимости от использования структуры данных для хранения узлов обход поискового дерева может быть: стек - поиск в глубину (DFS-Depth First Search), очередь - поиск в ширину (BFS-Breadth First Search). На картинках, взятых с википедии, цифрами показан порядок обхода дерева. Отметим, что в обоих случаях приходится обойти все узлы.
Очередь с приоритетами (priority queue) позволяет нам реализовать другой вид поиска - поиск с эвристикой (Best First Search). В нашем случае эвристика используется для поддержания порядка в очереди по расстоянию объекта (MBR для внутреннего узла или самого объекта для концевого узла) от заданной точки. Этим priority queue отличается от простой очереди, в которой поддерживается естественный порядок - FIFO (First Input First Out). Это означает, что каждый раз когда мы вытаскиваем запись из такой очереди, мы уверены, что это самый близкий объект. Таким образом, мы не обходим все дерево как для DFS и BFS, а скачем по дереву и как только мы набрали (извлекли из выхода из очереди) к-записей (указатели на heap), то можем остановиться.
Алгоритмы DFS и Best First Search для поиска ближайших соседей можно записать на псевдо-языке, при этом p - это указатель, Stack и PQ - это структуры для хранения указателей, а #p - это кол-во выданных результатов (указателей на данные).
Видно, что различий почти нет, разве что в использовании разных структур данных для хранения указателей. Есть еще одно важное отличие, что во втором случае мы можем прекратить поиск, как только выдали требуемое количество результатов, так как эвристика, управляющая PQ, гарантирует, что pop-нутый из очереди объект будет самым близким (из всей очереди) к заданной точке. В случае DFS мы так сказать не можем и приходится обойти все дерево, что будет очень неэффективно для knn-поиска.
Такая похожесть сподвигла нас на использовании PQ и для обычного поиска, чтобы не усложнять код.
Таким образом, в GiST теперь будет использоваться только одна стратегия обхода дерева, основанная на очереди с приоритетами.
PQ у нас реализовано на красно-черных деревьях (Red-black tree), которые уже используются в PostgreSQL и хорошо балансируются (B-tree плохо работает для упорядоченных данных, мы убедились в случае с GIN индексом), при этом в узле дерева хранятся объекты таким образом, что непосредственно объекты с концевых страниц находятся в начале списка, а MBR внутренних узлов - в конце. Таким образом, мы вначале будем работать с самими объектами - возможными результатами.
Теперь о производительности. В самом идеальном случае, когда прямоугольники не пересекаются и все k-точек находятся на одной странице, время knn-поиска будет пропорционально глубине дерева, т.е., логарифмически зависеть от количества записей (зависимость в виде ступенек) и линейно пропорциональна от k до тех пор, пока k-точек помещаются на одной странице. В самом плохом случае, когда все точки находятся на одинаковом расстоянии от заданной точки, придется обойти все дерево и выигрыш будет толко из-за того, что из таблицы надо будет прочесть только малое кол-во записей (хоть и в случайном порядке). Правда, как всегда, лежит посередине и мы надеемся, что ближе к идеальному случаю.
Примеры
Данные генерятся следующим запросом:
Как видно, мы равномерно покрываем карту точками. Число точек выделено красным цветом. Запрос выглядит (k-выделено красным цветом):
Запрос запускается с enable_indexscan=on|off. В первом случае мы получаем время поиска с использованием knn-поиска, описанного выше,а вот втором - базовое время на последовательное чтение таблицы, сортировку результатов и выдачу первых k-записей. Тесты проводились на моем десктопе с 8Gb памяти и следующими настройками в postgresql.conf:
Пример: k=1, n=1000,000
Мы видим, что прочитано 4 страницы для поиска, что вполне согласуется с нашим ожиданием - глубина дерева (распечатать можно с помощью Gevel) равна 3. Выигрыш в производительности около 4000 раз, а ведь бывает, что иной раз пытаешься вытащить несчастные проценты:)
Результаты суммированы в таблице:
Если на больших размерах хорошо виден выигрыш knn-search, особенно при малых k, то
на примере с меньшим количеством данных легче наблюдать асимптотическое поведение knn-search.
Мы видим, что при k=n knn-search проигрывает последовательному скану таблицы с последующей сортировкой.
Уменьшим размер памяти для сортировки sortmem=8Mb. Для этого случая можно ожидать резкого падения производительности для последовательного скана при больших значениях k из-за того, что сортировка в памяти невозможна и придется использовать диск.
Видно, что для k=100000 резко увеличивается время поиска для случая без индекса из-за сортировки на диске. Отмечу, что в стандартной конфигурации постгреса sortmem=1MB, что приведет
к резкому ухудшению производительности для меньших значений k.
Пример с реальными данными (http://download.geonames.org/export/dump/US.zip) - 2 млн географических объектов США.
Log-Log зависимость времени поиска (ms) от k.
Пример с композитным индексом - поиск ближайших американских точек к точке (5.5) - нигерийский поселок, название которых содержит слово 'mars'. Нужно создать композитный индекс !
Пример со 1d значениями
Точки расположены на окружности
Как и ожидалось, читается все дерево и производительность indexscan всего лишь
в два раза лучше seqscan.
Помимо knn мы будем рассказывать про Bloom-индекс и улучшенную оценку стоимости поиска по обратному индексу (gincostestimate), что позволит планеру лучше выбирать что использовать - индекс или seqscan таблицы. Кто интересуется, вот сам тред обсуждения и постинг Тома.
Так и с поиском ближайших соседей, про который я уже писал, который мы (я и Федя Сигаев) должны представить на конференции разработчиков PostgreSQL в Оттаве (Канада). Конференция ежегодная, мы на ней уже выступали много раз, нам дают там обычно 1 час выступления перед всеми ведущими разработчиками, которые все имеют приличное образование и большой experience. Я практически уверен, что им будет достаточно сказать только одну фразу "Вместо использования стека для обхода поискового дерева, мы используем очередь с приоритетами (priority queue)" и дальше только обсудить тонкости конкретной реализации.
Однако, придут много интересующихся и для них нужно устроить нечто лекции с освещением вопросов:
- Что такое поиск ближайших соседей и примеры использования. Поиск ближайших соседей, или knn в дальнейшем, имеет очень широкое применение, например, помимо очевидных географических задач, его используют для задач классификации (голосование большинством), для поиска похожих объектов, поиск ближайших событий и тд.
- Используемые подходы и их проблемы. Что такое R-tree, пример поиска по нему. Так как knn - это не есть поиск в обычном смысле (есть условие поиска в WHERE clause), а так называемый неинформативный поиск, то придется обойти все поисковое дерево (индекс), при этом таблица будет сканироваться в случайном порядке, что на несколько порядков медленнее простого последовательного чтения и проще вообще не использовать индекс ! Палочка-выручалочка для скалярных данных - B-tree индекс тоже не может помочь knn из-за своей однонаправленности. Представьте временную шкалу и события на ней. B-tree может очень быстро найти все события находящиеся раньше или позже заданного момента времени, но не одновременно k-событий слева-справа. Обычный подход для ускорения knn - это range search, когда из спинно-мозговых соображений (хмм, а как это сказать на english ?) можно ограничить поисковое пространство, например, сказать, что ищем в ресторан пределах 1 км, или события 2 на два дня позже или раньше заданного момента времени. Это работает, но не всегда, например, для Парижа радиус окрестности 1 км сработает, но может выдать очень много кандидатов, так что придется потратить много времени на чтение записей и их сортировку, а для Сибири радиус 1 км вообще ничто и нужно последовательно увеличивать радиус и повторять поиск, пока не наберутся нужное количество записей, что тоже не быстро. Да и вообще, все это усложняет реализацию и бизнес-логику. Представьте себе, что вам нужно поддерживать динамическую двумерную ( а если 20-мерную )карту плотности !
- Что такое очередь с приоритетами и как она может помочь для knn. Пример обхода дерева с PQ.
- Тестовые запросы, исследование зависимости производительности knn от количества данных, от k. Здесь понятно, что от размера базы зависимость приблизительно логарифмическая (время обхода дерева меняется при изменении глубины дерева) , а от к - примерно линейная (в основном зависит только от работы с heap, т.е., от кол-ва выдаваемых результатов). Время работы knn плавно приближается к наивному алгоритму при k->nrows, когда последовательно читается вся таблица, сортируется и выдаются первые к записей. Однако, knn - не панацея, для ситуации, когда точка находится в окружении точек на окружности придется прочитать весь индекс и выигрыш будет только из-за того, что из таблицы нужно будет прочитать только к записей (в случайном порядке).
Итак: В зависимости от использования структуры данных для хранения узлов обход поискового дерева может быть: стек - поиск в глубину (DFS-Depth First Search), очередь - поиск в ширину (BFS-Breadth First Search). На картинках, взятых с википедии, цифрами показан порядок обхода дерева. Отметим, что в обоих случаях приходится обойти все узлы.
 |
 |
Очередь с приоритетами (priority queue) позволяет нам реализовать другой вид поиска - поиск с эвристикой (Best First Search). В нашем случае эвристика используется для поддержания порядка в очереди по расстоянию объекта (MBR для внутреннего узла или самого объекта для концевого узла) от заданной точки. Этим priority queue отличается от простой очереди, в которой поддерживается естественный порядок - FIFO (First Input First Out). Это означает, что каждый раз когда мы вытаскиваем запись из такой очереди, мы уверены, что это самый близкий объект. Таким образом, мы не обходим все дерево как для DFS и BFS, а скачем по дереву и как только мы набрали (извлекли из выхода из очереди) к-записей (указатели на heap), то можем остановиться.
Идеализированное (прямоугольники не пересекаются) поисковое дерево  |
Очередь с приоритетами будет выглядеть так:
1:{1,2,3,4,5,6,7,8,9} - корень, содержит точку Q, расстояние от корня до Q равно 0,
2:{2,5,6,7,9}, {1,3,4,8} - рут удаляем из очереди и добавляем его детей, учитывая расстояние
3:{5,6,7,9}, {1,3,4,8}, {2} - {2,5,6,7,9} заменяется на {5,6,7,9} и {2},
которое помещается в конец очереди как самое далекая от Q.
4:{5,9}, {1,3,4,8}, {2}, {6,7}
5:{1,3,4,8}, 5, {2}, {6,7}, 9
6:{1,3,4}, {8}, 5, {2}, {6,7}, 9
7:4, {8}, 5, {2}, {6,7}, 3, 1, 9
8:5, {2}, {6,7}, 3, 8, 1, 9 - точка 4 удаляется из очереди как самая близкая !
9:{6,7}, 3, 2, 8, 1, 9 - выдаем точку 5,прямоугольник с точкой 2 заменяем на точку 2
10:3, 2, 8, 1, 9, 6, 7 - все, этот упорядоченный список уже можно выдавать.
 |
Алгоритмы DFS и Best First Search для поиска ближайших соседей можно записать на псевдо-языке, при этом p - это указатель, Stack и PQ - это структуры для хранения указателей, а #p - это кол-во выданных результатов (указателей на данные).
push Stack, Root;
While Stack {
If p is heap {
output p;
else {
children = get_children(p);
push Stack, children;
}
}
|
push PQ, Root;
While PQ {
If p is heap {
output p;
else {
children = get_children(p);
push PQ, children;
}
}
|
Видно, что различий почти нет, разве что в использовании разных структур данных для хранения указателей. Есть еще одно важное отличие, что во втором случае мы можем прекратить поиск, как только выдали требуемое количество результатов, так как эвристика, управляющая PQ, гарантирует, что pop-нутый из очереди объект будет самым близким (из всей очереди) к заданной точке. В случае DFS мы так сказать не можем и приходится обойти все дерево, что будет очень неэффективно для knn-поиска.
Такая похожесть сподвигла нас на использовании PQ и для обычного поиска, чтобы не усложнять код.
Таким образом, в GiST теперь будет использоваться только одна стратегия обхода дерева, основанная на очереди с приоритетами.
PQ у нас реализовано на красно-черных деревьях (Red-black tree), которые уже используются в PostgreSQL и хорошо балансируются (B-tree плохо работает для упорядоченных данных, мы убедились в случае с GIN индексом), при этом в узле дерева хранятся объекты таким образом, что непосредственно объекты с концевых страниц находятся в начале списка, а MBR внутренних узлов - в конце. Таким образом, мы вначале будем работать с самими объектами - возможными результатами.
Теперь о производительности. В самом идеальном случае, когда прямоугольники не пересекаются и все k-точек находятся на одной странице, время knn-поиска будет пропорционально глубине дерева, т.е., логарифмически зависеть от количества записей (зависимость в виде ступенек) и линейно пропорциональна от k до тех пор, пока k-точек помещаются на одной странице. В самом плохом случае, когда все точки находятся на одинаковом расстоянии от заданной точки, придется обойти все дерево и выигрыш будет толко из-за того, что из таблицы надо будет прочесть только малое кол-во записей (хоть и в случайном порядке). Правда, как всегда, лежит посередине и мы надеемся, что ближе к идеальному случаю.
Примеры
Данные генерятся следующим запросом:
create table qq ( id serial, p point, s int4);
insert into qq (p,s) select point( p.lat, p.long), (random()*1000)::int
from ( select (0.5-random())*180 as lat, random()*360 as long
from ( select generate_series(1,100000) ) as t
) as p;
create index qq_p_s_idx on qq using gist(p);
analyze qq;
Как видно, мы равномерно покрываем карту точками. Число точек выделено красным цветом. Запрос выглядит (k-выделено красным цветом):
explain (analyze on, buffers on)
select * from qq order by (p <-> '(0,0)') asc limit 10;
Запрос запускается с enable_indexscan=on|off. В первом случае мы получаем время поиска с использованием knn-поиска, описанного выше,а вот втором - базовое время на последовательное чтение таблицы, сортировку результатов и выдачу первых k-записей. Тесты проводились на моем десктопе с 8Gb памяти и следующими настройками в postgresql.conf:
shared_buffers = 512MB #32MB # min 128kB work_mem = 32MB #1MB # min 64kB maintenance_work_mem = 256MB #16MB # min 1MB checkpoint_segments = 16 # in logfile segments, min 1, 16MB each effective_cache_size = 1GB #128MB
Пример: k=1, n=1000,000
Limit (cost=0.00..0.08 rows=1 width=24) (actual time=0.104..0.104 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using qq_p_idx on qq (cost=0.00..82060.60 rows=1000000 width=24) (actual time=0.104..0.104 rows=1 loops=1)
Sort Cond: (p <-> '(0,0)'::point)
Buffers: shared hit=4
Total runtime: 0.117 ms
--------------------------
Limit (cost=24853.00..24853.00 rows=1 width=24) (actual time=469.129..469.130 rows=1 loops=1)
Buffers: shared hit=7353
-> Sort (cost=24853.00..27353.00 rows=1000000 width=24) (actual time=469.128..469.128 rows=1 loops=1)
Sort Key: ((p <-> '(0,0)'::point))
Sort Method: top-N heapsort Memory: 25kB
Buffers: shared hit=7353
-> Seq Scan on qq (cost=0.00..19853.00 rows=1000000 width=24) (actual time=0.007..241.539 rows=1000000 loops=1)
Buffers: shared hit=7353
Total runtime: 469.150 ms
Мы видим, что прочитано 4 страницы для поиска, что вполне согласуется с нашим ожиданием - глубина дерева (распечатать можно с помощью Gevel) равна 3. Выигрыш в производительности около 4000 раз, а ведь бывает, что иной раз пытаешься вытащить несчастные проценты:)
Результаты суммированы в таблице:
gist_stat
-------------------------------------------
Number of levels: 3 +
Number of pages: 8787 +
Number of leaf pages: 8704 +
Number of tuples: 1008786 +
Number of invalid tuples: 0 +
Number of leaf tuples: 1000000 +
Total size of tuples: 44492028 bytes+
Total size of leaf tuples: 44104448 bytes+
Total size of index: 71983104 bytes+
hit - количество страниц индекса, knn, seq - времена (ms) для knn-search и последовательного скана соответственно, sortmem (Kb) количество памяти затраченное на сортировку в случае последовательного скана таблицы.
k :hit :knn : seq : sortmem
----------------------------------
1 :4 :0.117 :469.150 : 25
10 :17 :0.289 :471.735 : 25
100 :118 :0.872 :468.244 : 32
1000 :1099 :7.107 :473.840: 127
10000:10234 :31.629 :525.557: 1550
100000:101159:321.182:994.925: 13957
Если на больших размерах хорошо виден выигрыш knn-search, особенно при малых k, то
на примере с меньшим количеством данных легче наблюдать асимптотическое поведение knn-search.
gist_stat
-----------------------------------------
Number of levels: 2 +
Number of pages: 76 +
Number of leaf pages: 75 +
Number of tuples: 10075 +
Number of invalid tuples: 0 +
Number of leaf tuples: 10000 +
Total size of tuples: 444212 bytes+
Total size of leaf tuples: 440900 bytes+
Total size of index: 622592 bytes+
k :hit :knn : seq
-----------------------
1 :3 :0.117 :6.072
10 :13 :0.247 :5.014
100 :103 :0.295 :6.381
1000 :996 :1.605 :8.670
10000:9916:16.487:14.706
Мы видим, что при k=n knn-search проигрывает последовательному скану таблицы с последующей сортировкой.
Уменьшим размер памяти для сортировки sortmem=8Mb. Для этого случая можно ожидать резкого падения производительности для последовательного скана при больших значениях k из-за того, что сортировка в памяти невозможна и придется использовать диск.
n=1000,000, sortmem=8MB k :hit :knn : seq : sortmem ---------------------------------- 1 :11 :0.425 :471.600 : 25 10 :24 :0.611 :471.866 : 25 100 :134 :1.934 :475.008 : 32 1000 :1090 :8.422 :515.681 : 127 10000:10217 :29.303 :721.398 : 1550 100000:101110:265.267:2047.305: 48800 (external merge Disk)
Видно, что для k=100000 резко увеличивается время поиска для случая без индекса из-за сортировки на диске. Отмечу, что в стандартной конфигурации постгреса sortmem=1MB, что приведет
к резкому ухудшению производительности для меньших значений k.
Пример с реальными данными (http://download.geonames.org/export/dump/US.zip) - 2 млн географических объектов США.
Log-Log зависимость времени поиска (ms) от k.
Пример с композитным индексом - поиск ближайших американских точек к точке (5.5) - нигерийский поселок, название которых содержит слово 'mars'. Нужно создать композитный индекс !
create index pt_fts_idx on geo using gist(point, to_tsvector('english',asciiname));
o=# explain (analyze on, buffers on) select asciiname,point, (point <->
'5.0,5.0'::point) as dist from geo where to_tsvector('english', asciiname)
@@ to_tsquery('english','mars') order by dist asc limit 10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..33.55 rows=10 width=35) (actual time=0.452..0.597 rows=10 loops=1)
Buffers: shared hit=56
-> Index Scan using pt_fts_idx on geo (cost=0.00..34313.91 rows=10227 width=35) (actual time=0.452..0.592 rows=10 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (asciiname)::text) @@ '''mar'''::tsquery)
Sort Cond: (point <-> '(5,5)'::point)
Buffers: shared hit=56
Total runtime: 0.629 ms
(7 rows)
Time: 1.087 ms
Пример со 1d значениями
knn=# \d events
Table "public.events"
Column | Type | Modifiers
--------+---------+-----------
id | integer | not null
type | integer |
date | date |
event | text |
Indexes:
"events_pkey" PRIMARY KEY, btree (id)
"event_date_idx" gist (date)
"trgm_idx" gist (event gist_trgm_ops)
knn=# select count(*) from events;
count
--------
151643
(1 row)
Используем индекс по триграммам ( d=1-S, где S - похожесть по триграмам).
knn=# select date, event, ('jeorge ewashington' <-> event ) as dist from events order by dist asc limit 10;
date | event | dist
------------+---------------------------------------------------+----------
1732-02-11 | George Washington | 0.458333
1792-12-05 | George Washington re-elected U.S. pres | 0.674419
1811-02-23 | George Washington Hewitt, composer | 0.675
1753-08-04 | George Washington becomes a master mason | 0.697674
1941-07-19 | Jennifer Dunn, Rep-R-Washington | 0.710526
1945-05-12 | Jayotis Washington, rocker | 0.714286
1817-05-05 | George Washington Julian, MC, Union, died in 1899 | 0.72549
1789-08-25 | Mary Ball Washington, mother of George, dies | 0.729167
1844-01-12 | George Washington Cable, American Novelist | 0.729167
1925-01-31 | George Washington Cable, American Novelist | 0.729167
(10 rows)
Time: 187.604 ms
Ближайшие события к запуску спутника.
knn=# select date, event, ('1957-10-04'::date <-> date) as dist from events order by dist asc limit 10;
date | event | dist
------------+-----------------------------------------------------------------+------
1957-10-04 | Gregory T Linteris, Demarest, New Jersey, astronaut, sk: STS 83 | 0
1957-10-04 | Christina Smith, born in Miami, Florida, playmate, Mar, 1978 | 0
1957-10-04 | U.S.S.R. launches Sputnik I, 1st artificial Earth satellite | 0
1957-10-04 | "Leave It to Beaver," debuts on CBS | 0
1957-10-03 | Lorinc Szabo, Hungarian poet (Tucsokzene), dies at 57 | 1
1957-10-05 | Lee "Kix" Thompson, saxophonist, Madness-Baggy Trousers | 1
1957-10-05 | Larry Saumell, jockey | 1
1957-10-05 | Jeanne Evert, tennis player, Chris' sister | 1
1957-10-05 | Yugoslav dissident Milovan Djilos sentenced to 7 years | 1
1957-10-05 | 11th NHL All-Star Game: All-Stars beat Montreal 5-3 at Montreal | 1
(10 rows)
Time: 0.590 ms
Точки расположены на окружности
create table circle (id serial, p point, s int4);
insert into circle (p,s)
select point( p.x, p.y), (random()*1000)::int
from ( select t.x, sqrt(1- t.x*t.x) as y
from ( select random() as x, generate_series(1,1000000) ) as t
) as p;
create index circle_p_idx on circle using gist(p);
analyze circle;
select gist_stat('circle_p_idx');
gist_stat
-------------------------------------------
Number of levels: 3 +
Number of pages: 8266 +
Number of leaf pages: 8201 +
Number of tuples: 1008265 +
Number of invalid tuples: 0 +
Number of leaf tuples: 1000000 +
Total size of tuples: 44462852 bytes+
Total size of leaf tuples: 44098412 bytes+
Total size of index: 67715072 bytes+
geo=# explain (analyze on, buffers on) select * from circle order by (p <-> '(0,0)') asc limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..0.80 rows=10 width=24) (actual time=226.907..226.924 rows=10 loops=1)
Buffers: shared hit=8276
-> Index Scan using circle_p_idx on circle (cost=0.00..79976.58 rows=1000000 width=24) (actual time=226.905..226.921 rows=10 loops=1)
Sort Cond: (p <-> '(0,0)'::point)
Buffers: shared hit=8276
Total runtime: 230.885 ms
(6 rows)
geo=# set enable_indexscan to off;
geo=# explain (analyze on, buffers on) select * from circle order by (p <-> '(0,0)') asc limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Limit (cost=41462.64..41462.67 rows=10 width=24) (actual time=454.298..454.300 rows=10 loops=1)
Buffers: shared hit=7353
-> Sort (cost=41462.64..43962.64 rows=1000000 width=24) (actual time=454.296..454.296 rows=10 loops=1)
Sort Key: ((p <-> '(0,0)'::point))
Sort Method: top-N heapsort Memory: 25kB
Buffers: shared hit=7353
-> Seq Scan on circle (cost=0.00..19853.00 rows=1000000 width=24) (actual time=0.011..226.816 rows=1000000 loops=1)
Buffers: shared hit=7353
Total runtime: 454.331 ms
Как и ожидалось, читается все дерево и производительность indexscan всего лишь
в два раза лучше seqscan.
Помимо knn мы будем рассказывать про Bloom-индекс и улучшенную оценку стоимости поиска по обратному индексу (gincostestimate), что позволит планеру лучше выбирать что использовать - индекс или seqscan таблицы. Кто интересуется, вот сам тред обсуждения и постинг Тома.