dgraph-io / dgraph / 6190802467
66%

DEFAULT BRANCH: main
Ran
Jobs 1
Files 252
Run time 8s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 66.995% (+0.04%) from 66.96%
6190802467

push

web-flow 
perf(query): use quickselect instead of sorting while pagination (#8995)

When we get pagination request, we still sort the entire structure and
then return relevant results. This diff introduces mini select algorithm
that will only sort till we get first k elements out of n.

Both LDBC Benchmarks and MicroBenchmarks show that this is only useful
until 50%

```
LDBC Queries Benchmarks
Total elements : 300000
Current main:
BenchmarkQueries/IC09/First_:20-8                      1        36621508916 ns/op
BenchmarkQueries/IC09/First_:304368-8                  1        50905281926 ns/op
BenchmarkQueries/IC09/First_:608716-8                  1        63878833326 ns/op
BenchmarkQueries/IC09/First_:913064-8                  1        77455114015 ns/op
BenchmarkQueries/IC09/First_:1217412-8                 1        94143638593 ns/op
BenchmarkQueries/IC09/First_:1521760-8                 1        111483390712 ns/op
BenchmarkQueries/IC09/First_:1826108-8                 1        123910498449 ns/op
```

```
QuickSelect:
BenchmarkQueries/IC09/First_:20-8                      1        32248068234 ns/op
BenchmarkQueries/IC09/First_:304368-8                  1        45877353021 ns/op
BenchmarkQueries/IC09/First_:608716-8                  1        60671818631 ns/op
BenchmarkQueries/IC09/First_:913064-8                  1        73447308743 ns/op
BenchmarkQueries/IC09/First_:1217412-8                 1        90371662972 ns/op
BenchmarkQueries/IC09/First_:1521760-8                 1        112880718231 ns/op
BenchmarkQueries/IC09/First_:1826108-8                 1        125487157700 ns/op
```

In microbenchmarks, first row is the current sort. Further rows are
various different k values for the new algo

```
MicroBenchmarks
Normal Sort vs QuickSelect
BenchmarkSortQuickSort/Normal_Sort_Ratio_1000000_-8                    1        1652489894 ns/op
BenchmarkSortQuickSort/QuickSort_Sort_Ratio_1000000_1-8                1          779... (continued)

121 of 121 new or added lines in 3 files covered. (100.0%)

58866 of 87866 relevant lines covered (67.0%)

2213639.97 hits per line

New Missed Lines in Diff

Lines Coverage ∆ File
3
95.83
 types/select.go
4
87.06
 -0.19% worker/sort.go
11
86.93
 -4.31% types/sort.go

Uncovered Existing Lines

Lines Coverage ∆ File
2
85.49
 0.0% conn/raft_server.go
2
65.03
 -0.3% dgraph/cmd/zero/zero.go
2
88.95
 -1.1% graphql/subscription/poller.go
5
80.28
 -1.41% dgraph/cmd/zero/oracle.go
Jobs
ID Job ID Ran Files Coverage
1 6190802467.1 252
67.0
Source Files on build 6190802467