66.4. Реализация
В этом разделе освещаются тонкости реализации и особенности, о которых полезно знать тем, кто будет реализовывать классы операторов SP-GiST.
66.4.1. Ограничения SP-GiST
Отдельные кортежи листьев и внутренние кортежи должны умещаться в одной странице индекса (по умолчанию её размер 8 Кбайт). Таким образом при индексировании значений типов данных переменной длины большие значения могут поддерживаться только такими схемами, как префиксные деревья, в которых каждый уровень дерева включает префикс, достаточно короткий для помещения в страницу, и на конечном уровне листьев содержится суффикс, который также достаточно мал, чтобы поместиться в странице. Класс операторов должен устанавливать признак longValuesOK, только если он готов организовывать такую структуру. Если этот признак не установлен, ядро SP-GiST не примет запрос на индексацию значения, которое слишком велико для одной страницы индекса.
Также класс операторов должен отвечать за то, чтобы внутренние кортежи при расширении не выходили за пределы страницы индекса; это ограничивает число дочерних узлов, которые могут принадлежать одному внутреннему кортежу, а также максимальный размер значения префикса.
Ещё одно ограничение состоит в том, что когда узел внутреннего кортежа указывает на набор кортежей листьев, все эти кортежи должны находиться в одной странице индекса. (Это конструктивное ограничение введено для оптимизации позиционирования и экономии места на ссылках, связывающих такие кортежи вместе.) Если набор кортежей листьев оказывается слишком большим для одной страницы, выполняется разделение и вставляется промежуточный внутренний кортеж. Чтобы устранить возникшую проблему, новый внутренний кортеж должен разделять набор значений в листе на несколько групп узлов. Если функция picksplit класса операторов не может сделать это, ядро SP-GiST переходит к чрезвычайным мерам, описанным в Подразделе 66.4.3.
Когда longValuesOK имеет значение true, ожидается, что последующие уровни дерева SP-GiST будут включать всё больше и больше информации в префиксы и метки узлов внутренних кортежей, постепенно уменьшая значение, которое нужно сохранить на уровне листьев, чтобы оно в конце концов уместилось на странице. Чтобы в случае ошибки в классах операторах исключить бесконечные циклы при добавлении записи, ядро SP-GiST выдаст ошибку, если значение для листа не уменьшится за 10 вызовов метода choose.
66.4.2. SP-GiST без меток узлов
В некоторых древовидных схемах каждый внутренний кортеж содержит фиксированный набор узлов; например, в дереве квадрантов это всегда четыре узла, соответствующие четырём квадрантам вокруг центральной точки внутреннего кортежа. В таком случае код обычно работает с узлами по номерам и необходимости в явных метках узлов нет. Чтобы убрать метки узлов (и таким образом сэкономить место), функция picksplit может возвратить NULL вместо массива nodeLabels, а функция choose аналогично может возвратить NULL вместо массива prefixNodeLabels во время действия spgSplitTuple. В результате при последующих вызовах функций choose и inner_consistent им вместо nodeLabels будет передаваться NULL. В принципе метки узлов могут применяться для одних внутренних кортежей и отсутствовать у других в том же индексе.
Когда внутренний кортеж содержит узлы без меток, функция choose не может выбрать действие spgAddNode, так как в этом случае предполагается, что набор узлов фиксированный.
66.4.3. Внутренние кортежи «все-равны»
Ядро SP-GiST может переопределить результаты функции picksplit класса операторов, когда эта функция не может разделить поступившие значения листьев на минимум две категории узлов. Когда это происходит, создаётся новый внутренний кортеж с несколькими узлами, каждый из которых имеет одну метку (если имеет), которую picksplit дала одному узлу, а значения листьев распределяются случайно между этими равнозначными узлами. Для этого внутреннего кортежа устанавливается флаг allTheSame, который предупреждает функции choose и inner_consistent, что кортеж не содержит набор узлов, который они обычно ожидают.
Когда обрабатывается кортеж с флагом allTheSame, выбранное функцией choose действие spgMatchNode воспринимается как указание, что новое значение можно присвоить одному из равнозначных узлов; код ядра будет игнорировать полученное значение nodeN и спустится в один из узлов, выбранный случайно (чтобы дерево было сбалансированным). Будет считаться ошибкой, если choose выберет действие spgAddNode, так как при этом не все узлы окажутся равны; если добавляемое значение не соответствует существующим узлам, должно выбираться действие spgSplitTuple.
Также, когда обрабатывается кортеж с флагом allTheSame, функция inner_consistent должна вернуть все или не возвращать никакие узлы для продолжения поиска по индексу, так как все узлы равнозначны. Для этого может потребоваться, а может и не потребоваться код обработки особого случая, в зависимости от того, как inner_consistent обычно воспринимает узлы.
66.4. Implementation
This section covers implementation details and other tricks that are useful for implementers of SP-GiST operator classes to know.
66.4.1. SP-GiST Limits
Individual leaf tuples and inner tuples must fit on a single index page (8kB by default). Therefore, when indexing values of variable-length data types, long values can only be supported by methods such as radix trees, in which each level of the tree includes a prefix that is short enough to fit on a page, and the final leaf level includes a suffix also short enough to fit on a page. The operator class should set longValuesOK to true only if it is prepared to arrange for this to happen. Otherwise, the SP-GiST core will reject any request to index a value that is too large to fit on an index page.
Likewise, it is the operator class's responsibility that inner tuples do not grow too large to fit on an index page; this limits the number of child nodes that can be used in one inner tuple, as well as the maximum size of a prefix value.
Another limitation is that when an inner tuple's node points to a set of leaf tuples, those tuples must all be in the same index page. (This is a design decision to reduce seeking and save space in the links that chain such tuples together.) If the set of leaf tuples grows too large for a page, a split is performed and an intermediate inner tuple is inserted. For this to fix the problem, the new inner tuple must divide the set of leaf values into more than one node group. If the operator class's picksplit function fails to do that, the SP-GiST core resorts to extraordinary measures described in Section 66.4.3.
When longValuesOK is true, it is expected that successive levels of the SP-GiST tree will absorb more and more information into the prefixes and node labels of the inner tuples, making the required leaf datum smaller and smaller, so that eventually it will fit on a page. To prevent bugs in operator classes from causing infinite insertion loops, the SP-GiST core will raise an error if the leaf datum does not become any smaller within ten cycles of choose method calls.
66.4.2. SP-GiST Without Node Labels
Some tree algorithms use a fixed set of nodes for each inner tuple; for example, in a quad-tree there are always exactly four nodes corresponding to the four quadrants around the inner tuple's centroid point. In such a case the code typically works with the nodes by number, and there is no need for explicit node labels. To suppress node labels (and thereby save some space), the picksplit function can return NULL for the nodeLabels array, and likewise the choose function can return NULL for the prefixNodeLabels array during a spgSplitTuple action. This will in turn result in nodeLabels being NULL during subsequent calls to choose and inner_consistent. In principle, node labels could be used for some inner tuples and omitted for others in the same index.
When working with an inner tuple having unlabeled nodes, it is an error for choose to return spgAddNode, since the set of nodes is supposed to be fixed in such cases.
66.4.3. “All-the-Same” Inner Tuples
The SP-GiST core can override the results of the operator class's picksplit function when picksplit fails to divide the supplied leaf values into at least two node categories. When this happens, the new inner tuple is created with multiple nodes that each have the same label (if any) that picksplit gave to the one node it did use, and the leaf values are divided at random among these equivalent nodes. The allTheSame flag is set on the inner tuple to warn the choose and inner_consistent functions that the tuple does not have the node set that they might otherwise expect.
When dealing with an allTheSame tuple, a choose result of spgMatchNode is interpreted to mean that the new value can be assigned to any of the equivalent nodes; the core code will ignore the supplied nodeN value and descend into one of the nodes at random (so as to keep the tree balanced). It is an error for choose to return spgAddNode, since that would make the nodes not all equivalent; the spgSplitTuple action must be used if the value to be inserted doesn't match the existing nodes.
When dealing with an allTheSame tuple, the inner_consistent function should return either all or none of the nodes as targets for continuing the index search, since they are all equivalent. This may or may not require any special-case code, depending on how much the inner_consistent function normally assumes about the meaning of the nodes.
