Build GRAPH.BULK topology from relation-partitioned coordinates and derive transposes once

perfloop/falkordb · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_fptwt283gw

Verdict

VERIFIED · settled 2026-08-03 · pull request opened as FalkorDB/FalkorDB#2299

What happened: The paired measurements met the required improvement.

Hypothesis

The source shows an algorithmic mismatch between GRAPH.BULK and its storage commit: Graph_BulkInsert passes declared counts to BulkInsert, which already pre-accommodates edge capacity, but _BulkInsert_ProcessEdgeFile still materializes Edge and AttributeSet arrays, makes an Edge* array, and calls GraphHub_CreateEdges; Graph_CreateEdges then copies that pointer array, allocates and assigns one DataBlock item and one adjacency Delta_Matrix element per edge, sorts the copy, and only then gives it to Tensor_SetEdges. The source marks both batch allocation and a GrB_Matrix_build-style adjacency update as TODOs, while Delta_Matrix mutation also maintains a transpose, so this is not just one removable allocation: every bulk edge is currently driven through a mutation-oriented representation before the relationship tensor can exploit its required endpoint grouping. A command-scoped coordinate builder changes the whole entry-to-leaf contract so the unavoidable floor is decoding and retaining each edge's attribute/ID plus materializing each distinct endpoint pair or multiedge group, rather than repeated pointer staging and per-edge forward-and-transpose matrix mutation; arrival-order ID assignment, duplicate pairs, existing-graph appends, and conditional edge indexes must remain explicit correctness boundaries. A later case should falsify this with an end-to-end GRAPH.BULK latency/CPU and allocation profile that holds payload size fixed while sweeping batch size, relation-file count, and duplicate-pair rate, compares Graph_CreateEdges matrix-call counts and peak memory, and verifies IDs, multiedges, indexed edges, and append batches; if the bulk builder does not lower the attributed commit cost without an unacceptable memory or first-read penalty, it should be rejected.

Change to test: Turn the declared-count GRAPH.BULK edge phase into a BulkEdgeBuild transaction: Graph_BulkInsert/BulkInsert allocates one bounded, relation-partitioned record buffer, edge-file parsing appends (relation, src, dst, attribute, arrival-order) records instead of Edge** batches, and the commit path batch-reserves DataBlock slots in arrival order, groups coordinates by relation and endpoint pair, bulk-builds the forward adjacency and relation Delta_Matrix state, and derives/installs the transpose once per built matrix. Merge grouped entries into existing matrix state for append batches, explicitly constructing tensor vectors for multiedge groups; then let GraphHub run only the required index side effects, preserving the existing log=false bulk behavior.

Where it lives

perfloop/falkordb · src/graph/graph_hub.c

Evidence

GRAPH.BULK fresh: 1000000 edges, 4 relation files, duplicate group size 1 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
wall_ns 4100849810 3794644954 −7.9% (−322600758) −363254571 to −146250097 < 0 PASSED
server_cpu_ns 3845000000 3645000000 −5.9% (−225000000) −250000000 to −80000000 < 0 PASSED
server_peak_rss_bytes 461846528 441176064 −4.5% (−20654080) −22622208 to −19243008 ≤ 8388608 PASSED

GRAPH.BULK fresh: 200000 edges, 1 relation file, duplicate group size 1 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
wall_ns 825924950 761295323 −8% (−66114644) −78663240 to −55673420 ≤ 50000000 PASSED
server_cpu_ns 770000000 730000000 −6.5% (−50000000) −70000000 to −30000000 ≤ 50000000 PASSED
server_peak_rss_bytes 216360960 209242112 −3.6% (−7755776) −9740288 to −4485120 ≤ 8388608 PASSED

GRAPH.BULK fresh: 200000 edges, 4 relation files, duplicate group size 8 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
wall_ns 786706096 758039299 −4.7% (−37168538) −55195860 to −10003554 ≤ 50000000 PASSED
server_cpu_ns 740000000 710000000 −4.7% (−35000000) −40000000 to −20000000 ≤ 50000000 PASSED
server_peak_rss_bytes 215803904 210464768 −2.3% (−4968448) −7852032 to −3829760 ≤ 8388608 PASSED

GRAPH.BULK append: populate 200000 then append 200000 edges, 4 relation files, duplicate group size 1 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
wall_ns 811382753 782436485 −3.8% (−31014773) −60830003 to −15694842 ≤ 50000000 PASSED
server_cpu_ns 760000000 740000000 −3.9% (−30000000) −50000000 to −10000000 ≤ 50000000 PASSED
server_peak_rss_bytes 272869376 267243520 −1.9% (−5087232) −6217728 to −4042752 ≤ 8388608 PASSED

Checks: 2 of 2 passed. Verification: no defect found.

Timeline