dolt_blame is O(commits x rows) and allocates three strings per row per assignment
- Dominant language
- C
- Stars
- 268
- Forks
- 18
- Avg merge
- 2h 26m
- Merged PRs (30d)
- 454
Description
Found in a full-repo review at `0ba280f06f`.
`dolt_blame_` compares every still-unattributed row against a full cursor over the table at every commit, so its cost is the product of history depth and table size.
## Measured
`SELECT count(*) FROM dolt_blame_t`:
| rows | 10 commits | 50 commits | 200 commits |
|---|---|---|---|
| 20,000 | 0.108 s | 0.318 s | 1.105 s |
| 100,000 | 0.439 s | 1.526 s | 5.522 s |
20x the commits costs 10-13x; 5x the rows costs 4-5x. Roughly O(commits x rows), about 276 ns per commit-row pair. A 100k-row table with 200 commits of history already takes 5.5 s, and blame is a read.
Each commit's work is a fresh pass over the unresolved rows regardless of how few rows that commit actually touched, even though the engine computes commit-to-commit diffs elsewhere.
## Cause
`blameCompareAgainstRef` (`src/doltlite_blame.c:528`) loops over every row in the cursor at each commit:
```c
for(i=0; inRows; i++){
BlameRow *r = &pCur->aRows[i];
...
if( r->blamed ) continue;
if( haveRef ){
if( canScanRef ){
int cmp = 1;
while( refCurValid ){
cmp = blameCursorCompareRowKey(&refCur, refFlags, r);
```
and `blameAssign` (`src/doltlite_blame.c:457-474`) allocates three strings per row per assignment, so every row attributed to the same commit gets a private copy of that commit's committer, email and message:
```c
pRow->zCommitter = sqlite3_mprintf("%s", pCommit->zName ? pCommit->zName : "");
pRow->zEmail = sqlite3_mprintf("%s", pCommit->zEmail ? pCommit->zEmail : "");
pRow->zMessage = sqlite3_mprintf("%s", pCommit->zMessage ? pCommit->zMessage : "");
```
## Fix
Drive blame from the per-commit diff the engine already produces, so each commit costs O(rows it changed) rather than O(rows still unattributed), and intern the commit metadata once per commit with the rows referencing it.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading blameCompareAgainstRef at src/doltlite_blame.c:528 and blameAssign at lines 457-474, then reproduce the SELECT count(*) FROM dolt_blame_t measurements. The work is done when blame follows per-commit diffs, scales with rows changed rather than unresolved rows, and commit metadata is shared once per commit instead of copied per row.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, sqlite
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100