Documentation
¶
Overview ¶
Package count holds the derived, non-durable relationship count-store that backs exact cardinality estimates for the Cypher planner (design docs/count-store-design.md, task #2082). It maintains three relationship statistics keyed by the stable interned ids of the graph's single label/relationship-type registry:
E(relType) — live edges of a relationship type
D(label, relType, dir)— degree-sum: edge endpoints of relType in a direction
whose this-end node carries label
T(labelA, relType, labelB) — live edges (:labelA)-[:relType]->(:labelB)
The node statistic N(label) is NOT stored here; it is read from the existing label index (see cypher/api.go ResolveLabelCount).
Structure ¶
Each cell is an atomic.Int64 held in one of a fixed number of shards; a cell is created on first observation of a combination and DELETED when its counter returns to zero, so the store's footprint is bounded by the number of currently-observed schema combinations — a function of schema cardinality, never of |V| or |E| (design §2.3). Keys are the registry's uint32 ids, so no string touches the hot path.
Concurrency contract ¶
The Store is safe for concurrent use with the following discipline, which the Cypher engine already provides: all MUTATIONS (Store.Apply, Store.MarkDirty, Store.RecomputeReset) are serialised by the engine's write barrier (visMu.Lock in commitUnderBarrier), and all READS (Store.CountE/Store.CountD/ Store.CountT and the dirty predicates) run under the query's read barrier (visMu.RLock in Graph.View). The per-shard sync.RWMutex and the dirty-set mutex are defence-in-depth that keep any non-barrier access path race-free; the atomic cells make an individual counter read lock-free regardless. The store spawns no goroutines.
Index ¶
- type Delta
- type Direction
- type DirtyMark
- type DirtyScope
- type Kind
- type Snapshot
- type Store
- func (s *Store) Apply(d Delta)
- func (s *Store) Cells() int
- func (s *Store) CountD(label, rt uint32, dir Direction) int64
- func (s *Store) CountE(rt uint32) int64
- func (s *Store) CountT(a, rt, b uint32) int64
- func (s *Store) DDirty(label uint32, dir Direction) bool
- func (s *Store) MarkDirty(m DirtyMark)
- func (s *Store) MaxRecountEdges() int
- func (s *Store) RecomputeReset()
- func (s *Store) Snapshot() Snapshot
- func (s *Store) TDirty(a, b uint32) bool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Delta ¶
type Delta struct {
A uint32 // KindD: label; KindT: labelA; KindE: unused.
RT uint32 // relationship-type id.
B uint32 // KindT: labelB; otherwise unused.
Delta int64 // signed increment (+1 on create, -1 on remove).
Kind Kind // which family this delta targets.
Dir Direction // KindD only.
}
Delta is one buffered increment to a single count cell. It is a small value carried by copy; a transaction accumulates a slice of them in the engine's CountBuffer and applies them at commit via Store.Apply.
type Direction ¶
type Direction uint8
Direction selects which end of a relationship a [D] degree-sum counts.
type DirtyMark ¶
type DirtyMark struct {
Label uint32
Scope DirtyScope
}
DirtyMark records that a family becomes non-exact for one label id, buffered alongside deltas and applied at commit via Store.MarkDirty. See design §3.3.1: a relabel whose IN-side cannot be enumerated in O(delta) marks the minimal X-scoped IN cells dirty rather than writing a wrong exact.
type DirtyScope ¶
type DirtyScope uint8
DirtyScope selects which X-scoped exactness set a DirtyMark toggles off.
const ( // DirtyDOut marks D(label, *, OUT) untrustworthy for a label. DirtyDOut DirtyScope = iota // DirtyDIn marks D(label, *, IN) untrustworthy for a label. DirtyDIn // DirtyTA marks T(label, *, *) untrustworthy (the a-position). DirtyTA // DirtyTB marks T(*, *, label) untrustworthy (the b-position). DirtyTB )
type Snapshot ¶
type Snapshot struct {
E map[uint32]int64
DOut map[uint64]int64
DIn map[uint64]int64
T map[[3]uint32]int64
DirtyDOut []uint32
DirtyDIn []uint32
DirtyTA []uint32
DirtyTB []uint32
}
Snapshot is a point-in-time copy of every live cell and dirty marking, for observability and differential testing. The D keys are dkey(label, relType) = label<<32|relType; the T keys are [3]uint32{labelA, relType, labelB}. The dirty slices list the label ids currently marked non-exact in each family.
type Store ¶
type Store struct {
// contains filtered or unexported fields
}
Store is the sharded relationship count-store. Its zero value is not usable; construct one with New.
func New ¶
New returns an empty, ready-to-use Store whose per-relabel OUT-side recount ceiling is maxRecountEdges (design §3.3.1). A maxRecountEdges of 0 or less disables the ceiling (the OUT side is always recounted exactly).
func (*Store) Apply ¶
Apply applies one buffered delta to its cell. A key is created on first observation and deleted when its counter returns to zero (bounded growth). A zero delta is a no-op. Apply is a mutation and must be serialised by the caller's write barrier (see the package concurrency contract).
func (*Store) Cells ¶
Cells reports the number of distinct live count cells currently held — the sum over every shard of the E, D(out), D(in) and T map sizes. Because a cell is deleted the moment its counter returns to zero ([Store.add]), every map entry is a live combination, so this is an exact, allocation-free size indicator for observability: it is bounded by the number of currently-observed schema combinations (design §2.3), never by |V| or |E|. It is a read taken under the shard read locks and is safe to call concurrently with the barrier-serialised writers. The metrics [Backend] exposes no gauge, so this is the accessor an observer reads to surface the store's footprint (task #2087).
func (*Store) CountD ¶
CountD returns the degree-sum D(label, rt, dir) (0 when absent). It ignores the dirty flag; callers that need the exactness verdict consult Store.DDirty.
func (*Store) CountT ¶
CountT returns the triple count T(a, rt, b) (0 when absent). It ignores the dirty flag; callers that need the exactness verdict consult Store.TDirty.
func (*Store) MarkDirty ¶
MarkDirty toggles off the exactness of one X-scoped family set. It is a mutation and must be serialised by the caller's write barrier.
func (*Store) MaxRecountEdges ¶
MaxRecountEdges reports the per-relabel OUT-side recount ceiling (0 or less means unbounded). The relabel maintenance consults it to decide between an exact OUT-side recount and an X-scoped OUT dirty marking (design §3.3.1).
func (*Store) RecomputeReset ¶
func (s *Store) RecomputeReset()
RecomputeReset clears every cell and every dirty flag, returning the store to its empty state. It is the seam an O(V+E) recompute-from-graph (task #2084) resets before replaying the create-deltas of every live edge; clearing the dirty sets restores full exactness. It is a mutation and must be serialised by the caller's write barrier.
Source Files