Мы уже рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и три метода: хеш-индекс, B-дерево и GiST. В этой части речь пойдет о SP-GiST.

SP-GiST

Вначале немного о названии. Слово «GiST» намекает на определенную схожесть с одноименным методом. Схожесть действительно есть: и тот, и другой — generalized search trees, обобщенные деревья поиска, предоставляющие каркас для построения разных методов доступа.

«SP» расшифровывается как space partitioning, разбиение пространства. В роли пространства часто выступает именно то, что мы и привыкли называть пространством — например, двумерная плоскость. Но, как мы увидим, имеется в виду любое пространство поиска, по сути произвольная область значений.

SP-GiST подходит для структур, в которых пространство рекурсивно разбивается на непересекающиеся области. В этот класс входят деревья квадрантов (quadtree), k-мерные деревья (k-D tree), префиксные деревья (trie).

Устройство

Итак, идея индексного метода SP-GiST состоит в разбиении области значений на неперекрывающиеся подобласти, каждая из которых, в свою очередь, также может быть разбита. Такое разбиение порождает несбалансированные деревья (в отличие от B-деревьев и обычного GiST).

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

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

Внутренний узел дерева SP-GiST хранит ссылки на дочерние узлы; для каждой ссылки может быть задана метка. Кроме того, внутренний узел может хранить значение, называемое префиксом. На самом деле это значение не обязано быть именно префиксом; его можно рассматривать как произвольный предикат, выполняющийся для всех дочерних узлов.

Листовые узлы SP-GiST содержат значение индексированного типа и ссылку на строку таблицы (TID). В качестве значения могут использоваться сами индексированные данные (ключ поиска), но не обязательно: может храниться и сокращенное значение.

Кроме того, листовые узлы могут собираться в списки. Таким образом, внутренний узел может ссылаться не на одно единственное значение, а на целый список.

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

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

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

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

Пример: дерево квадрантов

Дерево квадрантов (quadtree) используется для индексирования точек на плоскости. Идея состоит в рекурсивном разбиении области на четыре части (квадранта) по отношению к центральной точке. Глубина ветвей такого дерева может различаться и зависит от плотности точек в соответствующих квадрантах.

Вот как это выглядит на картинках на примере демо-базы, дополненной аэропортами с сайта openflights.org. Кстати, недавно мы выпустили новую версию базы, в которой, помимо прочего, заменили долготу и широту одним полем типа point.


Сначала делим плоскость на четыре квадранта...


Затем делим каждый из квадрантов...


И так далее, пока не получим итоговое разбиение.

Рассмотрим теперь подробнее простой пример, который нам уже встречался в части про GiST. Вот как может выглядеть разбиение плоскости в этом случае:



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



Точки, лежащие на границах, относятся к квадранту с меньшим номером.

postgres=# create table points(p point);
CREATE TABLE

postgres=# insert into points(p) values
  (point '(1,1)'), (point '(3,2)'), (point '(6,3)'),
  (point '(5,5)'), (point '(7,8)'), (point '(8,6)');
INSERT 0 6

postgres=# create index points_quad_idx on points using spgist(p);
CREATE INDEX

В данном случае по умолчанию используется класс операторов quad_point_ops, в который входят следующие операторы:

postgres=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'quad_point_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'spgist'
and amop.amoplefttype = opc.opcintype;
     amopopr     | amopstrategy
-----------------+--------------
 <<(point,point) |            1  строго слева
 >>(point,point) |            5  строго справа
 ~=(point,point) |            6  совпадает
 <^(point,point) |           10  строго сверху
 >^(point,point) |           11  строго снизу
 <@(point,box)   |            8  содержится в прямоугольнике
(6 rows)

Рассмотрим, например, как будет выполняться запрос select * from points where p >^ point '(2,7)' (найти все точки, лежащие выше заданной).



Начинаем с корневого узла и выбираем, в какие дочерние узлы надо спускаться с помощью функции согласованности. Для оператора >^ эта функция сравнивает точку (2,7) с центральной точкой узла (4,4) и выбирает квадранты, в которых могут находиться искомые точки — в данном случае первый и четвертый.

В узле, соответствующем первому квадранту, снова определяем дочерние узлы с помощью функции согласованности. Центральная точка (6,6), и нам снова требуется просмотреть первый и четвертый квадранты.



Первому квадранту соответствует список листовых узлов (8,6) и (7,8), из которых под условие запроса подходит только точка (7,8). Ссылка на четвертый квадрант пуста.

У внутреннего узла (4,4) ссылка на четвертый квадрант также пуста, и на этом писк завершен.

postgres=# set enable_seqscan = off;
SET
postgres=# explain (costs off) select * from points where p >^ point '(2,7)';
                   QUERY PLAN                  
------------------------------------------------
 Index Only Scan using points_quad_idx on points
   Index Cond: (p >^ '(2,7)'::point)
(2 rows)


Внутри

Внутреннее устройство индексов SP-GiST можно изучать с помощью расширения gevel, про которое мы уже говорили ранее. Плохая новость: из-за ошибки расширение некорректно работает на современных версиях PostgreSQL. Хорошая новость: мы планируем перенести функциональность gevel в pageinspect (обсуждение). И ошибка там уже исправлена.

Для примера возьмем расширенную демо-базу, которая использовалась для рисования картинок с картой мира.

demo=# create index airports_coordinates_quad_idx on airports_ml using spgist(coordinates);
CREATE INDEX

Об индексе можно, во-первых, узнать некоторую статистическую информацию:

demo=# select * from spgist_stats('airports_coordinates_quad_idx');
           spgist_stats          
----------------------------------
 totalPages:        33           +
 deletedPages:      0            +
 innerPages:        3            +
 leafPages:         30           +
 emptyPages:        2            +
 usedSpace:         201.53 kbytes+
 usedInnerSpace:    2.17 kbytes  +
 usedLeafSpace:     199.36 kbytes+
 freeSpace:         61.44 kbytes +
 fillRatio:         76.64%       +
 leafTuples:        5993         +
 innerTuples:       37           +
 innerAllTheSame:   0            +
 leafPlaceholders:  725          +
 innerPlaceholders: 0            +
 leafRedirects:     0            +
 innerRedirects:    0
(1 row)

И во-вторых, вывести само дерево индекса:

demo=# select tid, n, level, tid_ptr, prefix, leaf_value
from spgist_print('airports_coordinates_quad_idx') as t(
  tid tid,
  allthesame bool,
  n int,
  level int,
  tid_ptr tid,
  prefix point,    -- тип префикса
  node_label int,  -- тип метки (в данном случае не используется)
  leaf_value point -- тип листового значения
)
order by tid, n;
   tid   | n | level | tid_ptr |      prefix      |    leaf_value
---------+---+-------+---------+------------------+------------------
 (1,1)   | 0 |     1 | (5,3)   | (-10.220,53.588) |
 (1,1)   | 1 |     1 | (5,2)   | (-10.220,53.588) |
 (1,1)   | 2 |     1 | (5,1)   | (-10.220,53.588) |
 (1,1)   | 3 |     1 | (5,14)  | (-10.220,53.588) |
 (3,68)  |   |     3 |         |                  | (86.107,55.270)
 (3,70)  |   |     3 |         |                  | (129.771,62.093)
 (3,85)  |   |     4 |         |                  | (57.684,-20.430)
 (3,122) |   |     4 |         |                  | (107.438,51.808)
 (3,154) |   |     3 |         |                  | (-51.678,64.191)
 (5,1)   | 0 |     2 | (24,27) | (-88.680,48.638) |
 (5,1)   | 1 |     2 | (5,7)   | (-88.680,48.638) |
 ...

Но имейте в виде. что функция spgist_print выводит не все листовые значения, а только первое из списка, и поэтому показывает структуру индекса, а не полное его содержимое.

Пример: k-мерные деревья

Для тех же точек на плоскости можно предложить и другой способ разбиения пространства.

Проведем через первую индексируемую точку горизонтальную линию. Она разбивает плоскость на две части: верхнюю и нижнюю. Вторая индексируемая точка попадает в одну из этих частей. Через нее проведем вертикальную линию, которая разбивает эту часть на две: правую и левую. Через следующую точку снова проводим горизонтальную линию, через следующую — вертикальную и так далее.

У всех внутренних узлов дерева, построенного таким образом, будет всего два дочерних узла. Каждая из двух ссылок может вести либо на следующий в иерархии внутренний узел, либо на список листовых узлов.

Метод легко обобщается на k-мерные пространства, поэтому и деревья в литературе называются k-мерным (k-D tree).

На примере аэропортов:


Сначала делим плоскость на верх и низ...


Затем каждую часть на лево и право...


И так далее, пока не получим итоговое разбиение.

Чтобы использовать именно такое разбиение, нужно при создании индекса явно указать класс операторов kd_point_ops:

postgres=# create index points_kd_idx on points using spgist(p kd_point_ops);
CREATE INDEX


В этот класс входят ровно те же операторы, что и в «умолчательный» quad_point_ops.

Внутри

При просмотре структуры дерева надо учесть, что префиксом в данном случае является не точка, а всего одна координата:

demo=# select tid, n, level, tid_ptr, prefix, leaf_value
from spgist_print('airports_coordinates_kd_idx') as t(
  tid tid,
  allthesame bool,
  n int,
  level int,
  tid_ptr tid,
  prefix float,    -- тип префикса
  node_label int,  -- тип метки (в данном случае не используется)
  leaf_value point -- тип листового значения
)
order by tid, n;
   tid   | n | level | tid_ptr |   prefix   |    leaf_value
---------+---+-------+---------+------------+------------------
 (1,1)   | 0 |     1 | (5,1)   |     53.740 |
 (1,1)   | 1 |     1 | (5,4)   |     53.740 |
 (3,113) |   |     6 |         |            | (-7.277,62.064)
 (3,114) |   |     6 |         |            | (-85.033,73.006)
 (5,1)   | 0 |     2 | (5,12)  |    -65.449 |
 (5,1)   | 1 |     2 | (5,2)   |    -65.449 |
 (5,2)   | 0 |     3 | (5,6)   |     35.624 |
 (5,2)   | 1 |     3 | (5,3)   |     35.624 |
 ...


Пример: префиксное дерево

С помощью SP-GiST можно реализовать и префиксное дерево (radix tree) для строк. Идея префиксного дерева в том, что индексируемая строка не хранится целиком в листовом узле, а получается конкатенацией значений, хранящихся в узлах вверх от данного до корня.

Допустим, надо проиндексировать адреса сайтов: «postgrespro.ru», «postgrespro.com», «postgresql.org» и «planet.postgresql.org».

postgres=# create table sites(url text);
CREATE TABLE

postgres=# insert into sites values ('postgrespro.ru'),('postgrespro.com'),('postgresql.org'),('planet.postgresql.org');
INSERT 0 4

postgres=# create index on sites using spgist(url);
CREATE INDEX

Дерево будет иметь следующий вид:



Во внутренних узлах дерева хранятся префиксы, общие для всех дочерних узлов. Например, в дочках узла «stgres» значения начинаются на «p» + «o» + «stgres».

Каждый указатель на дочерний узел, в отличие от дерева квадрантов, дополнительно помечен одним символом (на самом деле двумя байтами, но это не так важно).

Класс операторов text_ops поддерживает операторы, традиционные для b-tree: «равно», «больше», «меньше»:

postgres=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'text_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'spgist'
and amop.amoplefttype = opc.opcintype;
     amopopr     | amopstrategy
-----------------+--------------
 ~<~(text,text)  |            1
 ~<=~(text,text) |            2
 =(text,text)    |            3
 ~>=~(text,text) |            4
 ~>~(text,text)  |            5
 <(text,text)    |           11
 <=(text,text)   |           12
 >=(text,text)   |           14
 >(text,text)    |           15
(9 rows)

Операторы с тильдами отличаются тем, что работают не с символами, а с байтами.

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

Рассмотрим запрос: select * from sites where url like 'postgresp%ru'. Он может быть выполнен с помощью индекса:

postgres=# explain (costs off) select * from sites where url like 'postgresp%ru';
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Index Only Scan using sites_url_idx on sites
   Index Cond: ((url ~>=~ 'postgresp'::text) AND (url ~<~ 'postgresq'::text))
   Filter: (url ~~ 'postgresp%ru'::text)
(3 rows)

Фактически по индексу находятся значения, большие или равные «postgresp» и в то же время меньшие «postgresq» (Index Cond), а затем из результата отбираются подходящие значения (Filter).

Сначала функция согласованности должна решить, в какие дочерние узлы корня «p» нужно спуститься. Есть два варианта: «p» + «l» (не подходит, даже не заглядывая дальше) и «p» + «o» + «stgres» (подходит).

Для узла «stgres» снова требуется обращение к функции согласованности, чтобы проверить «postgres» + «p» + «ro.» (подходит) и «postgres» + «q» (не подходит).

Для узла «ro.» и всех его дочерних листовых узлов функции согласованности ответит «подходит», так что индексный метод вернет два значения: «postgrespro.com» и «postgrespro.ru». Из них — уже на этапе фильтрации — будет выбрано одно подходящее значение.

Внутри

При просмотре структуры дерева надо учесть типы данных:

postgres=# select * from spgist_print('sites_url_idx') as t(
  tid tid,
  allthesame bool,
  n int,
  level int,
  tid_ptr tid,
  prefix text,         -- тип префикса
  node_label smallint, -- тип метки
  leaf_value text      -- тип листового значения
)
order by tid, n;


Свойства

Посмотрим на свойства метода доступа spgist (запросы приводились ранее):

 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 spgist | can_order     | f
 spgist | can_unique    | f
 spgist | can_multi_col | f
 spgist | can_exclude   | t


Индксы SP-GiST не могут использоваться для сортировки и поддержки уникальности. Кроме того, такие индексы нельзя строить по нескольким столбцам (в отличие от GiST). Использование для поддержки ограничений исключения допускается.

Свойства индекса:

     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f

Здесь отличие от GiST состоит в отсутствии возможности кластеризации.

И, наконец, свойства уровня столбца:

        name        | pg_index_column_has_property
--------------------+------------------------------
 asc                | f
 desc               | f
 nulls_first        | f
 nulls_last         | f
 orderable          | f
 distance_orderable | f
 returnable         | t
 search_array       | f
 search_nulls       | t

Поддержки сортировки нет, что понятно. Операторы расстояния для поиска ближайших соседей в SP-GiST пока не доступны; скорее всего такая поддержка появится в будущем.

SP-GiST может использоваться для исключительно индексного сканирования, по крайней мере для рассмотренных классов операторов. Как мы видели, в каких-то случаях индексированные значения непосредственно хранятся в листовых узлах, а в каких-то — восстанавливаются по частям при спуске по дереву.

Неопределенные значения

До сих пор мы ничего не говорили про неопределенные значения, чтобы не усложнять картину. Как видно из свойств индекса, NULL поддерживается. И действительно:

postgres=# explain (costs off)
select * from sites where url is null;
                  QUERY PLAN                  
----------------------------------------------
 Index Only Scan using sites_url_idx on sites
   Index Cond: (url IS NULL)
(2 rows)

Однако неопределенное значение для SP-GiST — нечто чужеродное. Все операторы, входящие в класс операторов метода spgist, должны быть строгими: для неопределенных параметров они должны возвращать неопределенный результат. Это обеспечивает сам метод; неопределенные значения просто не передаются операторам.

Но, чтобы метод доступа мог использоваться для исключительно индексного сканирования, неопределенные значения все-таки нужно хранить в индексе. Они и хранятся, но в отдельном дереве со своим собственным корнем.

Другие типы данных

Помимо точек и префиксных деревьев для строк, в PostgreSQL реализованы и другие методы на основе SP-GiST:

• Дерево квадрантов для прямоугольников обеспечивает класс операторов box_ops.
  Каждый прямоугольник представляется точкой в четырехмерном пространстве, так что число квадрантов равно 16. Такой индекс может выиграть у GiST по производительности, когда среди прямоугольников много пересечений: в GiST невозможно провести границы так, чтобы отделить пересекающиеся объекты друг от друга, а вот с точками (пусть и четырехмерными) таких проблем нет.
  
• Дерево квадрантов для диапазонов предоставляет класс операторов range_ops.
  Интервал представляется двумерной точкой: нижняя граница становится абсциссой, а верхняя — ординатой.
  

Продолжение следует.

Original source: habrahabr.ru (comments, light).