search

ssbc / jitdb

A database on top of a log with automatic index generation and maintenance
50 stars 7 forks source link

fix paginate on prefix index false positives #231

Closed staltz closed 2 years ago

staltz commented 2 years ago

Context

I was updating ssb-db2 in some other libraries and noticed an infinite loop somewhere in the stack and it was in jitdb, related to pagination.

Problem

Reminder: we used to increment seq with the limit that defines the page size, then we changed that to be seqs.length.

If you're using a prefix index, the initial seqs may contain false positives, which are then removed in the "filters". So then the seqs.length turns out to be zero. Since the calculation of nextSeq was seq + seqs.length, this meant that the same seq got repeated over and over again, infinitely.

Solution

If seqs.length is zero, we fallback to using limit as the next page size.

1st :x: 2nd :heavy_check_mark:

github-actions[bot] commented 2 years ago

Benchmark results

Part Speed Heap Change Samples
Count 1 big index (3rd run) 0.54ms ± 0.37ms 1.79 kB ± 25.81 kB 40
Create an index twice concurrently 813.52ms ± 5.28ms 14.64 kB ± 41.92 kB 66
Load core indexes 1.21ms ± 0.02ms 86.62 B ± 294.65 B 7089
Load two indexes concurrently 568.27ms ± 3.43ms 229.15 kB ± 325.13 kB 20
Paginate 10 results 20.04ms ± 0.24ms -7.65 kB ± 37.65 kB 27
Paginate 20000 msgs with pageSize=5 7839.71ms ± 116.61ms 2.42 MB ± 6.38 MB 5
Paginate 20000 msgs with pageSize=500 680.13ms ± 9.61ms 84.63 kB ± 876.48 kB 17
Query 1 big index (1st run) 779.87ms ± 2.67ms -41.2 kB ± 63.8 kB 70
Query 1 big index (2nd run) 366.2ms ± 2.85ms 4.85 kB ± 35.38 kB 40
Query 3 indexes (1st run) 1162.17ms ± 9.07ms 66.5 kB ± 84.26 kB 45
Query 3 indexes (2nd run) 271.79ms ± 1.08ms 10.81 kB ± 36.03 kB 49
Query a prefix map (1st run) 316.38ms ± 1.09ms 44.35 kB ± 122.2 kB 21
Query a prefix map (2nd run) 9.73ms ± 0.88ms 1.29 kB ± 247.31 kB 25
github-actions[bot] commented 2 years ago

Benchmark results

Part Speed Heap Change Samples
Count 1 big index (3rd run) 0.95ms ± 0.62ms 9.7 kB ± 32.81 kB 46
Create an index twice concurrently 606.55ms ± 1.91ms -19.75 kB ± 23.37 kB 90
Load core indexes 1.24ms ± 0.02ms 90.7 B ± 418.46 B 6416
Load two indexes concurrently 641.42ms ± 13.3ms -356.59 kB ± 266.46 kB 18
Paginate 10 results 20.06ms ± 0.17ms -6.63 kB ± 51.33 kB 27
Paginate 20000 msgs with pageSize=5 7907.08ms ± 174.24ms 2.61 MB ± 2.16 MB 5
Paginate 20000 msgs with pageSize=500 552.65ms ± 3.77ms 438.12 kB ± 646.52 kB 21
Query 1 big index (1st run) 1050.75ms ± 7.86ms -46.12 kB ± 71.43 kB 51
Query 1 big index (2nd run) 323.61ms ± 1.26ms -8.86 kB ± 29.11 kB 45
Query 3 indexes (1st run) 1062.4ms ± 7.56ms -76.19 kB ± 88.05 kB 50
Query 3 indexes (2nd run) 302.73ms ± 4.96ms -1.78 kB ± 45 kB 40
Query a prefix map (1st run) 271.39ms ± 1.88ms 60.74 kB ± 204.24 kB 23
Query a prefix map (2nd run) 8.68ms ± 0.51ms 57.41 kB ± 64.94 kB 24