Merge builds secondary-index edits in the sorted-insert mutmap; cost grows superlinearly in changed rows
- Dominant language
- C
- Stars
- 268
- Forks
- 18
- Avg merge
- 2h 27m
- Merged PRs (30d)
- 447
Description
Found in a full-repo review at `0ba280f06f`.
Merge builds its secondary-index edits in the **sorted-insert** mutmap mode, while ordinary DML uses the deferred-sort mode. Index edits arrive in primary-key order, which is unordered in index-key space, so each insert shifts the order array and the cost grows faster than linearly in the number of changed rows.
## Measured
Merge of two branches that each changed a large fraction of the table (`UPDATE` on ~50% and ~33% of rows), median of one run per point:
| rows | no secondary index | index correlated with PK | index scattered vs PK |
|---|---|---|---|
| 1,000,000 | 2.250 s | 4.181 s | 5.253 s |
| 2,000,000 | 5.173 s | 13.268 s | 16.439 s |
| 3,000,000 | 6.929 s | 19.010 s | 32.004 s |
Scaling from 1M to 3M rows (3x the data): no index **3.1x**, correlated index **4.5x**, scattered index **6.1x**. The penalty over the no-index case widens steadily — **2.3x → 3.2x → 4.6x** — so the index term is growing faster than the rest of the merge and will keep widening with table size.
"Scattered" here just means the index key is not correlated with the primary key, which is the ordinary case for a secondary index on anything other than a monotonically assigned column.
## Cause
`src/doltlite_merge_rows.c:1438` initialises each index's edit map with the sorted-insert mode:
```c
rc = prollyMutMapInit(aIndexes[i].pEdits, 0);
```
`prollyMutMapInit` is `prollyMutMapInitMode(mm, isIntKey, 1)` — `keepSorted=1` (`src/prolly_mutmap.c:530-531`). Every insert then goes through `insertOrderEntry` (`src/prolly_mutmap.c:510-528`), which `memmove`s the tail of the order array:
```c
if( idx < mm->nEntries ){
memmove(&mm->aOrder[idx+1], &mm->aOrder[idx],
(mm->nEntries - idx) * sizeof(int));
}
```
For the primary key the three-way diff supplies edits in ascending key order, so `idx == nEntries` and the shift is free. For a secondary index the same edits arrive in primary-key order, so each insert lands in the middle and shifts ~n/2 ints.
The ordinary DML path already avoids this — `src/prolly_btree_mutation.c:547` uses `prollyMutMapInitMode(pMap, pCur->curIntKey, 0)`, i.e. unsorted with a deferred sort.
## Fix
Use the deferred-sort mode for merge index edits, as the DML path does. A one-line change to that call is the obvious candidate and was measured during the review as restoring near-linear scaling, but I have not audited the dedup/ordering semantics of the unsorted mode for this call site — treat the one-liner as sizing evidence rather than a vetted patch.
Whatever the fix, the benchmark that should have caught this cannot: `make_merge_data_db` in `test/vc_perf_ceiling.sh:164` builds `t(id INTEGER PRIMARY KEY, v TEXT)` with **no secondary index**, and changes only `MERGE_CHANGE_ROWS=2000` of `MERGE_ROWS=100000` in contiguous PK ranges — 2% of rows, in exactly the order that makes the sorted insert free.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start at src/doltlite_merge_rows.c:1438 and compare the mutmap initialization with src/prolly_btree_mutation.c:547; read the sorted and deferred-sort paths in src/prolly_mutmap.c. Review deduplication and ordering semantics, then inspect test/vc_perf_ceiling.sh:164. Done means merge index edits scale near-linearly and coverage exercises a secondary index with scattered keys.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, sqlite
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100