COUNT_EXTEND_CHAIN and COUNT_ANTI_EDGE_CHAIN lack MVCC guards; wrong counts with deleted nodes/concurrent writes

[adsharma]

Summary

COUNT_EXTEND_CHAIN and COUNT_ANTI_EDGE_CHAIN can return wrong counts when node tables contain deleted rows or when concurrent writes are present. Unlike the CSR-gated count paths, these two rewrites have no epoch/invalidation guard and optimize even without ALTER TABLE .. SET SORTED BY .. CSR.

Verification

Optimizer gates (both only skip the writer transaction, not a reader racing a writer):

• src/optimizer/count_rel_table_optimizer.cpp, tryRewriteExtendChainCount() (~line 506) and tryRewriteAntiEdgeChainCount() (~line 98):

  if (transaction != nullptr && transaction->isWriteTransaction()) { return op; }

  A read-only transaction still takes the fast path while another transaction's writes commit around/after planning.

No CSR / epoch gate on the new paths:

• tryRewriteSortedOffsetCount() (~line 1406+) and the reachable-count rewrite (~line 1356+) both require nodeEntry->isCsr() and table->getChangeEpoch() == nodeEntry->getCsrChangeEpoch().
• tryRewriteExtendChainCount() only requires native storage (StorageFormat::NONE, no scan function, ~line 574) — no isCsr(), no changeEpoch check.
• tryRewriteAntiEdgeChainCount() does not even check native storage — only getScanFunction().has_value() — so it optimizes regular (non-CSR-declared) tables unconditionally.

Physical operators ignore node visibility:

• grep isVisible|isDeleted|getNumDeletions|hasVersionInfo src/processor/operator/scan/count_extend_chain.cpp src/processor/operator/scan/count_anti_edge_chain.cpp → no hits. Rel-edge deletions are filtered for free by RelTable::scan(transaction, ...), but node deletions are not:
  • count_extend_chain.cpp::getNextTuplesInternal(): counts[0] is initialized to 1 for every offset in the node-group grid, including deleted/invisible source nodes. The correct semantic (scan → extend chain) seeds counts only from visible nodes produced by SCAN_NODE_TABLE.
  • Same file: per-hop propagation never calls NodeTable::isVisible() on bound or nbr nodes; edges scanned from a deleted bound node still contribute, whereas the unoptimized plan would never emit that bound node.
  • count_anti_edge_chain.cpp: computeSuffixCounts() accumulates Bk[v] += Bk1[w] for every scanned edge without checking visibility of v/w; steps 3–5 (T/S/A loops over 0..offsetUpper) likewise never check mid-node visibility. A deleted n1 still contributes degN0 * D[nbr] to T.
• getOffsetUpperBound() in both operators reads the latest global getNumNodeGroups() / getNumTuplesInNodeGroup(), not the reader snapshot. A concurrent commit that appends a node group changes the iteration range mid-scan (snapshot violation / missed or phantom nodes). NodeTable::isVisible() already returns false for out-of-snapshot offsets, but the operators never call it.

For comparison, CountRelTable::getNextTuplesInternal() (src/processor/operator/scan/count_rel_table.cpp) is MVCC-aware: getNumTotalRows(transaction), getNumDeletions(transaction, ...), and local-storage handling only for writer transactions.

Suggested fix

Pick one (or stage them):

1. Make the operators snapshot-correct (preferred): in both operators, filter every bound/nbr offset through NodeTable::isVisible(transaction, offset) (source seeding, suffix propagation, and T/S/A loops), and clip getOffsetUpperBound() to the snapshot (treat beyond-snapshot offsets as invisible rather than iterating the latest grid size). Rel-edge visibility can stay on RelTable::scan.
2. Conservative guard until (1) lands: capture each involved node/rel table's getChangeEpoch() in LogicalCountExtendChain / LogicalCountAntiEdgeChain at rewrite time and bail out (don't rewrite) when any table has ever been mutated, or re-validate the epoch at execution and fall back to the unoptimized plan. This mirrors the changeEpoch != csrChangeEpoch invalidation used by the CSR paths.
3. Also add the missing native-storage gate to the anti-edge path (parity with the extend-chain path's StorageFormat::NONE checks) so Arrow/icebug-disk tables can't take the CSR-grid arithmetic.

Suggested tests

• Chain count after DELETE of a source/mid/dst node (each position) vs. unoptimized plan (EXPLAIN / optimizer-disabled session).
• Chain count with deleted rels (already covered by scan, but lock it in).
• Read txn running the chain count concurrently with a committing writer (node insert + rel insert) — expect snapshot-consistent count.
• Writer-txn chain count already falls back (existing isWriteTransaction guard) — keep that test.
• Non-CSR table chain count correctness with a populated + partially deleted graph (the no-SET SORTED BY CSR case above).

Files

• src/optimizer/count_rel_table_optimizer.cpp (tryRewriteExtendChainCount, tryRewriteAntiEdgeChainCount)
• src/processor/operator/scan/count_extend_chain.cpp
• src/processor/operator/scan/count_anti_edge_chain.cpp
• src/include/processor/operator/scan/count_extend_chain.h / count_anti_edge_chain.h
• Reference (correct) patterns: src/processor/operator/scan/count_rel_table.cpp; CSR epoch gate at count_rel_table_optimizer.cpp:1363,1367,1409,1415

[itz-puneet]

I'd like to pick up item 3 (the missing native-storage gate on the anti-edge path). Per CONTRIBUTING I'm checking here before opening a PR, and I have a question about where the test belongs.

What I confirmed:

• tryRewriteExtendChainCount gates on getStorage().empty() && getStorageFormat() == StorageFormat::NONE for both rel groups and node tables (count_rel_table_optimizer.cpp:598 and :607). tryRewriteAntiEdgeChainCount checks only getScanFunction().has_value() at :237 and :408, and never checks the node entry.
• The path is reachable rather than theoretical. bind_ddl.cpp:437 rejects mixing formats but explicitly allows an all-icebug-disk graph, and dataset/demo-db/icebug-disk/schema.cypher is exactly that shape — user nodes plus follows(FROM user TO user) — which is the self-referencing pattern the anti-edge rewrite matches. Without the gate that graph takes the CSR-grid arithmetic against tables that have neither the node-group grid nor a native CSR.

The patch is small: hoist the two isNative*Entry lambdas out of tryRewriteExtendChainCount into file-scope helpers and apply them in the anti-edge path to the anti rel group, the prefix-chain rel groups, and the node entry (n0/n1/n2 all bind midTableID, so one check covers all three). It only narrows when the rewrite fires, so the fallback is the regular plan. Branch: https://github.com/itz-puneet/ladybug/tree/anti-edge-native-storage-gate

My question is the test. CONTRIBUTING asks for one, and I can't find a good fit:

• The .test format has no plan assertion and no optimizer-disable knob, so I can't assert "this query no longer takes the rewrite" there.
• optimizer_test.cpp has hasOperatorType, which is exactly right, but OptimizerTest::getInputDir() is wired to the tinysnb CSV dataset, and I don't see an existing pattern for a gtest fixture over an icebug-disk dataset.
• A result-correctness test against the icebug-disk demo dataset is easy to write, but I can't confirm the query actually triggers the rewrite, so it could pass identically before and after and prove nothing.

Would you prefer a gtest case with an icebug-disk fixture asserting COUNT_ANTI_EDGE_CHAIN is absent from the plan, and if so is there an existing fixture I've missed? Happy to add whichever you'd rather see before opening the PR.

Separately, items 1 and 2 (node visibility in the operators, and the snapshot clipping in getOffsetUpperBound) look considerably larger, and I've left them alone — let me know if you'd rather they were staged together.

[adsharma]

ok with focusing on native here. We can verify icebug-disk manually for now.

[itz-puneet]

Thanks — opened #943 with just the native gate then. Left items 1 and 2 out, so this issue stays open for them.