index

package
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 6, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type EdgePropEntry 

type EdgePropEntry struct {
	ID    store.EdgeID
	Key   string
	Value []byte
}

EdgePropEntry is a single (edgeID, key, value) tuple.

type NodePropEntry 

type NodePropEntry struct {
	ID    store.NodeID
	Key   string
	Value []byte
}

NodePropEntry is a single (nodeID, key, value) tuple used when enumerating all indexed node property entries (e.g. for WAL re-emission after compaction).

type PropertyIndex 

type PropertyIndex struct {
	// contains filtered or unexported fields
}

PropertyIndex is a secondary index from (property key, encoded value) to the set of node or edge IDs that carry that property value.

Properties in Graphene are stored as opaque msgpack blobs. The property index operates one level above raw storage: callers decode the blob (or know the encoding) and explicitly register individual key-value pairs for indexing by calling IndexNode / IndexEdge. This keeps the storage layer schema-agnostic while still enabling O(1) lookups on frequently queried fields (e.g. hash, filename, timestamp string).

value is stored internally as a string key derived from the raw byte slice, so any deterministic encoding (msgpack, raw bytes, string cast) works as long as the same encoding is used for both IndexNode and NodesByProperty calls.

Structure

  • Postings lists are kept sorted by ID. Membership and insertion are O(log n) + memmove, lookups return an already-ordered slice (so the query path can skip sorting), and duplicate registrations are idempotent.
  • A reverse map from ID to its registered (key, value) pairs makes RemoveNode / RemoveEdge proportional to that entity's own entries rather than to the size of the whole index.

Sharding

The index is split into propertyShards independent shards, chosen by hashing the property key. One global lock meant that registering "sha256" on one goroutine blocked a lookup of "bucket" on another even though the two share no state; with per-key shards, unrelated keys no longer contend.

**The reverse map is sharded alongside the forward map, not by ID.** Each shard holds only the (key, value) pairs for keys it owns, so removing an entity is a pass over the shards with each one taking its own lock independently — no operation ever needs two shard locks at once, which means there is no lock ordering to get wrong and no deadlock to reason about. The cost is that RemoveNode touches every shard instead of one map, which is a handful of lookups against work that is already proportional to the entity's entries.

PropertyIndex is safe for concurrent use.

func NewPropertyIndex 

func NewPropertyIndex() *PropertyIndex

NewPropertyIndex returns an empty PropertyIndex.

func (*PropertyIndex) DeclareOrderedEdgeKey 

func (p *PropertyIndex) DeclareOrderedEdgeKey(key string)

DeclareOrderedEdgeKey is DeclareOrderedNodeKey for edge properties.

func (*PropertyIndex) DeclareOrderedNodeKey 

func (p *PropertyIndex) DeclareOrderedNodeKey(key string)

DeclareOrderedNodeKey builds and maintains an ordered index over key, so that range and prefix filters on it are answered by binary search instead of a scan of every entry under that key.

Entries already registered under key are absorbed, so this can be called at any point in a store's life.

Declaring a key changes how its range predicates compare: from the scan path's "numeric when both sides parse, byte-wise otherwise" rule to plain byte order. Encode values with index/encoding (or use a naturally byte-ordered form such as fixed-width zero-padded digits or hex) so byte order means what you intend. Equality lookups are unaffected.

func (*PropertyIndex) EdgeCardinality 

func (p *PropertyIndex) EdgeCardinality(key string, value []byte) int

EdgeCardinality returns the number of edge IDs registered under key=value.

func (*PropertyIndex) EdgeEntries 

func (p *PropertyIndex) EdgeEntries() []EdgePropEntry

EdgeEntries returns all indexed edge property entries, ordered by (Key, Value, ID). See NodeEntries for why the order is a contract.

func (*PropertyIndex) EdgesByProperty 

func (p *PropertyIndex) EdgesByProperty(key string, value []byte) []store.EdgeID

EdgesByProperty returns all EdgeIDs that have an indexed entry for key=value, in ascending ID order. Returns nil if no match.

func (*PropertyIndex) EdgesMatchingOrdered 

func (p *PropertyIndex) EdgesMatchingOrdered(dst []store.EdgeID, f store.PropertyFilter) ([]store.EdgeID, bool)

EdgesMatchingOrdered is NodesMatchingOrdered for edge properties.

func (*PropertyIndex) EntryCounts 

func (p *PropertyIndex) EntryCounts() (nodes, edges int)

EntryCounts returns the number of indexed (id, key, value) triples, split by entity kind. Both are exact: each shard keeps a running count, so this does not walk the index.

func (*PropertyIndex) ForEachEdgeEntry 

func (p *PropertyIndex) ForEachEdgeEntry(key string, fn func(id store.EdgeID, value []byte) bool)

ForEachEdgeEntry calls fn for every (id, value) registered under key. Return false from fn to stop early.

func (*PropertyIndex) ForEachEdgeValue 

func (p *PropertyIndex) ForEachEdgeValue(key string, fn func(value []byte, ids []store.EdgeID) bool)

ForEachEdgeValue is ForEachNodeValue for edge properties.

func (*PropertyIndex) ForEachNodeEntry 

func (p *PropertyIndex) ForEachNodeEntry(key string, fn func(id store.NodeID, value []byte) bool)

ForEachNodeEntry calls fn for every (id, value) registered under key, holding only a read lock and allocating nothing. Return false from fn to stop early.

This is the scan path for operators the index cannot answer directly (prefix, contains, and the ordered comparisons). It touches only the buckets belonging to key, unlike NodeEntries which materialises the entire index.

func (*PropertyIndex) ForEachNodeValue 

func (p *PropertyIndex) ForEachNodeValue(key string, fn func(value []byte, ids []store.NodeID) bool)

ForEachNodeValue calls fn once per distinct value under key, with that value's id list. Prefer it over ForEachNodeEntry when the callback depends only on the value — a filter scan does, and this makes it one comparison per value instead of one per entry.

The id slice is owned by the index: read it, do not retain or mutate it.

func (*PropertyIndex) IndexEdge 

func (p *PropertyIndex) IndexEdge(id store.EdgeID, key string, value []byte)

IndexEdge records that edgeID has property key=value. Re-registering an identical (id, key, value) triple is a no-op.

func (*PropertyIndex) IndexNode 

func (p *PropertyIndex) IndexNode(id store.NodeID, key string, value []byte)

IndexNode records that nodeID has property key=value. Re-registering an identical (id, key, value) triple is a no-op.

func (*PropertyIndex) IndexedEdgeIDs 

func (p *PropertyIndex) IndexedEdgeIDs() []store.EdgeID

IndexedEdgeIDs returns every edge ID that has at least one indexed entry.

func (*PropertyIndex) IndexedNodeIDs 

func (p *PropertyIndex) IndexedNodeIDs() []store.NodeID

IndexedNodeIDs returns every node ID that has at least one indexed entry. Used by integrity checks to detect postings that outlived their entity.

func (*PropertyIndex) NarrowEdgesByFilters 

func (p *PropertyIndex) NarrowEdgesByFilters(candidates []store.EdgeID, filters []store.PropertyFilter, skip int) []store.EdgeID

NarrowEdgesByFilters is NarrowNodesByFilters for edge properties, and consumes its candidates slice in the same way.

func (*PropertyIndex) NarrowNodesByFilters 

func (p *PropertyIndex) NarrowNodesByFilters(candidates []store.NodeID, filters []store.PropertyFilter, skip int) []store.NodeID

NarrowNodesByFilters returns the ascending subset of candidates matching every filter. candidates must be ascending and deduplicated; the result is too.

**The candidates slice is consumed.** Filtering happens in place and the result reuses its backing array, so the caller must not use candidates afterwards — the same contract store.IntersectSortedIDs carries, for the same reason.

skip names a filter already applied to produce candidates, by index into filters, or -1. It is not re-evaluated.

This implements MatchAll only. Under MatchAny a candidate set driven by one filter is not a superset of the answer, so there is nothing to narrow.

func (*PropertyIndex) NodeCardinality 

func (p *PropertyIndex) NodeCardinality(key string, value []byte) int

NodeCardinality returns the number of node IDs registered under key=value without copying the postings list. Used by the query planner to pick the most selective driving index.

func (*PropertyIndex) NodeEntries 

func (p *PropertyIndex) NodeEntries() []NodePropEntry

NodeEntries returns all indexed node property entries, ordered by (Key, Value, ID).

The order is part of the contract, not an accident of enumeration. Entries live in per-shard maps, and Go randomises map iteration order on every range, so an unordered walk enumerates the same index differently on every call. disk.Store.Compact() writes these entries straight into the CSR's index section, which made the serialised image differ byte-for-byte between two compactions of an identical store. That makes the file's digest useless as an identity for its contents: a snapshot hash is not reproducible, and two parties holding the same evidence cannot agree on one. Pinned by TestCompact_IsByteDeterministic.

The order follows the index's own nesting — key, then value, then the postings list, which is already ascending by ID — so ordering costs one sort of the keys and one of each key's distinct values, and the entries are then emitted straight into place. Ordering by ID instead would group an entity's entries contiguously, which reads slightly better for a future per-entity digest, but it is a transpose of the layout above: it measured ~2.2x slower on the compaction path even after sorting a packed key and permuting, because every entry lands in a random slot. Determinism is what is actually required here, and this order delivers it for close to nothing.

This materialises the whole index; query paths should use ForEachNodeEntry.

func (*PropertyIndex) NodesByProperty 

func (p *PropertyIndex) NodesByProperty(key string, value []byte) []store.NodeID

NodesByProperty returns all NodeIDs that have an indexed entry for key=value, in ascending ID order. Returns nil if no match.

func (*PropertyIndex) NodesMatchingOrdered 

func (p *PropertyIndex) NodesMatchingOrdered(dst []store.NodeID, f store.PropertyFilter) ([]store.NodeID, bool)

NodesMatchingOrdered appends the IDs matching a range or prefix filter to dst, using the ordered index for f.Key. ok is false when the key is not declared ordered or the operator cannot be served from an ordering, in which case the caller must fall back to scanning the key's entries.

Results are appended in ascending value order, then ascending ID within each value — not in overall ID order, so callers that need sorted IDs must sort.

func (*PropertyIndex) OrderedEdgeKeys 

func (p *PropertyIndex) OrderedEdgeKeys() []string

OrderedEdgeKeys returns the declared ordered edge keys, sorted.

func (*PropertyIndex) OrderedNodeKeys 

func (p *PropertyIndex) OrderedNodeKeys() []string

OrderedNodeKeys returns the declared ordered node keys, sorted.

func (*PropertyIndex) PlanEdgeResiduals 

func (p *PropertyIndex) PlanEdgeResiduals(filters []store.PropertyFilter, skip, candidateCount int) []store.ResidualStep

PlanEdgeResiduals is PlanNodeResiduals for edge properties.

func (*PropertyIndex) PlanNodeResiduals 

func (p *PropertyIndex) PlanNodeResiduals(filters []store.PropertyFilter, skip, candidateCount int) []store.ResidualStep

PlanNodeResiduals reports the residual filters in the order they will be applied, with the cost estimate for each. It backs Graph.ExplainNodeQuery.

`Probe` is reported as the decision would be made at the *start* of the residual pass, against candidateCount. The executor re-decides it per step, because each step shrinks the candidate set — so a filter reported here as building its own set may end up probed once an earlier filter has thinned the candidates. The order and the costs are exact; that one flag is a forecast.

func (*PropertyIndex) RemoveEdge 

func (p *PropertyIndex) RemoveEdge(id store.EdgeID)

RemoveEdge drops every indexed entry for the given edge id across all keys and values. Buckets left empty are removed so they do not accumulate.

func (*PropertyIndex) RemoveNode 

func (p *PropertyIndex) RemoveNode(id store.NodeID)

RemoveNode drops every indexed entry for the given node id across all keys and values. Buckets left empty are removed so they do not accumulate.

func (*PropertyIndex) Verify 

func (p *PropertyIndex) Verify() error

Verify checks the index's internal invariants and returns the first violation found. It is intended for tests, for `Graph.VerifyIndexes`, and for validating an index that was loaded from disk rather than built in memory.

The invariants are:

  • every postings list is strictly ascending (sorted, no duplicates);
  • every (id, key, value) in a postings list has exactly one matching entry in the reverse map, and vice versa;
  • no bucket or key map is left empty;
  • the cached entry count matches the number of postings entries.

It cannot check whether an indexed value still reflects the entity's current properties — values are caller-encoded opaque bytes, so only the caller knows that. See store.ReindexPolicy for how that staleness is managed.

Source Files

View all Source files

Directories

Path Synopsis
Package encoding provides order-preserving encodings for property values.
 Package encoding provides order-preserving encodings for property values.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.