gopgext/spgist
import "gopgext/spgist"
Package spgist writes the support functions of SP-GiST operator classes in Go: space-partitioned trees (quadtrees, k-d trees, radix trees, …), the index method behind PostgreSQL’s point, range, inet and text prefix operator classes. The operator class decides how values are partitioned; SP-GiST does the rest (pages, concurrency, WAL, vacuum).
An SP-GiST index is a tree of inner tuples, each with an optional prefix and a list of nodes (child pointers, each with an optional label), and leaf tuples holding a leaf value per row. The extension registers an OpClass under the name of its operator class (in main or a package initializer):
spgist.Register("pt_quad_ops", spgist.OpClass{
Prefixes: true, // inner tuples have a prefix (a centroid)
CanReturnData: true, // leaves hold the values: index-only scans
Choose: choose, // which node of an inner tuple a value goes to
PickSplit: pickSplit, // an inner tuple for a page full of leaves
InnerConsistent: inner, // which nodes may hold matches (and their distances)
LeafConsistent: leaf, // does a leaf match (and its distance)?
})
and its sql/ files declare the support functions, which all use the C symbols of this package, and the operator class:
CREATE FUNCTION pt_spg_config(internal, internal) RETURNS void
AS 'MODULE_PATHNAME', 'gopgext_spgist_config' LANGUAGE C STRICT;
CREATE FUNCTION pt_spg_choose(internal, internal) RETURNS void
AS 'MODULE_PATHNAME', 'gopgext_spgist_choose' LANGUAGE C STRICT;
CREATE FUNCTION pt_spg_picksplit(internal, internal) RETURNS void
AS 'MODULE_PATHNAME', 'gopgext_spgist_picksplit' LANGUAGE C STRICT;
CREATE FUNCTION pt_spg_inner_consistent(internal, internal) RETURNS void
AS 'MODULE_PATHNAME', 'gopgext_spgist_inner_consistent' LANGUAGE C STRICT;
CREATE FUNCTION pt_spg_leaf_consistent(internal, internal) RETURNS boolean
AS 'MODULE_PATHNAME', 'gopgext_spgist_leaf_consistent' LANGUAGE C STRICT;
-- only with Compress:
CREATE FUNCTION pt_spg_compress(pt) RETURNS bytea
AS 'MODULE_PATHNAME', 'gopgext_spgist_compress' LANGUAGE C STRICT;
CREATE OPERATOR CLASS pt_quad_ops DEFAULT FOR TYPE pt USING spgist AS
OPERATOR 6 ~= , OPERATOR 8 <@ (pt, rect),
OPERATOR 15 <-> (pt, pt) FOR ORDER BY float_ops,
FUNCTION 1 pt_spg_config(internal, internal),
FUNCTION 2 pt_spg_choose(internal, internal),
FUNCTION 3 pt_spg_picksplit(internal, internal),
FUNCTION 4 pt_spg_inner_consistent(internal, internal),
FUNCTION 5 pt_spg_leaf_consistent(internal, internal);
The functions find their OpClass through the operator family they belong to (named like the operator class, unless it was created with FAMILY).
Values: indexed values and queries are variable-length values (types stored like bytea, e.g. declared with //gopgext:type over pg.Varlena), and so are prefixes, labels, leaf values (the indexed value, or what Compress makes of it: then stored as bytea), reconstructed values and traversal values. The functions get their bytes, valid during the call only (copy them to keep them), and return new ones. A nil prefix or label list means none (an empty, non-nil []byte is an empty value).
Searches: Keys are the WHERE conditions (strategy numbers of the operator class’s operators, with their right-hand values) and OrderBys the ORDER BY ordering operators (k-NN). InnerConsistent returns the nodes to visit, each with an optional reconstructed value (e.g. the prefix of a text built so far) and traversal value (anything the operator class wants to carry down, e.g. the region the node covers) and, for OrderBys, lower bounds of the distances below it. LeafConsistent decides on a leaf, with exact distances (or lower bounds with RecheckDistances). Recheck makes PostgreSQL evaluate the operator on the row. NULLs never reach the functions: SP-GiST handles them.
Index#
func Register(family string, oc OpClass)- type Action
- type ChooseIn
- type ChooseOut
- type Inner
- type Key
- type LeafOut
- type OpClass
- type PickSplitIn
- type PickSplitOut
- type Scan
- type Visit
Functions#
func Register#
func Register(family string, oc OpClass)
Register registers the operator class whose support functions belong to the operator family family (the name of the operator class, unless it was created with FAMILY).
Types#
type Action#
type Action int
Action is what Choose decides.
const (
MatchNode Action = 1 // descend into node Node
AddNode Action = 2 // add a node labeled Label at position Node, then retry
SplitTuple Action = 3 // split the inner tuple (its prefix doesn't fit), then retry
)
type ChooseIn#
type ChooseIn struct {
Value []byte // the original indexed value
Leaf []byte // the leaf value so far (Value, compressed, minus what levels above consumed)
Level int // the level of the inner tuple (from 0)
Inner Inner
}
ChooseIn describes a value being inserted at an inner tuple.
type ChooseOut#
type ChooseOut struct {
Action Action
// MatchNode: the node, how much to add to the level, and the leaf value
// to carry down (nil: Leaf unchanged).
// AddNode: where to insert the new node.
Node int
LevelAdd int
Rest []byte
// AddNode: the new node's label (nil without labels).
Label []byte
// SplitTuple: a new upper inner tuple (prefix Prefix, NNodes nodes or
// Labels) whose node ChildNode points to a new lower inner tuple with
// prefix PostfixPrefix and all the old nodes.
Prefix []byte
NNodes int
Labels [][]byte
ChildNode int
PostfixPrefix []byte
}
ChooseOut is the decision of Choose.
type Inner#
type Inner struct {
// AllTheSame is set for inner tuples whose nodes are all equivalent
// (SP-GiST made them so when PickSplit put every value in one node):
// InnerConsistent should then visit all nodes or none, and Choose must
// return MatchNode (SP-GiST picks the node) or SplitTuple.
AllTheSame bool
Prefix []byte // nil: no prefix
NNodes int // number of nodes
Labels [][]byte // node labels (nil: the operator class has no labels)
}
Inner is an inner tuple.
type Key#
type Key struct {
Strategy int
Query []byte
}
Key is a search condition (WHERE col op Query) or an ordering (ORDER BY col op Query): the operator’s strategy number and its right-hand value.
type LeafOut#
type LeafOut struct {
Match bool
Recheck bool // the operators must be checked on the row
Distances []float64 // one per OrderBys (when Match)
RecheckDistances bool // Distances are lower bounds
// Value is the original value, for index-only scans (nil: the leaf
// value, right without Compress).
Value []byte
}
LeafOut is the result of LeafConsistent.
type OpClass#
type OpClass struct {
Prefixes bool // inner tuples can have prefixes
Labels bool // nodes have labels
CanReturnData bool // leaves can give back the original value (index-only scans)
LongValuesOK bool // values can be longer than a page (suffixes split over levels)
// Compress returns the leaf value of an indexed value (stored as
// bytea). nil: the leaf value is the indexed value.
Compress func(value []byte) ([]byte, error)
Choose func(in ChooseIn) ChooseOut
PickSplit func(in PickSplitIn) PickSplitOut
InnerConsistent func(scan Scan, inner Inner) []Visit
LeafConsistent func(scan Scan, leaf []byte) LeafOut
}
OpClass is an SP-GiST operator class. Choose, PickSplit, InnerConsistent and LeafConsistent are required.
type PickSplitIn#
type PickSplitIn struct {
Leaves [][]byte
Level int
}
PickSplitIn are the leaf values of a full page, to be placed under a new inner tuple.
type PickSplitOut#
type PickSplitOut struct {
Prefix []byte
NNodes int
Labels [][]byte
Nodes []int
Leaves [][]byte
}
PickSplitOut is the new inner tuple: its prefix, nodes (NNodes, or Labels with one label per node), the node of each leaf, and the leaf value stored for each under its node (nil: unchanged).
type Scan#
type Scan struct {
Keys []Key
OrderBys []Key
Reconstructed []byte // from the parent's Visit (nil at the root)
Traversal []byte // from the parent's Visit (nil at the root)
Level int
ReturnData bool // index-only scan: the original value must be returned
}
Scan is the search state at a tuple.
type Visit#
type Visit struct {
Node int
LevelAdd int
Reconstructed []byte // passed to the child (nil: none)
Traversal []byte // passed to the child (nil: none)
Distances []float64 // lower bound of the distances below, one per OrderBys
}
Visit is a node InnerConsistent visits.