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, and it no longer rests on any exclusion the engine provides. This contract used to say that all MUTATIONS were serialised by the engine's write barrier (visMu.Lock in commitUnderBarrier) and that all READS ran under a read barrier (visMu.RLock in Graph.View). BOTH HALVES ARE FALSE, and have been since sprint 334 made MVCC the module's concurrency control: commitUnderBarrier now runs inside a SHARED hold, so two writers mutate this store concurrently, and an ordinary query read takes no barrier at all — Graph.View survives only for DDL-adjacent scans.
What makes it safe is therefore the structure itself, not exclusion:
- the per-shard sync.RWMutex serialises the insert-add-delete-on-zero sequence in [Store.add], which is the only sequence that is not a single atomic operation. It is genuinely contended now rather than defence-in-depth;
- the atomic cells make an individual counter read lock-free regardless;
- the aggregate is ORDER-INSENSITIVE (rmp #2303): a cell is deleted at exactly zero rather than at zero-or-below, so concurrent partial sums that transit a negative value do not lose a decrement. That property is what replaced writer exclusion, and [Store.add] documents the failure it fixes.
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.
It needs NO serialisation from the caller (rmp #2345). Every cell it touches goes through [Store.add], whose aggregate is ORDER-INSENSITIVE — a cell is deleted at exactly zero and a negative cell is retained, so addition commutes — and each touch is made under that cell's own per-shard lock. Two writers applying concurrently therefore reach the same totals in any interleaving. The package contract states this at the top; it is restated here because this doc used to require the engine's write barrier, which has not serialised writers since rmp #2320.
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 writers, which are NOT serialised against each other. 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. It needs no caller serialisation, for the order-insensitivity reason given on Store.Apply.
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 needs no caller serialisation for the order-insensitivity reason given on Store.Apply.
Source Files