FK constraint verification rescans the entire parent table for each orphan
- Dominant language
- C
- Stars
- 268
- Forks
- 18
- Avg merge
- 2h 26m
- Merged PRs (30d)
- 454
Description
FK verification performs a full parent-table scan for every candidate orphan, including INTEGER PRIMARY KEY parents. This yields O(parent rows * orphan rows) work.
Reproduced at f5d4636e70. Fixture: N parents numbered 1..N and N children whose FK values are N+1..2N, loaded with foreign_keys temporarily off and then re-enabled. Measure `SELECT dolt_verify_constraints('--all','--output-only')` in a fresh CLI process.
Three-run local medians:
| Parents | Orphans | Seconds |
|---:|---:|---:|
| 1000 | 1000 | 0.223 |
| 2000 | 2000 | 0.860 |
| 4000 | 4000 | 3.253 |
Every measured statement returned 1 with process exit zero. These are indicative local measurements, not proposed CI thresholds. Four times the data takes about 14.6 times longer.
Use indexed parent-key lookups against the merged catalog with correct parent affinity/collation, and cache FK metadata per constraint. Add a scaling benchmark that varies parent and orphan counts independently and checks violation counts. Keep the correctness fix separate from this performance work.
Sources: https://github.com/dolthub/doltlite/blob/f5d4636e70/src/doltlite_merge_constraints_fk.c#L345 and https://github.com/dolthub/doltlite/blob/f5d4636e70/src/doltlite_merge_constraints_fk.c#L116
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in src/doltlite_merge_constraints_fk.c at lines 116 and 345, then reproduce the issue with the supplied parent/orphan fixture and dolt_verify_constraints('--all','--output-only'). Implement indexed parent-key lookups against the merged catalog with correct affinity/collation and cached FK metadata per constraint. Add a scaling benchmark varying parent and orphan counts independently, and verify violation counts while keeping correctness changes separate.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, sqlite
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100