Documentation
¶
Overview ¶
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.
The structure answers exact-match property predicates (for example "every node where email == 'x@y.com'") in O(1) average time. For range predicates use the B+ tree index in package github.com/FlavioCFOliveira/GoGraph/graph/index/btree (Sprint 2, T19).
Index is safe for concurrent use by any number of goroutines; the shard sharding aligns with graph.NodeID's low-bit shard scheme.
Index ¶
- type Binding
- type Index
- func (i *Index[V]) Apply(c index.Change)
- func (i *Index[V]) BoundNode() (label, property string, ok bool)
- func (i *Index[V]) Cardinality(value V) uint64
- func (i *Index[V]) Contains(value V, node graph.NodeID) bool
- func (i *Index[V]) Delete(value V, node graph.NodeID)
- func (i *Index[V]) Deserialize(r io.Reader) error
- func (i *Index[V]) DistinctValues() uint64
- func (i *Index[V]) Insert(value V, node graph.NodeID)
- func (*Index[V]) Kind() string
- func (i *Index[V]) Lookup(value V) *roaring64.Bitmap
- func (i *Index[V]) LookupAppend(value V, dst []uint64) []uint64
- func (i *Index[V]) Serialize(w io.Writer) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Binding ¶ added in v0.3.0
type Binding[V comparable] struct { // Project converts a Change.OldValue / Change.NewValue payload to // the index key type. ok is false when the payload is absent or // not indexable (wrong kind), in which case the event is skipped // for that direction. Project func(v any) (V, bool) // Eligible reports whether the node should currently be present in // the index: it must be live (not deleted) and carry the bound // label, evaluated against the graph's final state. Eligible func(node graph.NodeID) bool // CurrentValue returns the node's current value for the bound // property, projected to the key type. ok is false when the node // is not live, lacks the property, or the value is not indexable. // It is consulted on label add/remove events, which carry no // property payload. CurrentValue func(node graph.NodeID) (V, bool) // Label and Property are the source names behind PropertyID and // LabelID. They let a query planner match the index against a // (label, property) predicate without access to the registries. Label, Property string // PropertyID is the interned property-key identifier this index // covers. Property changes whose Change.Property differs are // ignored. PropertyID uint32 // LabelID is the interned label identifier this index is scoped // to. Label changes whose Change.Label differs are ignored. Note // that interned IDs start at zero, so this field alone cannot mark // an unscoped binding; bindings are always label-scoped. LabelID uint32 }
Binding ties an Index to a single (label, property) pair of a live node graph. A bound index (see NewBound) maintains itself from the index.Manager change fan-out: property writes insert/delete typed keys, and label add/remove events attach/detach a node's current value. An unbound index (see New) ignores the fan-out entirely and is maintained by explicit Index.Insert / Index.Delete calls.
The identifier fields carry interned IDs from the owning graph's registries; the callbacks close over the graph so this package stays free of a dependency on any concrete graph implementation. Because changes are fanned out at commit time — after the transaction's mutations were applied eagerly to the graph — the callbacks observe the transaction's FINAL state, which is exactly the state the index must converge to.
type Index ¶
type Index[V comparable] struct { // contains filtered or unexported fields }
Index maps property values of type V to the NodeIDs that carry them.
Example ¶
ExampleIndex shows a hash index answering an exact-match property predicate: insert (value, NodeID) pairs keyed by a string property, then read back the NodeID set carrying one exact value.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
// An index over a string "email domain" property.
idx := hash.New[string]()
idx.Insert("example.com", graph.NodeID(1))
idx.Insert("example.org", graph.NodeID(2))
idx.Insert("example.com", graph.NodeID(3))
// Lookup answers "every node where domain == example.com".
bm := idx.Lookup("example.com")
fmt.Println("example.com nodes:", bm.ToArray())
fmt.Println("example.com cardinality:", idx.Cardinality("example.com"))
fmt.Println("distinct domains:", idx.DistinctValues())
}
Output: example.com nodes: [1 3] example.com cardinality: 2 distinct domains: 2
func NewBound ¶ added in v0.3.0
func NewBound[V comparable](b Binding[V]) (*Index[V], error)
NewBound returns an empty hash index bound to b. Unlike New, the returned index has a functional Index.Apply: it subscribes to the node property and label changes selected by b and keeps itself consistent with the graph. Returns an error when b is missing its Label, Property, or any of the three callbacks.
func (*Index[V]) Apply ¶
Apply maintains a bound index (see NewBound) from the index.Manager change fan-out; it is a no-op for an unbound index (see New), which cannot reliably interpret arbitrary index.Change values without the caller-supplied binding (property key + value-type coercion).
For a bound index the rules are, per change:
- SetNodeProperty on the bound property: the old value (when present and projectable) is deleted unconditionally, and the new value is inserted when the node is eligible in the graph's final state. The unconditional old-value delete is what clears a stale entry even when a label removal in the same batch is replayed before the property change.
- DelNodeProperty on the bound property: the old value is deleted.
- Add/RemoveNodeLabel on the bound label: the node's CURRENT property value is inserted / deleted. Because changes are applied at commit time the current value is the transaction's final value, so an interleaved property change in the same batch converges to the same final state regardless of replay order.
Apply is idempotent (bitmap add/remove) and safe for concurrent use with readers. Edge changes and changes for other properties/labels are ignored.
What makes CONCURRENT Apply calls safe, restated (rmp #2345) ¶
This used to say "writers are serialised upstream by the engine's single-writer transaction contract". THAT IS FALSE since rmp #2320: commitUnderBarrier runs under a SHARED hold, so two transactions flush their index buffers concurrently and two Apply calls can interleave.
It is nonetheless sound, and the reason is worth stating because it is not the one that was written down. Each mutation is made under its own per-shard lock (Index.Insert, Index.Delete), so no individual add or remove can tear. What serialisation would additionally buy is atomicity of the DELETE-then-INSERT pair in the OpSetNodeProperty arm — and the only interleaving that could strand a stale entry is two transactions writing the SAME node's bound property, which the substrate REFUSES: graph/lpg's property write path takes a write-write conflict check against the node's version-chain head (graph/lpg/property.go), so one of the two aborts and never reaches its Apply at all.
So the ordering guarantee comes from conflict detection on the object, not from exclusion on the writers. If that check is ever narrowed, this comment is the one to revisit.
On recovery from a corrupted snapshot, the index is left empty; callers re-populate via Index.Insert from the live LPG.
func (*Index[V]) BoundNode ¶ added in v0.3.0
BoundNode returns the (label, property) pair this index is bound to, with ok reporting whether the index is bound at all. Query planners use it to decide whether the index may serve a predicate: a bound index covers exactly its (label, property) pair, while an unbound index carries no coverage metadata.
func (*Index[V]) Cardinality ¶
Cardinality returns the number of NodeIDs associated with value. It is exposed for query planners to choose between index lookup and full-scan plans.
func (*Index[V]) Contains ¶
Contains reports whether node is in the set associated with value. Faster than Lookup when only existence matters.
Example ¶
ExampleIndex_Contains shows the point-membership query: Contains reports whether one specific NodeID carries a given value, without materialising the whole NodeID set.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
idx := hash.New[int]()
idx.Insert(404, graph.NodeID(7))
fmt.Println("node 7 has 404:", idx.Contains(404, graph.NodeID(7)))
fmt.Println("node 8 has 404:", idx.Contains(404, graph.NodeID(8)))
// Delete removes one membership; the value disappears once its last
// NodeID is gone.
idx.Delete(404, graph.NodeID(7))
fmt.Println("node 7 has 404 after delete:", idx.Contains(404, graph.NodeID(7)))
}
Output: node 7 has 404: true node 8 has 404: false node 7 has 404 after delete: false
func (*Index[V]) Delete ¶
Delete removes node from the set associated with value. No-op if absent or if value is a NaN (see Index.Insert for the rationale).
func (*Index[V]) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. Returns index.ErrIndexCorrupted on structural or CRC errors and index.ErrIndexValueTypeUnsupported when V cannot be decoded.
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed. Exposed for cardinality estimation by the query planner.
func (*Index[V]) Insert ¶
Insert records that node carries the given value. Insert is a no-op when value is a float32 or float64 NaN: Go map equality is language- fixed (NaN != NaN), so a NaN map key can never be looked up or deleted; skipping it prevents unbounded accumulation (task #1408).
func (*Index[V]) Kind ¶
Kind returns "hash" — satisfies index.Subscriber.
func (*Index[V]) Lookup ¶
Lookup returns a clone of the Roaring bitmap of NodeIDs that carry the given value, or an empty bitmap when the value is unknown or is a NaN (see Index.Insert for the rationale). Clone avoids returning the live bitmap to the caller, which could otherwise be mutated by concurrent writers.
func (*Index[V]) LookupAppend ¶ added in v0.6.0
LookupAppend appends the NodeIDs carrying value to dst in strictly ascending order and returns the extended slice, draining the posting list clone-free under the shard read lock. It is the allocation-light alternative to Index.Lookup for callers that iterate the result once — the dominant equality index-seek shape: a singleton or small posting list yields its ids with no heap allocation when dst has spare capacity, where Lookup would materialise (or clone) a full roaring bitmap plus an iterator. A NaN key or an unknown value appends nothing. The appended ids are an independent snapshot, so the caller may iterate them after the lock is released, exactly as with the cloned bitmap Lookup returns.
func (*Index[V]) Serialize ¶
Serialize writes every (value, NodeID-set) pair currently in the index to w in the format documented in docs/persistence.md:
uint32 magic ('SHSH')
uint32 formatVersion
uint64 entryCount
repeat entryCount times:
uint32 valueLen
[valueLen]byte value (kind-specific encoding)
uint64 idCount
[idCount]uint64 NodeIDs (sorted ascending)
uint32 crc32c (little-endian, covers every byte above)
Returns index.ErrIndexValueTypeUnsupported when V is not one of the documented supported types.
Source Files