Skip to content

perf(schema): index (name, path) so relationship writes seek, not scan - #1653

Merged
Shashankss1205 merged 1 commit into
CodeGraphContext:mainfrom
mollyjester:perf/cgc-schema-name-path-indexes
Aug 26, 2026
Merged

Shashankss1205 merged 1 commit into
CodeGraphContext:mainfrom
mollyjester:perf/cgc-schema-name-path-indexes

Conversation

@mollyjester

Copy link
Copy Markdown
Contributor

#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.

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 INDEXES on the graph measured above, after this change:

name type properties owningConstraint
function_identity RANGE name, path, line_number, occurrence_index function_identity
function_name_path RANGE name, path null

DROP INDEX function_name_path leaves function_identity and the other
ten 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, five
items, no live database required (it reuses the fake recording-session
pattern already used by test_falkordb_schema_and_watcher_fixes.py and
test_graph_layer_robustness.py):

  1. Neo4j emits exactly one (name, path) index per label in
    POSITIONAL_IDENTITY_LABELS — the test iterates the map, so it tracks
    the label list rather than duplicating it.
  2. falkordb and falkordb-remote emit none (parametrized).
  3. Every statement carries IF NOT EXISTS, and a second
    create_graph_schema call emits an identical list without raising.
  4. No _name_path statement mentions line_number or
    occurrence_index, while each *_identity constraint does. This is
    the 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 change
is guarded. ./tests/run_tests.sh fast gives the same failure set as
the base commit — 3 failed, all pre-existing — with 1473 passed here vs
1468 on the base, the +5 being these tests.

Because _DDLRunner swallows per-statement DDL failures, CI would only
warn, 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 dc7f33da without this change, so
red marks here are not necessarily mine:

  • build (3.12), build (3.13), build (3.14) — test.yml runs
    ./tests/run_tests.sh fast, which exits non-zero on the base because of
    three pre-existing failures: test_all_canonical_cli_commands_run_with_kuzudb,
    test_parser_goldens[sample_project_kotlin], and
    test_tree_sitter_language_pack_matches_pyproject_pin. Locally this branch
    reproduces exactly that set, with 1473 passed vs 1468 on the base.
  • db-parity — REL_CALLS differs on ladybugdb. Red on dc7f33da and
    on the commits preceding it.
  • test (windows-latest) — the e2e job cannot load the ladybugdb native
    library on the Windows runner, so indexing exits before any relationship pass
    runs.

lint.yml cannot be affected: it runs ruff against an explicit six-file list
that does not include schema.py.

Not in this PR

  • EnumMember, Object, Mixin and Extension have no index at all on
    Neo4j; their CREATE INDEX statements exist only in the is_falkordb
    branch. MATCH (m:EnumMember {name: ..., path: ...}) in the writer is
    therefore an unavoidable label scan.
  • Related but independent: perf(inherits): group INHERITS writes by the label pairs that occur #1652 also touches the INHERITS write path.
    It changes writer.py / inheritance.py and this changes only
    schema.py, so the two do not overlap and either can land first.

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]>
@vercel

vercel Bot commented Aug 19, 2026

Copy link
Copy Markdown

@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.

@mollyjester

Copy link
Copy Markdown
Contributor Author

A note on the INHERITS row, since #1652 merged while this was being measured:
those two figures were taken on dc7f33da, i.e. before #1652, so both columns
reflect the old 12x12 label-pair fan-out in write_inheritance_links.

The 485x ratio is still attributable to the schema alone — both sides ran the
identical writer against the identical store, with only the eleven indexes
dropped and recreated between runs, and both produced the same 20,963 edges with
the same per-(child_label, parent_label) breakdown. But the absolute
wall-times will be materially lower on current main, because #1652 cut the
number of batch passes. Anyone re-running that pass today should expect smaller
figures on both sides.

The CALLS numbers, the write-side figure and the PROFILE comparison are
unaffected — #1652 touched neither of those paths.

@Shashankss1205 Shashankss1205 left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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!

@Shashankss1205
Shashankss1205 merged commit 7e55246 into CodeGraphContext:main Aug 26, 2026
15 of 21 checks passed
@github-project-automation github-project-automation Bot moved this from Backlog tasks to Done in CGC Progress Board Aug 26, 2026
@Shashankss1205 Shashankss1205 added gssoc:approved GSSoC validation: counts toward scoring level:advanced GSSoC difficulty: 55 pts contributor / 30 mentor mentor:Shashankss1205 GSSoC mentor attribution: credits reviewing mentor quality:exceptional GSSoC quality: x1.5 contributor / +10 mentor type:feature GSSoC type bonus: feature labels Aug 26, 2026
@mollyjester
mollyjester deleted the perf/cgc-schema-name-path-indexes branch August 26, 2026 13:23
Shashankss1205 added a commit that referenced this pull request Aug 26, 2026
…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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

gssoc:approved GSSoC validation: counts toward scoring level:advanced GSSoC difficulty: 55 pts contributor / 30 mentor mentor:Shashankss1205 GSSoC mentor attribution: credits reviewing mentor quality:exceptional GSSoC quality: x1.5 contributor / +10 mentor type:feature GSSoC type bonus: feature

Projects

Status: Done

Development

Successfully merging this pull request may close these issues.

2 participants