Documentation
¶
Overview ¶
Package label provides a Roaring-bitmap-backed inverted index from label identifiers to the NodeIDs that carry them.
The index is the substrate for label-filtered queries such as "find every node with label Person and label Active": each label is represented by a 64-bit Roaring bitmap, and compound queries are answered via bitmap intersection / union, which Roaring implements with run-length and array-bitmap hybrids.
Index is safe for concurrent use.
Index ¶
- type Index
- func (i *Index) Add(label uint32, node graph.NodeID)
- func (i *Index) AddRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Apply(c index.Change)
- func (i *Index) Count(label uint32) uint64
- func (i *Index) Deserialize(r io.Reader) error
- func (i *Index) Has(label uint32, node graph.NodeID) bool
- func (i *Index) Intersect(labels ...uint32) *roaring64.Bitmap
- func (i *Index) IntersectCardinality(labels ...uint32) (uint64, bool)
- func (*Index) Kind() string
- func (i *Index) Remove(label uint32, node graph.NodeID)
- func (i *Index) RemoveRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Scan(label uint32) []graph.NodeID
- func (i *Index) Scope() Scope
- func (i *Index) Serialize(w io.Writer) error
- func (i *Index) Union(labels ...uint32) *roaring64.Bitmap
- type Scope
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index maps label identifiers (uint32) to the set of NodeIDs that carry them. Different LabelID namespaces (vertices, edges) should use distinct Index instances.
Each label's node set is held as an index.NodeSet: a sparse label carried by one or a handful of nodes stays in the inline small-set tier (no per-label roaring overhead), while a dense label — one built via Index.AddRange over a contiguous NodeID band, or grown past the small-set threshold — is a roaring64.Bitmap with its run-container optimality intact. Promotion to the bitmap tier is one-way, so a dense label can never be mis-tiered as a small set (sprint 206, #1585).
Example ¶
ExampleIndex shows membership queries on the label bitmap index: add NodeIDs under a label, test single-node membership with Has, count the carriers, and Scan the full member set in ascending NodeID order.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const labelPerson = uint32(1)
func main() {
idx := label.NewNodeIndex()
idx.Add(labelPerson, graph.NodeID(1))
idx.Add(labelPerson, graph.NodeID(2))
idx.Add(labelPerson, graph.NodeID(3))
fmt.Println("node 2 is Person:", idx.Has(labelPerson, graph.NodeID(2)))
fmt.Println("node 9 is Person:", idx.Has(labelPerson, graph.NodeID(9)))
fmt.Println("Person count:", idx.Count(labelPerson))
fmt.Println("Person members:", idx.Scan(labelPerson))
}
Output: node 2 is Person: true node 9 is Person: false Person count: 3 Person members: [1 2 3]
func NewEdgeIndex ¶
func NewEdgeIndex() *Index
NewEdgeIndex returns an empty index that listens for edge-label changes when registered with a index.Manager.
func NewIndex ¶
func NewIndex() *Index
NewIndex returns an empty index in ScopeNode — equivalent to NewNodeIndex. Existing callers that pre-date the scope field keep this constructor as the default.
func NewNodeIndex ¶
func NewNodeIndex() *Index
NewNodeIndex returns an empty index that listens for node-label changes when registered with a index.Manager.
func (*Index) AddRange ¶
AddRange records that all nodes in [fromNode, toNode] (inclusive) carry label. It uses roaring64.Bitmap.AddRange which represents dense ranges in O(1) space, making bulk ingestion of contiguous NodeID bands efficient.
func (*Index) Apply ¶
Apply dispatches the change to the underlying bitmaps when the change kind matches the index's Scope. Other ops are ignored (the manager fans every change to every subscriber; per-subscriber filtering is the subscriber's responsibility).
func (*Index) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. On any structural problem, truncated payload, or CRC mismatch the function returns a wrapped index.ErrIndexCorrupted and the receiver is restored to the pre-call state.
The implementation reads the whole payload into a buffer, validates the trailing CRC32C against the prefix, then re-parses the prefix to populate the bitmaps. This costs one extra pass over the data but keeps the corruption-detection contract simple and lets the reader reject malformed inputs before any state mutation.
func (*Index) Intersect ¶
Intersect returns a fresh Roaring bitmap containing the NodeIDs that carry every supplied label. Calling with no labels returns the empty bitmap.
Example ¶
ExampleIndex_Intersect shows compound label queries via bitmap set operations. Intersect answers "every node carrying all of these labels"; Union answers "every node carrying any of them".
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const (
labelPerson = uint32(1)
labelActive = uint32(2)
)
func main() {
idx := label.NewNodeIndex()
for _, n := range []graph.NodeID{1, 2, 3} {
idx.Add(labelPerson, n)
}
for _, n := range []graph.NodeID{2, 3, 4} {
idx.Add(labelActive, n)
}
both := idx.Intersect(labelPerson, labelActive)
either := idx.Union(labelPerson, labelActive)
fmt.Println("Person AND Active:", both.ToArray())
fmt.Println("Person OR Active:", either.ToArray())
}
Output: Person AND Active: [2 3] Person OR Active: [1 2 3 4]
func (*Index) IntersectCardinality ¶ added in v0.11.0
IntersectCardinality returns the EXACT number of NodeIDs carrying every supplied label, without materialising the intersection and — in the common case — without allocating at all.
It exists because the size of an intersection is a planner DECISION input, and paying for the answer defeats the purpose of asking. [Intersect] must clone the first label's live bitmap to hand the caller an owned result; a planner that only wants the count would pay that clone for nothing. Measured: gating a multi-label plan through Intersect cost +85.8% B/op on a query the gate then DECLINED, because two bitmaps were materialised purely to be counted.
roaring64.AndCardinality walks the two container arrays by key with skips and accumulates per-container intersection counts, touching no allocation. For the pairwise case this therefore runs directly against the LIVE bitmaps under the index read-lock. Three or more labels have no k-way cardinality primitive, so the pairwise count over the first two is returned; that is an UPPER bound on the k-way result (|L₁ ∩ … ∩ L_k| ≤ |L₁ ∩ L₂|), which is what a conservative gate needs — pass the two smallest labels to make it tight.
A label absent from the index makes the intersection empty, so the result is 0. Fewer than two labels reports (0, false): there is no intersection to size, and the caller must not read the count as authoritative.
Like [Intersect], the whole read happens under ONE RLock, so the answer is a consistent image of the index rather than independently sampled bitmaps.
func (*Index) RemoveRange ¶
RemoveRange records that all nodes in [fromNode, toNode] (inclusive) no longer carry label. Empty bitmaps are deleted so the map does not grow unboundedly after bulk-remove operations.
func (*Index) Scan ¶
Scan returns the sorted slice of NodeIDs that carry label. Returns nil when label has no entries.
func (*Index) Scope ¶
Scope reports which label-event kind the index observes via Index.Apply.
func (*Index) Serialize ¶
Serialize writes the index's per-label bitmaps to w in the format documented in docs/persistence.md. The on-disk layout is:
uint32 magic ('SLBI')
uint32 formatVersion
uint32 labelCount
repeat labelCount times:
uint32 labelID
uint64 bitmapLen
[bitmapLen]byte bitmap (Roaring native binary format)
uint32 crc32c (covers every byte above, little-endian)
Serialize takes the index's RLock for the whole emission so a concurrent writer cannot observe a partially serialised state. The returned error wraps the underlying I/O failure verbatim; the caller treats short writes the same as any other I/O error.
type Scope ¶
type Scope uint8
Scope tags whether the index observes node-label or edge-label changes when registered with index.Manager. The two scopes share a common bitmap shape so the on-disk format is identical.
const ( // ScopeNode listens for [index.OpAddNodeLabel] / [index.OpRemoveNodeLabel] // when the index is registered with a [index.Manager]. It is the // default; callers building an unregistered index can ignore the // scope entirely. ScopeNode Scope = iota + 1 // ScopeEdge listens for [index.OpAddEdgeLabel] / [index.OpRemoveEdgeLabel]. // Edge bitmaps are keyed by the source NodeID, mirroring the LPG // convention exposed by [lpg.Graph.EdgeIndex]. ScopeEdge )
Scope values for NewNodeIndex / NewEdgeIndex.
Source Files