Как оптимизировать этот SQL-запрос для прямоугольной области?

Question

Я пытаюсь оптимизировать следующий запрос, но мне не ясно, какой индекс или индексы будет лучше. Я храню плитки в двухмерной плоскости и запрашиваю прямоугольные области этой плоскости. Для целей этого вопроса в таблице имеются следующие столбцы:

• id: целое число первичного ключа
• world_id: целочисленный внешний ключ, который действует как пространство имен для подмножества плиток.
• tileY: целое число Y-координаты
• tileX: целое число X-координат
• значение: содержимое этой плитки, varchar, если это имеет значение.

У меня есть следующие индексы:

• "ywot_tile_pkey" ПЕРВИЧНЫЙ КЛЮЧ, btree (id)
• "ywot_tile_world_id_key" UNIQUE, btree (world_id, "tileY", "tileX")
• "ywot_tile_world_id" btree (world_id)

И этот запрос я пытаюсь оптимизировать:

ywot=> EXPLAIN ANALYZE SELECT * FROM "ywot_tile" WHERE ("world_id" = 27685  AND "tileY" <= 6  AND "tileX" <= 9  AND "tileX" >= -2  AND "tileY" >= -1 );                                                                    QUERY PLAN                                                                 -------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on ywot_tile  (cost=11384.13..149421.27 rows=65989 width=168) (actual time=79.646..80.075 rows=96 loops=1)
   Recheck Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tileX" <= 9) AND ("tileX" >= (-2)))
   ->  Bitmap Index Scan on ywot_tile_world_id_key  (cost=0.00..11367.63 rows=65989 width=0) (actual time=79.615..79.615 rows=125 loops=1)
         Index Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tileX" <= 9) AND ("tileX" >= (-2)))
 Total runtime: 80.194 ms

Итак, мир зафиксирован, и мы запрашиваем прямоугольную область плиток. Еще немного информации, которая может иметь отношение к теме:

Все плитки для запрашиваемой области могут присутствовать или не присутствовать Высота и ширина запрашиваемого прямоугольника обычно составляют примерно 10x10-20x20 Для любой данной пары (world, X) или (world, Y) может быть неограниченное количество совпадающих тайлов, но наихудший случай в настоящее время составляет около 10 000, и обычно их гораздо меньше. Новые плитки создаются гораздо реже, чем обновляются существующие (изменяя «значение»), и это само по себе гораздо реже, чем просто чтение, как в запросе выше.

Единственное, о чем я могу думать, - это индексировать (world, X) и (world, Y). Я предполагаю, что база данных сможет взять эти два набора и пересечь их. Проблема в том, что существует потенциально неограниченное количество совпадений для любого из них. Есть ли другой вид индекса, который был бы более подходящим?

Answer 1

кластеризует таблицу на "ywot_tile_world_id_key", первичный ключ выглядит как искусственный идентификатор. Если у вас больше уникальных вертикальных значений, чем горизонтальных, вы можете изменить порядок (world-id, y, x). Также удалите одинокий индекс для идентификатора мира, он дублируется составным индексом.

Answer 2

GIST для вашего X, Y почти такой же, как PostGIS. На самом деле вы могли бы даже использовать расширение PostGIS для Postgresql и получить немало денег за свой доллар

Answer 3

Вот что я в итоге сделал. Запросы теперь ~ 20 мс вместо 80, что является неплохим улучшением, хотя и не удивительным.

1. Загружен модуль вклада btree_gist
2. Создан следующий индекс:

   CREATE INDEX CONCURRENTLY ywot_tile_boxes ON ywot_tile USING gist (world_id, box(point("tileX","tileY"),point("tileX","tileY")));

3. Переключил запросы, чтобы они выглядели так:

   SELECT * FROM "ywot_tile" WHERE world_id = 27685 AND box(point("tileX","tileY"),point("tileX","tileY")) && box(point(-2,-1),point(9,6));

Будем весьма благодарны за любые дальнейшие предложения.