dgraph-io / dgraph / 6190802467

66%

push

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