electric-sql / electric-sql/d2ts
Problem with compaction in SQLite
- Dominant language
- TypeScript
- Stars
- 562
- Forks
- 12
- PR merge metrics
- No merged PRs in 30d
Description
Consider the following test:
```ts
test('should handle compaction with incomparable versions', () => {
const version1 = v([1, 0])
const version2 = v([1, 1])
const version3 = v([2, 0])
index.addValue('key1', version1, [10, 1])
index.addValue('key1', version2, [10, 2])
index.addValue('key1', version3, [10, -1])
const frontier = new Antichain([v([1, 2]), v([2, 1])])
index.compact(frontier) // should compact into [1, 1] -> [10, 3] and [2, 1] -> [10, -1]
const result1 = index.reconstructAt('key1', v([1, 2]))
expect(result1).toEqual([[10, 3]]) // fails with SQLite
const result2 = index.reconstructAt('key1', v([2, 1]))
expect(result2).toEqual([
[10, 3],
[10, -1],
])
})
```
The frontier indicates that we will only get updates `>= [1, 2]` or `>= [2, 1]`.
- Since both `[1, 0]` and `[1, 1]` are `< [1, 2]` we can compact them into timestamp [1, 1] and take the sum of their multiplicities: `[10, 3]`
- We're not collapsing version [1, 1] with [2, 0] because they are incomparable and we could still receive updates at version [1, 2] for instance
According to the [compaction algorithm](https://justinjaffray.com/compaction/), the compacted index should be:
```
'key1' -> [1, 1] -> [10, 3]
-> [2, 1] -> [10, -1]
```
The test from above works in-memory but when executed against SQLite it fails because `result1` is `[]` and thus `expect(result1).toEqual([[10, 3]])` fails. Seems to indicate that there is a bug in `SQLIndex`.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.