Repository navigation
perf(schema): index (name, path) so relationship writes seek, not scan - #1653
Conversation
CodeGraphContext#1393 gave the eleven positional-identity labels a four-property identity -- (name, path, line_number, occurrence_index) -- and that UNIQUE constraint's backing index is the only composite index they have. The relationship passes and code_finder do not look nodes up that way. 1. Neo4j uses a composite index only when every indexed property has a predicate. The identity constraint's backing index therefore cannot serve a lookup that predicates on (name, path) alone, and the planner falls back to NodeByLabelScan + Filter -- once per row. 2. Those two-property lookups are the norm, not the exception. write_inheritance_links matches `(child:<Label> {name: row.child_name, path: row.path})`, and the same for the parent, for every label pair it enumerates. write_function_call_groups matches the callee by (name, path) in both the batched and the single-row path -- only the caller carries line_number. code_finder's who_calls_function, what_does_function_call, find_class_hierarchy, find_all_callers and find_all_callees do the same. On a 159,041-Function graph every such row scans the whole label. 3. The fix is one plain two-property index per label, created by looping the same POSITIONAL_IDENTITY_LABELS map the identity constraints already use. Both writers template the label, so indexing only Function and Class would leave Struct, Interface, Trait, Macro, Enum, Union, Record and Property scanning exactly as before on C++/Rust/Go/Kotlin repositories. 4. They cannot collide with the identity constraints: a constraint's backing index covers (name, path, line_number, occurrence_index), a different property set, so the two coexist. Verified on Neo4j 5.26.27 -- SHOW INDEXES lists function_name_path (owningConstraint null) beside function_identity (owningConstraint function_identity), and dropping the former leaves all eleven identity constraints intact. IF NOT EXISTS makes re-runs no-ops: calling create_graph_schema twice leaves SHOW INDEXES and SHOW CONSTRAINTS identical. FalkorDB is excluded -- the loop sits inside the existing `if not is_falkordb:` block. FalkorDB indexes per attribute rather than per property tuple, and the composite CREATE INDEX statements in its own branch already cover name and path. Kuzu manages its own storage and already receives -- and swallows, via _DDLRunner -- every CREATE CONSTRAINT in this block; these statements join that set. Measured on Neo4j 5.26.27 community, a 27,530-file Odoo checkout (Python/JavaScript/XML) indexed to 750,083 nodes: 342,430 Variable, 182,242 Parameter, 159,041 Function, 21,132 Class. One instance, 3G page cache, 1G heap; the store is 1.2G, so it is fully resident in page cache on both sides and the difference is planner work rather than disk I/O. Read side, measured on ONE store -- with the eleven indexes, then again after DROPping them, Neo4j restarted between runs so each starts from a cold page cache: without with CALLS, 20 x 1000-row batches 3397.0 s 7.8 s 438x median per batch 172.5 s 0.216 s INHERITS, full pass 6259.9 s 12.9 s 485x PROFILE of the callee lookup, the same 100 (name, path) rows against the same store: without: NodeByLabelScan(Function) + Filter 31,809,230 db hits with: NodeIndexSeek(function_name_path) 1,030 db hits Write side, measured separately -- two stores built from the same parsed input, one with upstream's schema and one with this change, timed over the same first 12,500 files: 1798.0 s -> 450.9 s. The CALLS figure is per 20 batches, not a whole-pass total: fn_to_fn resolves to 763,007 rows on this corpus, and the unindexed pass does not finish in a working day. The scan cost is a function of how many nodes carry the label, which is identical on both sides, so a fixed row slice measures the real per-row cost at full scale. Output is identical. The same store produced the same 8,713 CALLS and 3,362 HEURISTIC_CALLS edges over the measured slice with and without the indexes, and the same 20,963 INHERITS edges with an identical per-(child_label, parent_label) breakdown. Adding an index cannot change results, only plans -- and because both sides here are literally the same database, node identity is unchanged too. The 21-project parser golden suite is untouched, as it must be for a DDL-only change. Not in this PR, but found while auditing the lookup sites: on Neo4j, EnumMember, Object, Mixin and Extension have no index at all -- their CREATE INDEX statements exist only in the is_falkordb branch -- so `MATCH (m:EnumMember {name: ..., path: ...})` in the writer is an unavoidable label scan. Confirmed by SHOW INDEXES on the graph above. Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
|
@mollyjester is attempting to deploy a commit to the shashankss1205's projects Team on Vercel. A member of the Team first needs to authorize it. |
|
A note on the INHERITS row, since #1652 merged while this was being measured: The 485x ratio is still attributable to the schema alone — both sides ran the The CALLS numbers, the write-side figure and the |
Shashankss1205
left a comment
There was a problem hiding this comment.
Verified on a local trial-merge against current main (0.6.5): the 5 new schema tests + schema contract pass, full unit suite 1411 passed / 7 skipped, and a golden spot-check confirms the DDL-only claim. The analysis is exactly right — the #1393 identity constraint's backing index can't serve (name, path) predicates on Neo4j, and every relationship pass looks nodes up that way. The coexistence table, the FalkorDB exclusion rationale, and the fixed-slice methodology for the unfinishable unindexed pass are all appreciated. The EnumMember/Object/Mixin/Extension no-index-at-all finding at the bottom is a good catch — worth a small follow-up on the same pattern if you're inclined.
Together with #1652 this closes out both halves of the write-path cost you identified in #1605's qualification note. Thanks @mollyjester!
…by class/global vars and values; Neo4j indexes for the falkordb-only labels (#1671) - kotlin/php: annotated/attributed declarations reported the annotation line as line_number (the declaration node starts at its annotation). Both now report the declaration proper — and their _get_parent_context walkers were aligned to the same line, since Hilt/Previews resolution and the writer join context line against the function's line_number. - ruby: @@class_variables and $globals were never captured (missing node types in the query); variable `value` was ALWAYS None because captures bucketed by id() of tree-sitter's per-access wrapper objects (n1 == n2 while id(n1) != id(n2)) — bucketing by node span fixes it; and the type ladder tested startswith("@") before "@@", leaving the class branch dead. - schema: EnumMember/Object/Mixin/Extension/Parameter had index statements only in the is_falkordb branch, so Neo4j lookups on them were label scans (#1653's closing observation). They now get (name, path) indexes on the same pattern. Kotlin/PHP goldens regenerated (property-level line shifts only — zero node/edge count drift). Unit suite 1418 passed / 7 skipped; all 21 goldens green.
#1393 gave the eleven positional-identity labels a four-property
identity -- (name, path, line_number, occurrence_index) -- and that
UNIQUE constraint's backing index is the only composite index they
have. The relationship passes and code_finder do not look nodes up
that way.
Neo4j uses a composite index only when every indexed property has a
predicate. The identity constraint's backing index therefore cannot
serve a lookup that predicates on (name, path) alone, and the
planner falls back to NodeByLabelScan + Filter -- once per row.
Those two-property lookups are the norm, not the exception.
write_inheritance_links matches
(child:<Label> {name: row.child_name, path: row.path}), and thesame for the parent, for every label pair it enumerates.
write_function_call_groups matches the callee by (name, path) in
both the batched and the single-row path -- only the caller carries
line_number. code_finder's who_calls_function,
what_does_function_call, find_class_hierarchy, find_all_callers and
find_all_callees do the same. On a 159,041-Function graph every
such row scans the whole label.
The fix is one plain two-property index per label, created by
looping the same POSITIONAL_IDENTITY_LABELS map the identity
constraints already use. Both writers template the label, so
indexing only Function and Class would leave Struct, Interface,
Trait, Macro, Enum, Union, Record and Property scanning exactly as
before on C++/Rust/Go/Kotlin repositories.
They cannot collide with the identity constraints: a constraint's
backing index covers (name, path, line_number, occurrence_index),
a different property set, so the two coexist. Verified on Neo4j
5.26.27 -- SHOW INDEXES lists function_name_path (owningConstraint
null) beside function_identity (owningConstraint
function_identity), and dropping the former leaves all eleven
identity constraints intact. IF NOT EXISTS makes re-runs no-ops:
calling create_graph_schema twice leaves SHOW INDEXES and SHOW
CONSTRAINTS identical.
FalkorDB is excluded -- the loop sits inside the existing
if not is_falkordb:block. FalkorDB indexes per attribute ratherthan per property tuple, and the composite CREATE INDEX statements in
its own branch already cover name and path. Kuzu manages its own
storage and already receives -- and swallows, via _DDLRunner -- every
CREATE CONSTRAINT in this block; these statements join that set.
Measured on Neo4j 5.26.27 community, a 27,530-file Odoo checkout
(Python/JavaScript/XML) indexed to 750,083 nodes: 342,430 Variable,
182,242 Parameter, 159,041 Function, 21,132 Class. One instance, 3G
page cache, 1G heap; the store is 1.2G, so it is fully resident in
page cache on both sides and the difference is planner work rather
than disk I/O.
Read side, measured on ONE store -- with the eleven indexes, then
again after DROPping them, Neo4j restarted between runs so each
starts from a cold page cache:
PROFILE of the callee lookup, the same 100 (name, path) rows against
the same store:
Write side, measured separately -- two stores built from the same
parsed input, one with upstream's schema and one with this change,
timed over the same first 12,500 files: 1798.0 s -> 450.9 s.
The CALLS figure is per 20 batches, not a whole-pass total: fn_to_fn
resolves to 763,007 rows on this corpus, and the unindexed pass does
not finish in a working day. The scan cost is a function of how many
nodes carry the label, which is identical on both sides, so a fixed
row slice measures the real per-row cost at full scale.
Output is identical. The same store produced the same 8,713 CALLS and
3,362 HEURISTIC_CALLS edges over the measured slice with and without
the indexes, and the same 20,963 INHERITS edges with an identical
per-(child_label, parent_label) breakdown. Adding an index cannot
change results, only plans -- and because both sides here are
literally the same database, node identity is unchanged too. The
21-project parser golden suite is untouched, as it must be for a
DDL-only change.
Not in this PR, but found while auditing the lookup sites: on Neo4j,
EnumMember, Object, Mixin and Extension have no index at all -- their
CREATE INDEX statements exist only in the is_falkordb branch -- so
MATCH (m:EnumMember {name: ..., path: ...})in the writer is anunavoidable label scan. Confirmed by SHOW INDEXES on the graph above.
Index / constraint coexistence
The first thing this change invites is "won't that collide with the
identity constraint?" It does not — the property sets differ. Taken from
SHOW INDEXESon the graph measured above, after this change:function_identityfunction_identityfunction_name_pathDROP INDEX function_name_pathleavesfunction_identityand the otherten identity constraints untouched, which is how the read-side A/B above
was run on a single store.
Tests added
tests/unit/tools/test_schema_name_path_indexes.py— four tests, fiveitems, no live database required (it reuses the fake recording-session
pattern already used by
test_falkordb_schema_and_watcher_fixes.pyandtest_graph_layer_robustness.py):(name, path)index per label inPOSITIONAL_IDENTITY_LABELS— the test iterates the map, so it tracksthe label list rather than duplicating it.
falkordbandfalkordb-remoteemit none (parametrized).IF NOT EXISTS, and a secondcreate_graph_schemacall emits an identical list without raising._name_pathstatement mentionsline_numberoroccurrence_index, while each*_identityconstraint does. This isthe test that encodes why the fix works: it fails if the index is
ever "tidied" to match the constraint, which would silently restore
the label scans.
Test 1 fails on
main(assert 0 == 1) and passes here, so the changeis guarded.
./tests/run_tests.sh fastgives the same failure set asthe base commit — 3 failed, all pre-existing — with 1473 passed here vs
1468 on the base, the +5 being these tests.
Because
_DDLRunnerswallows per-statement DDL failures, CI would onlywarn, never fail, if this DDL were invalid on a real server — so the
DDL was exercised against a real Neo4j 5.26.27 locally (the graph above)
rather than trusted to the unit test.
CI
Five checks already fail on the base commit
dc7f33dawithout this change, sored marks here are not necessarily mine:
build (3.12),build (3.13),build (3.14)—test.ymlruns./tests/run_tests.sh fast, which exits non-zero on the base because ofthree pre-existing failures:
test_all_canonical_cli_commands_run_with_kuzudb,test_parser_goldens[sample_project_kotlin], andtest_tree_sitter_language_pack_matches_pyproject_pin. Locally this branchreproduces exactly that set, with 1473 passed vs 1468 on the base.
db-parity—REL_CALLSdiffers onladybugdb. Red ondc7f33daandon the commits preceding it.
test (windows-latest)— the e2e job cannot load theladybugdbnativelibrary on the Windows runner, so indexing exits before any relationship pass
runs.
lint.ymlcannot be affected: it runsruffagainst an explicit six-file listthat does not include
schema.py.Not in this PR
EnumMember,Object,MixinandExtensionhave no index at all onNeo4j; their
CREATE INDEXstatements exist only in theis_falkordbbranch.
MATCH (m:EnumMember {name: ..., path: ...})in the writer istherefore an unavoidable label scan.
It changes
writer.py/inheritance.pyand this changes onlyschema.py, so the two do not overlap and either can land first.