Skip to content

perf(inherits): group INHERITS writes by the label pairs that occur - #1652

Merged
Shashankss1205 merged 1 commit into
CodeGraphContext:mainfrom
mollyjester:perf/cgc-inherits-label-pair-grouping
Aug 19, 2026
Merged

Shashankss1205 merged 1 commit into
CodeGraphContext:mainfrom
mollyjester:perf/cgc-inherits-label-pair-grouping

Conversation

@mollyjester

@mollyjester mollyjester commented Aug 19, 2026 •

Copy link
Copy Markdown
Contributor

write_inheritance_links iterates a 12x12 (child_label, parent_label)
grid and passes the FULL resolved batch to every surviving pair. #1617
made the grid sparse by probing each label table once and skipping pairs
whose table is empty -- but every pair that survives the probe still
receives the whole batch, and the number of survivors is a property of
the repo's label inventory, not of the edges being written.

  1. Resolution now attaches the exact child/parent node label to each
    row. build_inheritance_and_csharp_files builds a path -> {name ->
    set(labels)} index over the 12 inheritance-eligible construct kinds
    and pins a row's child_label / parent_label only when that (path,
    name) maps to exactly one kind. The writer then runs one query per
    (child_label, parent_label) pair that actually occurs.

  2. Rows whose (path, name) is ambiguous carry no label and fall back to
    the original enumeration. This is not hypothetical: as
    write_binds_links' docstring already records, Kotlin does not qualify
    name by enclosing scope, so a top-level interface and an unrelated
    nested class can legitimately share name+path. perf(kuzu): skip empty label pairs in write_inheritance_links (-80% queries) #1617's
    populated_labels set is retained and applied to exactly those
    fallback paths. It is deliberately NOT applied to the grouped pairs:
    those pairs come from the rows themselves, so they are never empty,
    and probing them would be pure overhead while a stale or
    lazily-created label table would let the probe silently drop a real
    INHERITS edge.

  3. batch_size = 500 was declared and never used; the batch is now
    chunked. This is a separate robustness fix -- it keeps a five-figure
    UNWIND payload out of a single driver round-trip -- and it is not
    what produces the numbers below. On a repo with few populated labels
    it slightly raises the raw query count while cutting total work.

Relationship to #1617: complementary, not overlapping. #1617's saving is
a function of how many of the 12 label tables are empty; this change's
saving is a function of how many (child, parent) pairs the data actually
contains. On a repo where all 12 tables are non-empty, #1617 removes no
pairs at all and the full fan-out survives.

Measured, Neo4j, the pass in isolation on a 27,530-file
Python/JavaScript repo (756k nodes, 20,719 resolved rows), same store
and page cache on both sides, INHERITS deleted between runs so each
starts identical:

metric upstream/main this change
resolution 1.05 s 1.77 s (we cost +0.72 s)
write_inheritance_links 7,433.5 s 620.4 s 12.0× faster
batch-rows processed 207,340 21,487 9.7× fewer
queries 32 80 0.4× — more, see below

Query count goes UP because batch_size chunking splits the one large
pair into ~21 round-trips; the work per round-trip is what falls.
Upstream's 32 queries are 12 probes + 16 internal + 4 external, and
solving 16*I + 4*E = 207,340 against I + E = 20,719 gives
I = 10,372, E = 10,347 -- i.e. the internal batch really is passed 16 times and the
external batch 4 times, where this change passes each once. Resolution
costs 0.72 s more, for the path -> {name -> set(labels)} index over all
27,530 files.

These figures were measured against 810ea8a, before #1648 added row
deduplication to this function. Dedupe shrinks the batch identically on
both sides, so the batch-pass structure and the ratios above are
unaffected; only the absolute row counts would be smaller today.

Qualification: that database was provisioned by upstream's own schema,
which has no composite (name, path) index, so every pair query scans
rather than seeks and the absolute times are dominated by that scan
cost. The quantity this change controls is the number of batch passes,
and that is unaffected by indexing. On Kuzu the same structure shows up
without any index question, because the Kuzu adapter unrolls UNWIND $batch into one query per row to sidestep a relationship planner bug:
with all 12 label tables populated, the added test's 3-row input issues
468 session.run calls before this change and 18 after.

The batch-pass count is structural: with P of the 12 labels populated
the old code passes the internal batch P^2 times and the external
batch P times. P was 4 here; at P = 12, #1617 skips nothing and the factor is
78x.

Output is unchanged: the produced INHERITS edge set is identical. On the
corpus above both sides produced the same 20,963 INHERITS edges with an
identical per-(child_label, parent_label) breakdown across all seven
pairs that occur. Also verified by (a) the 21-project parser golden
suite (tests/fixtures/goldens), whose node/edge exports are unchanged,
(b) upstream's three existing write_inheritance_links tests, which feed
label-less rows and so exercise the fallback enumeration unmodified --
including #1617's probe-failure invariant, and (c) the added test, whose
exact-edge-set assertion passes identically before and after the change
while the query count collapses. On that corpus the ambiguity guard
fired on 74 of 20,719 rows (0.36%), which took the enumeration fallback.

Tests added

tests/unit/core/test_database_kuzu_kotlin_metadata.py::test_write_inheritance_links_groups_by_row_labels_in_kuzu

Modelled on #1617's own test and living beside it, against the same embedded
Kuzu backend, so it runs in ./tests/run_tests.sh fast with no external
service. It creates one node under every one of the 12 enumerated labels —
the scenario in which the empty-table probe can skip nothing at all — and
asserts both halves of the contract:

  • the exact INHERITS edge set produced by the labeled rows (right edges,
    correct endpoint labels, correct confidence, and nothing extra);
  • the session.run count, which drops from 468 to 18 on that input.

The edge-set assertion passes identically with and without the change, so
the test doubles as an output-identity check; only the count assertion fails
on the pre-change code.

./tests/run_tests.sh fast on this branch: 1 failed, 1282 passed, 7 skipped.
On pristine main: 1 failed, 1281 passed, 7 skipped. Identical failure sets —
the single failure, test_parser_goldens[sample_project_kotlin], is
pre-existing on main. No golden fixture changed.

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

write_inheritance_links iterates a 12x12 (child_label, parent_label)
grid and passes the FULL resolved batch to every surviving pair. CodeGraphContext#1617
made the grid sparse by probing each label table once and skipping pairs
whose table is empty -- but every pair that survives the probe still
receives the whole batch, and the number of survivors is a property of
the repo's label inventory, not of the edges being written.

1. Resolution now attaches the exact child/parent node label to each
   row. build_inheritance_and_csharp_files builds a path -> {name ->
   set(labels)} index over the 12 inheritance-eligible construct kinds
   and pins a row's child_label / parent_label only when that (path,
   name) maps to exactly one kind. The writer then runs one query per
   (child_label, parent_label) pair that actually occurs.

2. Rows whose (path, name) is ambiguous carry no label and fall back to
   the original enumeration. This is not hypothetical: as
   write_binds_links' docstring already records, Kotlin does not qualify
   `name` by enclosing scope, so a top-level interface and an unrelated
   nested class can legitimately share name+path. CodeGraphContext#1617's
   populated_labels set is retained and applied to exactly those
   fallback paths. It is deliberately NOT applied to the grouped pairs:
   those pairs come from the rows themselves, so they are never empty,
   and probing them would be pure overhead while a stale or
   lazily-created label table would let the probe silently drop a real
   INHERITS edge.

3. batch_size = 500 was declared and never used; the batch is now
   chunked. This is a separate robustness fix -- it keeps a five-figure
   UNWIND payload out of a single driver round-trip -- and it is not
   what produces the numbers below. On a repo with few populated labels
   it slightly *raises* the raw query count while cutting total work.

Relationship to CodeGraphContext#1617: complementary, not overlapping. CodeGraphContext#1617's saving is
a function of how many of the 12 label tables are empty; this change's
saving is a function of how many (child, parent) pairs the data actually
contains. On a repo where all 12 tables are non-empty, CodeGraphContext#1617 removes no
pairs at all and the full fan-out survives.

Measured, Neo4j, the pass in isolation on a 27,530-file
Python/JavaScript repo (756k nodes, 20,719 resolved rows), same store
and page cache on both sides, INHERITS deleted between runs so each
starts identical:

                      upstream/main      this change
  resolution              1.05 s            1.77 s
  write_inheritance_links 7433.5 s          620.4 s     12.0x
  batch-rows processed    207,340           21,487       9.7x
  queries                 32                80          0.4x

Query count goes UP because batch_size chunking splits the one large
pair into ~21 round-trips; the work per round-trip is what falls.
Upstream's 32 queries are 12 probes + 16 internal + 4 external, and
solving 16*I + 4*E = 207,340 against I + E = 20,719 gives I = 10,372, E
= 10,347 -- i.e. the internal batch really is passed 16 times and the
external batch 4 times, where this change passes each once. Resolution
costs 0.72 s more, for the path -> {name -> set(labels)} index over all
27,530 files.

These figures were measured against 810ea8a, before CodeGraphContext#1648 added row
deduplication to this function. Dedupe shrinks the batch identically on
both sides, so the batch-pass structure and the ratios above are
unaffected; only the absolute row counts would be smaller today.

Qualification: that database was provisioned by upstream's own schema,
which has no composite (name, path) index, so every pair query scans
rather than seeks and the absolute times are dominated by that scan
cost. The quantity this change controls is the number of batch passes,
and that is unaffected by indexing. On Kuzu the same structure shows up
without any index question, because the Kuzu adapter unrolls `UNWIND
$batch` into one query per row to sidestep a relationship planner bug:
with all 12 label tables populated, the added test's 3-row input issues
468 session.run calls before this change and 18 after.

The batch-pass count is structural: with P of the 12 labels populated
the old code passes the internal batch P^2 times and the external batch
P times. P was 4 here; at P = 12, CodeGraphContext#1617 skips nothing and the factor is
78x.

Output is unchanged: the produced INHERITS edge set is identical. On the
corpus above both sides produced the same 20,963 INHERITS edges with an
identical per-(child_label, parent_label) breakdown across all seven
pairs that occur. Also verified by (a) the 21-project parser golden
suite (tests/fixtures/goldens), whose node/edge exports are unchanged,
(b) upstream's three existing write_inheritance_links tests, which feed
label-less rows and so exercise the fallback enumeration unmodified --
including CodeGraphContext#1617's probe-failure invariant, and (c) the added test, whose
exact-edge-set assertion passes identically before and after the change
while the query count collapses. On that corpus the ambiguity guard
fired on 74 of 20,719 rows (0.36%), which took the enumeration fallback.

Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
@mollyjester
mollyjester force-pushed the perf/cgc-inherits-label-pair-grouping branch from 173215d to fa8229d Compare August 19, 2026 12:46
@mollyjester

Copy link
Copy Markdown
Contributor Author

CI note. Two checks are red here, and both fail identically on the base commit
(dc7f33da) without these changes:

  • test (windows-latest) — the e2e job fails at Run end-to-end tests with
    RuntimeError: Could not find lbug C API shared library, i.e. the ladybugdb native
    library is unavailable on the Windows runner, so indexing exits before any relationship
    pass runs. The same job fails on dc7f33da.
  • db-parity — REL_CALLS differs on ladybugdb (561 vs 678 on the other three
    backends; allowed spread is 1). This check is red on dc7f33da and on the four commits
    preceding it; it was last green at e48c3e3a.

Worth noting from the db-parity report itself, since it speaks directly to this change:

REL_INHERITS              | 145        | 145        | 145        | 145        | YES
                            Kuzudb       Ladybugdb    Falkordb     Neo4J

The label-pair grouping produces an identical INHERITS edge set on all four backends.

Locally, pytest tests/unit tests/integration gives the same failure set on this branch
and on pristine dc7f33da (3 failed, all pre-existing), with 1469 passed here vs 1468 on the
base — the +1 being the test added in this PR.

@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 (post-#1648): the new test passes alongside the batching and identity suites (23), the full unit suite is green (1383 / 7 skipped), and all 21 parser goldens pass unchanged — the output-identity claim holds with the exact-endpoint comparison. The design is right: pinning labels at resolution time from the per-path construct index turns the P²+P batch-pass structure into one pass per occurring pair, and keeping the #1617 probe only on the ambiguous-row fallback is exactly the correct scoping (probing the grouped pairs would risk dropping a real edge on a lazily-created table). Bounded <= 20 call-count assertions stay robust against the rel-batching #1648 enabled. Excellent measurement discipline throughout. Thanks @mollyjester!

@Shashankss1205
Shashankss1205 merged commit 60fcd52 into CodeGraphContext:main Aug 19, 2026
14 of 20 checks passed
@github-project-automation github-project-automation Bot moved this from Backlog tasks to Done in CGC Progress Board Aug 19, 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 19, 2026
@mollyjester
mollyjester deleted the perf/cgc-inherits-label-pair-grouping branch August 21, 2026 08:35
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