Индексы R-Tree

Начиная с DuckDB v1.1.0, spatial расширение обеспечивает базовую поддержку пространственного индексирования с помощью типа индекса расширения R-tree.

Зачем использовать индекс R-Tree?

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

Как работают индексы R-Tree?

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

Минимальный ограничивающий прямоугольник (MBR) геометрии — это наименьший прямоугольник, полностью охватывающий геометрию. Обычно, когда мы говорим об ограничивающем прямоугольнике геометрии (или ограничивающем «прямоугольнике» в контексте 2D-геометрии), мы имеем в виду минимальный ограничивающий прямоугольник. Кроме того, мы склонны предполагать, что ограничивающие прямоугольники/прямоугольники являются выровненными по осям, т.е., прямоугольник не повернут — стороны всегда параллельны осям координат. MBR точки — это сама точка.

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

Какие ограничения индексов R-Tree в DuckDB?

Прежде чем начать использовать индекс R-tree, следует учитывать некоторые ограничения:

• Индекс R-tree поддерживается только для типа данных GEOMETRY.
• Индекс R-tree будет использоваться только для выполнения «сканирования индекса», когда таблица отфильтрована (с помощью WHERE-запроса) с одной из следующих пространственных функций предиката (поскольку все они подразумевают пересечение): ST_Equals, ST_Intersects, ST_Touches, ST_Crosses, ST_Within, ST_Contains, ST_Overlaps, ST_Covers, ST_CoveredBy, ST_ContainsProperly.
• Один из аргументов функции пространственного предиката должен быть «константой» (т. е. выражением, результат которого известен на этапе планирования запроса). Это необходимо, так как планировщик запросов должен знать ограничивающий прямоугольник области запроса *до* фактического выполнения запроса, чтобы использовать сканирование индекса R-tree.

В будущем мы планируем включить возможность использования индексов R-tree для ускорения дополнительных функций предикатов и более сложных запросов, таких как пространственные соединения.

Как использовать индексы R-Tree в DuckDB

Чтобы создать индекс R-tree, просто используйте оператор CREATE INDEX с предложением USING RTREE, передавая столбец геометрии для индексирования в скобках. Например:

-- Create a table with a geometry column
CREATE TABLE my_table (geom GEOMETRY);

-- Create an R-tree index on the geometry column
CREATE INDEX my_idx ON my_table USING RTREE (geom);

Вы также можете передать дополнительные параметры при создании индекса R-tree, используя предложение WITH для управления поведением индекса R-tree. Например, чтобы указать максимальное количество записей на узел в R-дереве, вы можете использовать параметр max_node_capacity:

CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);

Влияние настройки этих параметров на производительность сильно зависит от конфигурации системы, на которой работает DuckDB, пространственного распределения набора данных и шаблонов запросов вашей конкретной рабочей нагрузки. Значения по умолчанию должны быть достаточными, но если вы хотите поэкспериментировать с различными параметрами, см. полный список параметров здесь.

Пример

Вот пример, показывающий, как создать индекс R-tree в столбце геометрии, где мы видим, что оператор RTREE_INDEX_SCAN используется при фильтрации таблицы с пространственным предикатом:

INSTALL spatial;
LOAD spatial;

-- Create a table with 10_000_000 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 10_000, 1337);

-- Create an index on the table.
CREATE INDEX my_idx ON t1 USING RTREE (geom);

-- Perform a query with a "spatial predicate" on the indexed geometry column
-- Note how the second argument in this case, the ST_MakeEnvelope call is a "constant"
SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));

390

Мы можем проверить, что используется сканирование индекса R-tree, используя оператор EXPLAIN:

EXPLAIN SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));

┌───────────────────────────┐
│    UNGROUPED_AGGREGATE    │
│    ────────────────────   │
│        Aggregates:        │
│        count_star()       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ ST_Within(geom, '...')    │ 
│                           │
│         ~2000 Rows        │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│     RTREE_INDEX_SCAN      │
│    ────────────────────   │
│   t1 (RTREE INDEX SCAN :  │
│           my_idx)         │
│                           │
│     Projections: geom     │
│                           │
│        ~10000 Rows        │
└───────────────────────────┘

Соображения по производительности

Массовая загрузка и обслуживание

Создание R-деревьев поверх уже заполненной таблицы происходит намного быстрее, чем сначала создание индекса, а затем вставка данных. Это происходит потому, что R-дерево будет периодически перебалансироваться и выполнять относительно дорогостоящую операцию разделения, когда узел достигает максимальной ёмкости после вставки, что может привести к каскаду дополнительных разделений вверх по дереву. Однако, когда индекс R-tree создаётся для уже заполненной таблицы, используется специальный алгоритм «массовой загрузки» снизу вверх (Sort-Tile-Recursive), который делит все записи на уже сбалансированное дерево, поскольку общее количество необходимых узлов может быть вычислено с самого начала.

Кроме того, использование алгоритма массовой загрузки, как правило, создаёт R-дерево с лучшей структурой (меньше перекрытий между ограничивающими прямоугольниками), что обычно приводит к лучшей производительности запросов. Если вы заметите, что производительность запросов R-дерева начинает ухудшаться после большого числа обновлений или удалений, удаление и повторное создание индекса может привести к R-дереву более высокого качества.

Использование памяти

Как и встроенный индекс ART в DuckDB, все связанные буферы, содержащие R-дерево, будут загружаться по мере необходимости с диска (при запуске DuckDB в режиме, поддерживаемом диском), но они в настоящее время никогда не выгружаются, пока индекс не будет удалён. Это означает, что если вы в конечном итоге просканируете весь индекс, весь индекс будет загружен в память и останется там на всё время соединения с базой данных. Тем не менее, вся память, используемая индексом R-tree (даже во время массовой загрузки), отслеживается DuckDB и будет учитываться при ограничении памяти, заданном параметром конфигурации memory_limit.

Настройка

В зависимости от вашей рабочей нагрузки, вы можете поэкспериментировать с параметрами max_node_capacity и min_node_capacity, чтобы изменить структуру R-дерева и то, как оно реагирует на вставки и удаления, см. полный список параметров здесь. В целом, дерево с большим общим количеством узлов (т. е. с меньшим значением max_node_capacity) *может* привести к более детализированной структуре, что позволит более агрессивно обрезать поддеревья при выполнении запросов, но также потребует больше памяти для хранения самого дерева и будет более затратным при запросе больших областей, поскольку придётся пройти больше внутренних узлов.

Параметры

Следующие параметры можно передать в предложение WITH при создании индекса R-tree: (например, CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (⟨option⟩ = ⟨value⟩);)

*Если узел попадает под минимальное количество записей после удаления, узел будет удалён, а все записи будут повторно вставлены сверху дерева. Это распространённая операция в реализациях R-дерева, чтобы предотвратить слишком большое неравновесие дерева.

Функции таблицы R-Tree

Функция таблицы rtree_index_dump(VARCHAR) может использоваться для возврата всех узлов в индексе R-tree, что может быть полезно при отладке, профилировании или просто для проверки структуры индекса. Функция принимает имя индекса R-tree в качестве аргумента и возвращает таблицу со следующими столбцами:

Пример:

-- Create a table with 64 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 64, 1337);

-- Create an R-tree index on the geometry column (with a low max_node_capacity for demonstration purposes)
CREATE INDEX my_idx ON t1 USING RTREE (geom) WITH (max_node_capacity = 4);

-- Inspect the R-tree index. Notice how the area of the bounding boxes of the branch nodes 
-- decreases as we go deeper into the tree.
SELECT 
  level, 
  bounds::GEOMETRY AS geom, 
  CASE WHEN row_id IS NULL THEN st_area(geom) ELSE NULL END AS area, 
  row_id, 
  CASE WHEN row_id IS NULL THEN 'branch' ELSE 'leaf' END AS kind 
FROM rtree_index_dump('my_idx') 
ORDER BY area DESC;

┌───────┬──────────────────────────────┬────────────────────┬────────┬─────────┐
│ level │             geom             │        area        │ row_id │  kind   │
│ int32 │           geometry           │       double       │ int64  │ varchar │
├───────┼──────────────────────────────┼────────────────────┼────────┼─────────┤
│     0 │ POLYGON ((2.17285037040710…  │  3286.396482226409 │        │ branch  │
│     0 │ POLYGON ((6.00962591171264…  │  3193.725100864862 │        │ branch  │
│     0 │ POLYGON ((0.74995160102844…  │  3099.921458393704 │        │ branch  │
│     0 │ POLYGON ((14.6168870925903…  │ 2322.2760491675654 │        │ branch  │
│     1 │ POLYGON ((2.17285037040710…  │  604.1520104388514 │        │ branch  │
│     1 │ POLYGON ((26.6022186279296…  │  569.1665467030252 │        │ branch  │
│     1 │ POLYGON ((35.7942314147949…  │ 435.24662436250037 │        │ branch  │
│     1 │ POLYGON ((62.2643051147460…  │ 396.39027683023596 │        │ branch  │
│     1 │ POLYGON ((59.5225715637207…  │ 386.09153403820187 │        │ branch  │
│     1 │ POLYGON ((82.3060836791992…  │ 369.15115640929434 │        │ branch  │
│     · │              ·               │          ·         │      · │  ·      │
│     · │              ·               │          ·         │      · │  ·      │
│     · │              ·               │          ·         │      · │  ·      │
│     2 │ POLYGON ((20.5411434173584…  │                    │     35 │ leaf    │
│     2 │ POLYGON ((14.6168870925903…  │                    │     36 │ leaf    │
│     2 │ POLYGON ((43.7271652221679…  │                    │     39 │ leaf    │
│     2 │ POLYGON ((53.4629211425781…  │                    │     44 │ leaf    │
│     2 │ POLYGON ((26.6022186279296…  │                    │     62 │ leaf    │
│     2 │ POLYGON ((53.1732063293457…  │                    │     63 │ leaf    │
│     2 │ POLYGON ((78.1427154541015…  │                    │     10 │ leaf    │
│     2 │ POLYGON ((75.1728591918945…  │                    │     15 │ leaf    │
│     2 │ POLYGON ((62.2643051147460…  │                    │     42 │ leaf    │
│     2 │ POLYGON ((80.5032577514648…  │                    │     49 │ leaf    │
├───────┴──────────────────────────────┴────────────────────┴────────┴─────────┤
│ 84 rows (20 shown)                                                 5 columns │
└──────────────────────────────────────────────────────────────────────────────┘