dolthub / dolthub/doltlite

Merge builds secondary-index edits in the sorted-insert mutmap; cost grows superlinearly in changed rows

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.