dolthub / dolthub/doltlite

dolt_blame is O(commits x rows) and allocates three strings per row per assignment

Closed
#2,919 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.