count

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.

Within a shard each family's cell map is IMMUTABLE ONCE PUBLISHED and swapped as a whole through an atomic.Pointer (copy-on-write). Only the map's STRUCTURE — which combinations exist — is versioned that way; a cell's VALUE lives behind the pointer the map holds and changes in place, so the ordinary increment never rebuilds a map. See [addCell] for why that split is what makes the store scale.

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:

• Store.CountE, Store.CountD and Store.CountT take NO LOCK AT ALL. They load the shard's published cell map through an atomic.Pointer and read the cell. The map they observe is immutable, so a concurrent structural change cannot mutate it under them;
• an increment to an ALREADY-PRESENT cell runs under the shard's SHARED hold and is a single atomic.Int64.Add. The shared hold is not protecting the arithmetic — the arithmetic is already atomic. It is what stops a cell being unlinked out from under an in-flight increment, which would silently discard the delta. Since rmp #2696 that hold is taken on an [rbMutex], whose shared side is striped per-P, rather than on a sync.RWMutex whose shared side was one contended word;
• creating a cell, and deleting one that has returned to zero, take the shard's EXCLUSIVE lock. Those are the only two operations that change a map's structure, and their frequency is schema-cardinality-bounded rather than data-size-bounded;
• 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 [addCell] documents the failure it fixes.

The store spawns no goroutines.

Why the WRITE path's shared hold is striped (rmp #2696) ¶

rmp #2682 removed the read lock and fixed the SPREAD case. It did not fix the single-hot-type case, which was unchanged at 0.319x from 1 to 8 goroutines, and the reason is that the remaining cost was never the counter.

MEASURED at HEAD 42a27558, one hot relationship type at 8 goroutines: sync/atomic.(*Int32).Add was 48.85% of ALL CPU, and pprof -peek attributes 100% of it to sync.RWMutex.RLock (53.17%) and sync.RWMutex.RUnlock (46.83%). The count cell those calls exist to protect — an atomic.Int64 — was 12.60%. The lock word was the contended object; the counter was not.

That distinction decided the design, and it was settled by measurement rather than by argument. Two candidates were built and benchmarked against the same 90%-read/10%-write shape:

• a STRIPED COUNTER summed on read, in the shape of Java's LongAdder: each cell becomes eight per-line counters, a write picks one, a read sums them. It bought 1.227x, made an uncontended read 1.92x SLOWER (5.198ns against 2.702ns) and an uncontended write 3.4x slower, because the delete-on-zero test must sum every stripe on every increment. It loses, and it loses because it unshares the object that was not shared enough to matter;
• a STRIPED LOCK with the counter left alone — the shape adopted here. It bought 2.018x on the same benchmark and left the read path exactly as it was, O(1) and exact, at 0.994x.

The generalisable lesson is that on this store the FREQUENT hold is the shared one and the RARE hold is the exclusive one, so the object worth striping is the LOCK. ClickHouse draws the same line explicitly between its two counter families: ProfileEvents is striped per-CPU and summed on read, while CurrentMetrics is a single unstriped atomic precisely because it must be exactly readable at a point in time (src/Common/CurrentMetrics.h). This store is the second kind — the planner reads an exact cardinality, and delete-on-zero needs an exact zero — so striping its counter was the wrong transplant.

The lock-free increment that does not work ¶

Recorded because it is the obvious next idea and it is WRONG. Replacing the shared hold with a dead-flag handshake — the writer adds and then checks a flag, the unlinker sets the flag and then re-reads the counter — appears sound and is not. After a SUCCESSFUL unlink the flag stays set, so a writer whose delta was already counted into the zero that justified the unlink also observes it, undoes its delta and re-applies it to the replacement cell. The delta lands twice and the aggregate drifts. MEASURED: with the unlink ablated the same increment is exact over 8x50000 oscillations through zero, and with the unlink restored the same test read 13 against an expected 24. Safe reclamation of a cell that lock-free writers may still hold a pointer to needs epochs or hazard pointers, which is a far larger change than this store's contention warrants.

Why the read path holds no lock (rmp #2682) ¶

It used to take the shard's read lock, and that single sync.RWMutex reader counter was measured to be the whole of the store's contention: with one hot relationship type — every cell of which lands on one shard, because [Store.eShardOf] keys on the relationship type alone — throughput FELL to 0.391x going from 1 to 8 goroutines on a 10-core host, and 98.15% of the module's mutex delay sat on this package's increment.

That is the same failure rmp #2203 measured elsewhere in this module: a bare sync.RWMutex degrading 17.6x from 1 to 10 cores purely because of its one shared reader counter, the counter and not the code around it being the bottleneck. A reader-side RLock is two atomic read-modify-writes on ONE cache line shared by every core, so it serialises at the cache-coherence level however little work the critical section does. Copy-on-write removes the read-side read-modify-write entirely: a reader performs a plain atomic LOAD, which leaves the line in shared state on every core at once.