Documentation
¶
Overview ¶
Package index coordinates the secondary indexes attached to a labelled property graph.
A Manager owns a set of named indexes (label bitmap, hash exact-match, B+ tree range) and fans out mutations to every index that subscribes to the affected property or label. The fan-out is best-effort sequential: failures in one subscriber do not abort the others (subscribers are independent and idempotent).
Index ¶
- Variables
- type Change
- type ChangeOp
- type Manager
- func (m *Manager) Apply(c Change)
- func (m *Manager) ApplyBatch(changes []Change)
- func (m *Manager) Count() int
- func (m *Manager) CreateIndex(name string, sub Subscriber) error
- func (m *Manager) DropIndex(name string) error
- func (m *Manager) GetIndex(name string) (Subscriber, error)
- func (m *Manager) ListIndexes() []string
- type NodeSet
- func (s *NodeSet) Add(node uint64) (wasEmpty bool)
- func (s *NodeSet) AddRange(from, to uint64)
- func (s *NodeSet) AppendTo(dst []uint64) []uint64
- func (s *NodeSet) Bitmap() (bm *roaring64.Bitmap, shared bool)
- func (s *NodeSet) Cardinality() uint64
- func (s *NodeSet) Contains(node uint64) bool
- func (s *NodeSet) IsEmpty() bool
- func (s *NodeSet) Minimum() uint64
- func (s *NodeSet) OrInto(dst *roaring64.Bitmap)
- func (s *NodeSet) Remove(node uint64) (nowEmpty bool)
- func (s *NodeSet) RemoveRange(from, to uint64) (nowEmpty bool)
- func (s *NodeSet) ToArray() []uint64
- type Serializer
- type Subscriber
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrIndexCorrupted = errors.New("index: serialized form corrupted")
ErrIndexCorrupted is returned by Serializer.Deserialize when the serialised form is structurally malformed or its CRC32C trailer does not match the payload. Callers (snapshot recovery in particular) treat this as "rebuild from the LPG" rather than as a fatal error.
var ErrIndexExists = errors.New("index: an index by that name already exists")
ErrIndexExists is returned by Manager.CreateIndex when the name is already in use.
var ErrIndexNotFound = errors.New("index: no index by that name")
ErrIndexNotFound is returned by Manager.DropIndex or Manager.GetIndex when the named index does not exist.
var ErrIndexValueTypeUnsupported = errors.New("index: value type not supported for serialization")
ErrIndexValueTypeUnsupported is returned by a generic index's Serialize / Deserialize methods when the value-type parameter is not in the supported on-disk encoding set (currently: string). Callers can convert their value type to string before registering the index for snapshot durability.
Functions ¶
This section is empty.
Types ¶
type Change ¶
type Change struct {
Op ChangeOp
Node graph.NodeID
Dst graph.NodeID // edge changes only
Property uint32 // 0 when not a property change
Label uint32 // 0 when not a label change
// OldValue and NewValue are present only for property changes.
// They are typed as any so this package stays generic across
// every PropertyValue kind without importing the lpg package.
OldValue any
NewValue any
}
Change describes a single mutation observed by the Manager. Each subscriber inspects the relevant fields and decides whether to update its own state.
Property and Label fields are interned identifiers from the owning graph's registries (lpg.PropertyKeyID / lpg.LabelID), surfaced as uint32 so this package does not import the lpg package and create a cycle.
func (Change) IsEdgeChange ¶
IsEdgeChange reports whether the change concerns an edge.
type Manager ¶
type Manager struct {
// contains filtered or unexported fields
}
Manager owns the set of named indexes attached to a graph and fans out mutations to every subscriber.
Manager is safe for concurrent use.
Example ¶
ExampleManager shows the Manager lifecycle: register a concrete index under a name, list and count the registered indexes, and reject a duplicate registration with ErrIndexExists.
package main
import (
"errors"
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/index"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
func main() {
m := index.NewManager()
if err := m.CreateIndex("by_label", label.NewNodeIndex()); err != nil {
fmt.Println("unexpected:", err)
}
// Re-registering the same name is rejected.
err := m.CreateIndex("by_label", label.NewNodeIndex())
fmt.Println("duplicate is ErrIndexExists:", errors.Is(err, index.ErrIndexExists))
fmt.Println("count:", m.Count())
fmt.Println("names:", m.ListIndexes())
}
Output: duplicate is ErrIndexExists: true count: 1 names: [by_label]
func (*Manager) Apply ¶
Apply fans c out to every registered subscriber under a read lock so subscribers cannot be unregistered mid-update. The Manager itself does not enforce ordering across subscribers — each subscriber is expected to be order-independent on the change stream it observes.
Example ¶
ExampleManager_Apply shows the Manager fanning a change out to every registered subscriber. The label index observes OpAddNodeLabel events and can then be queried back through GetIndex for the NodeIDs that carry a given label.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
func main() {
const labelPerson = uint32(7)
m := index.NewManager()
_ = m.CreateIndex("node_labels", label.NewNodeIndex())
// A mutation observed by the owning graph is fanned out to every
// subscriber. Here two nodes acquire the Person label.
m.Apply(index.Change{Op: index.OpAddNodeLabel, Node: graph.NodeID(1), Label: labelPerson})
m.Apply(index.Change{Op: index.OpAddNodeLabel, Node: graph.NodeID(4), Label: labelPerson})
// Recover the concrete index to run a query.
sub, _ := m.GetIndex("node_labels")
idx := sub.(*label.Index)
fmt.Println("kind:", idx.Kind())
fmt.Println("Person count:", idx.Count(labelPerson))
fmt.Println("Person members:", idx.Scan(labelPerson))
}
Output: kind: label Person count: 2 Person members: [1 4]
func (*Manager) ApplyBatch ¶
ApplyBatch fans an ordered slice of changes out to every subscriber in order. The whole batch is applied under one read lock; this is the substrate consumed by future transaction integration (Sprint 3).
func (*Manager) Count ¶
Count returns the number of currently registered indexes. It is safe to call on a nil Manager and returns 0 in that case.
func (*Manager) CreateIndex ¶
func (m *Manager) CreateIndex(name string, sub Subscriber) error
CreateIndex registers sub under name. Returns ErrIndexExists when the name is already taken.
func (*Manager) GetIndex ¶
func (m *Manager) GetIndex(name string) (Subscriber, error)
GetIndex returns the subscriber registered under name. It is safe to call on a nil Manager and returns ErrIndexNotFound in that case.
func (*Manager) ListIndexes ¶
ListIndexes returns the names of every currently registered index in unspecified order. It is safe to call on a nil Manager and returns nil in that case.
type NodeSet ¶ added in v0.6.0
type NodeSet struct {
// contains filtered or unexported fields
}
NodeSet is the per-key node-set representation shared by the btree, hash, and label indexes. The zero value is a valid empty set. See the package-level nodeset.go documentation for the state machine and the query/serialization/GC-safety invariants.
Concurrency: a NodeSet is not safe for concurrent use on its own. It is embedded by value in an index (a btree leaf slot, a hash shard map, or the label-index map), and every read and mutation is serialised by that owning index's lock; a NodeSet is never shared across goroutines outside that discipline. Lookup paths that hand a set's contents to a caller copy out under the read lock, so the returned data is safe for concurrent use.
The two fields form a tagged union resolved solely by meta's low two bits (see the state* constants). ptr is GC-scanned and is always nil or a real Go pointer; it never carries tag bits.
func NodeSetFromBitmap ¶ added in v0.6.0
NodeSetFromBitmap returns the cheapest NodeSet representation of bm. A bitmap whose cardinality fits the inline small-set tier is down-converted (its few sorted ids extracted) so a sparse entry reloaded from a roaring image regains the memory win; a denser bitmap is kept on the bitmap tier WITHOUT extracting its (potentially huge) id array, so a dense label costs no transient O(cardinality) slice. Ownership of bm transfers to the set when it is kept; when down-converted, bm is no longer referenced.
It is the label index's deserialization adaptor: that index persists the roaring native image, so it reads back a bitmap and calls this to recover the tiered in-memory shape (sprint 206, #1585).
func NodeSetFromSorted ¶ added in v0.6.0
NodeSetFromSorted builds a NodeSet from an already strictly-ascending id slice. It is the deserialization constructor: the btree and hash readers parse the logical sorted NodeID list and hand it here, getting the cheapest representation for that cardinality (singleton/small/ bitmap) without re-sorting. The caller guarantees ids is sorted ascending with no duplicates.
func (*NodeSet) Add ¶ added in v0.6.0
Add inserts node into the set, preserving ascending order and promoting to a bitmap when the small tier would overflow. Adding a node already present is a no-op (set semantics). Returns true when the set was previously empty (so a caller maintaining a distinct-key count can detect a brand-new entry).
func (*NodeSet) AddRange ¶ added in v0.6.0
AddRange adds every id in [from, to] (inclusive) to the set. It always promotes to (or stays) a bitmap and uses roaring's run-container AddRange, so a contiguous band of NodeIDs is stored in O(1) space. This is the bulk-ingest fast path the label index relies on for dense labels; it is intentionally the ONLY entry point that can create a bitmap without first crossing smallSetMax, and a set that takes an AddRange is permanently a bitmap (#1585).
func (*NodeSet) AppendTo ¶ added in v0.6.0
AppendTo appends every NodeID in strictly ascending order — the same order as ToArray — to dst and returns the extended slice, WITHOUT materialising a throwaway bitmap for the inline (singleton/small) states. It is the allocation-light way to drain a set into a caller-owned buffer under the index read lock: a singleton or small set appends straight from the inline fields, so a caller whose dst has spare capacity (e.g. a reused seek buffer) pays no heap allocation at all. Only the promoted bitmap state allocates a single iterator. The appended ids are an independent snapshot the caller may read after releasing the lock.
func (*NodeSet) Bitmap ¶ added in v0.6.0
Bitmap returns the set as a *roaring64.Bitmap. When the set is already in the bitmap state the live bitmap is returned (the caller must NOT mutate it); otherwise a fresh bitmap is materialised from the sorted ids. The materialised image is byte-identical under roaring's content-deterministic WriteTo to a bitmap that held the same ids all along, which is what keeps the label index's roaring-native on-disk format unchanged across this refactor (storage-engine-auditor, #1585).
shared reports whether the returned bitmap aliases the set's live bitmap (true only in the bitmap state); callers that need an independent copy must Clone when shared is true.
func (*NodeSet) Cardinality ¶ added in v0.6.0
Cardinality returns the number of NodeIDs in the set.
func (*NodeSet) Contains ¶ added in v0.6.0
Contains reports whether node is in the set. O(1) for the singleton state, O(log n) for the small array, and roaring's container probe for the bitmap state.
func (*NodeSet) Minimum ¶ added in v0.6.0
Minimum returns the smallest NodeID in the set. The caller must ensure the set is non-empty; on an empty set it returns 0.
func (*NodeSet) OrInto ¶ added in v0.6.0
OrInto adds every NodeID in the set to dst (set union into dst), preserving dst's ascending order. It is the allocation-light way to fold a small set into a destination bitmap during a range scan: a singleton becomes a single Add, a small set an AddMany of the sorted ids (which hits roaring's batch-by-high-bits fast path), and a bitmap a roaring Or — never materialising a throwaway bitmap for the inline states (graph-theory-expert, #1584).
func (*NodeSet) Remove ¶ added in v0.6.0
Remove deletes node from the set. No-op when absent. A NodeSet never demotes: removing from a bitmap leaves it a bitmap even if its cardinality drops to one (promote-and-never-demote, #1584). Returns true when the set became EMPTY as a result (so a caller maintaining a distinct-key count can drop the key).
func (*NodeSet) RemoveRange ¶ added in v0.6.0
RemoveRange removes every id in [from, to] (inclusive). On an inline (non-bitmap) set it removes the few covered ids individually; on a bitmap it uses roaring's RemoveRange. A NodeSet never demotes, so a bitmap stays a bitmap. Returns true when the set became EMPTY.
func (*NodeSet) ToArray ¶ added in v0.6.0
ToArray returns the NodeIDs in strictly ascending order as a freshly allocated slice the caller owns. This is the canonical iteration order every index consumer relies on, and the exact sorted list the btree and hash on-disk formats serialize — so it is representation-independent.
type Serializer ¶
Serializer is implemented by indexes that can persist and restore their internal state through an io.Writer / io.Reader pair. The Manager type-asserts every registered Subscriber to this interface during snapshot writes; subscribers that do not implement Serializer are silently skipped (rebuild-on-restart).
Implementations must:
- Write a fixed self-describing header (magic + format version) so a future format bump can be detected on read.
- Cover the entire on-disk payload with a CRC32C trailer (uint32 little-endian) so corruption surfaces as ErrIndexCorrupted.
- Be safe for concurrent reads from other goroutines while Serialize executes (typically by holding the index's own RLock for the duration of the write).
Deserialize replaces the receiver's state with the contents of r. On any structural problem or CRC mismatch the function returns a wrapped ErrIndexCorrupted and leaves the receiver in its previous state.
type Subscriber ¶
type Subscriber interface {
Apply(Change)
// Kind returns a short stable identifier of the underlying index
// implementation, used for introspection (e.g. "label", "hash",
// "btree").
Kind() string
}
Subscriber is implemented by every concrete index that wishes to receive change events from the Manager. The Apply method must be idempotent: replays of the same change must not produce duplicate state.
Implementations must be safe for concurrent use: the Manager fans changes out to Apply while query goroutines read the same index concurrently, so a concrete index synchronises its own state internally (the built-in hash and label indexes hold an RWMutex). The Manager itself does not serialise an index's reads against its Apply calls.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package btree provides an order-preserving property index over a constraints.Ordered value type, answering range predicates against the NodeIDs that carry each value.
|
Package btree provides an order-preserving property index over a constraints.Ordered value type, answering range predicates against the NodeIDs that carry each value. |
|
Package hash provides a sharded hash index from arbitrary comparable property values to the set of NodeIDs that carry them, represented as a 64-bit Roaring bitmap.
|
Package hash provides a sharded hash index from arbitrary comparable property values to the set of NodeIDs that carry them, represented as a 64-bit Roaring bitmap. |
|
Package label provides a Roaring-bitmap-backed inverted index from label identifiers to the NodeIDs that carry them.
|
Package label provides a Roaring-bitmap-backed inverted index from label identifiers to the NodeIDs that carry them. |