search

bakoe / hyrise

Hyrise is a research in-memory database.
https://hpi.de/plattner/projects/hyrise.html
MIT License
0 stars 0 forks source link

WIP: Add NewSort operator implementation #11

Open bakoe opened 4 years ago

bakoe commented 4 years ago
Archived: Open To Dos before re-implementation of input materialization
- [x] Fix the NULL-using tests failing (i. e. allow the NewSort operator to handle tables with NULL value, paying attention to the specific `OrderByMode`): ```javascript [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneColumnWithNull/1 unknown file: Failure C++ exception with description "boost::bad_get: failed value get using boost::get" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneColumnWithNull/1, where GetParam() = Dictionary (2 ms) [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneColumnWithNull/1 unknown file: Failure C++ exception with description "boost::bad_get: failed value get using boost::get" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneColumnWithNull/1, where GetParam() = Dictionary (2 ms) [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneColumnWithNullsLast/1 unknown file: Failure C++ exception with description "src/lib/operators/sort_new.cpp:50 Currently unsupported order_by_mode" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneColumnWithNullsLast/1, where GetParam() = Dictionary (3 ms) [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneColumnWithNullsLast/1 unknown file: Failure C++ exception with description "src/lib/operators/sort_new.cpp:50 Currently unsupported order_by_mode" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneColumnWithNullsLast/1, where GetParam() = Dictionary (3 ms) [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneDictSegmentWithNull/1 unknown file: Failure C++ exception with description "boost::bad_get: failed value get using boost::get" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.AscendingSortOfOneDictSegmentWithNull/1, where GetParam() = Dictionary (2 ms) [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneDictSegmentWithNull/1 unknown file: Failure C++ exception with description "boost::bad_get: failed value get using boost::get" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.DescendingSortOfOneDictSegmentWithNull/1, where GetParam() = Dictionary (2 ms) ``` - [x] Investigate why the `SortAfterOuterJoin` test fails for the SortNew operator and fix the failing test: ```javascript [ RUN ] DictionaryEncodingTypes/OperatorsSortNewTest.SortAfterOuterJoin/1 unknown file: Failure C++ exception with description "boost::bad_get: failed value get using boost::get" thrown in the test body. [ FAILED ] DictionaryEncodingTypes/OperatorsSortNewTest.SortAfterOuterJoin/1, where GetParam() = Dictionary (2 ms) ```

Open To Dos:

bakoe commented 4 years ago

Intermediate micro benchmark results created with commit 619803355438e61d43a118c7433c467cd1836432 (without Multi Column sorting micro benchmarks for the SortNew operator), running on a the vm-appleton:

Bastian.Koenig@vm-appleton:~/hyrise$ cmake-build-release/hyriseMicroBenchmarks --benchmark_filter=BM_Sort*
2020-01-17 18:58:33
Running cmake-build-release/hyriseMicroBenchmarks
Run on (32 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x32)
  L1 Instruction 32K (x32)
  L2 Unified 256K (x32)
  L3 Unified 25600K (x32)
Load Average: 0.02, 0.18, 0.11
--------------------------------------------------------------------------------------------------
Benchmark                                                        Time             CPU   Iterations
--------------------------------------------------------------------------------------------------
SortPicoBenchmark/BM_SortPico                                 2967 ns         2967 ns       221461
SortSmallBenchmark/BM_SortSmall                             634902 ns       634902 ns         1000
SortBenchmark/BM_Sort                                     11222083 ns     11222086 ns           69
SortLargeBenchmark/BM_SortLarge                           70624971 ns     70624062 ns           10
SortReferencePicoBenchmark/BM_SortReferencePico               3588 ns         3588 ns       199678
SortReferenceSmallBenchmark/BM_SortReferenceSmall           866087 ns       866088 ns          733
SortReferenceBenchmark/BM_SortReference                   15101429 ns     15100713 ns           56
SortReferenceLargeBenchmark/BM_SortReferenceLarge        111153960 ns    111145409 ns            6
SortStringSmallBenchmark/BM_SortStringSmall                2726626 ns      2726598 ns          323
SortStringBenchmark/BM_SortString                         32748152 ns     32746559 ns           27
SortStringLargeBenchmark/BM_SortStringLarge              483443022 ns    483144956 ns            2
SortNullBenchmark/BM_SortNullBenchmark                     7519293 ns      7518876 ns          114
SortBenchmark/BM_SortSingleColumnSQL                      12067350 ns     12065987 ns           52
[PERF] Multiple ORDER BYs are executed one-by-one at src/lib/logical_query_plan/lqp_translator.cpp:272
    Performance can be affected. This warning is only shown once.

SortBenchmark/BM_SortMultiColumnSQL                       24340610 ns     24340623 ns           24
SortNewPicoBenchmark/BM_SortNewPico                           3122 ns         3122 ns       223231
SortNewSmallBenchmark/BM_SortNewSmall                       646944 ns       646494 ns         1000
SortNewBenchmark/BM_SortNew                               10494336 ns     10494135 ns           76
SortNewLargeBenchmark/BM_SortNewLarge                     68281783 ns     68275161 ns            9
SortNewReferencePicoBenchmark/BM_SortNewReferencePico         3649 ns         3649 ns       182925
SortNewReferenceSmallBenchmark/BM_SortNewReferenceSmall     781442 ns       781320 ns         1110
SortNewReferenceBenchmark/BM_SortNewReference             15589593 ns     15586984 ns           55
SortNewReferenceLargeBenchmark/BM_SortNewReferenceLarge  115312258 ns    115290692 ns            6
SortNewStringSmallBenchmark/BM_SortNewStringSmall          3091580 ns      3091524 ns          180
SortNewStringBenchmark/BM_SortNewString                   32264621 ns     32264618 ns           27
SortNewStringLargeBenchmark/BM_SortNewStringLarge        359665275 ns    359658318 ns            2
SortNewNullBenchmark/BM_SortNewNullBenchmark               7758200 ns      7758095 ns          116
bakoe commented 4 years ago

I've run some intermediate benchmarks (with a partial refactoring of the Sort micro benchmarks as stated in #5; see 2c184b2bf963971f599e648966f96afcc31dae45) for comparing the multi-column sort performance of the Sort operator vs. the performance of the newly implemented SortNew operator:

./cmake-build-release/hyriseMicroBenchmarks --benchmark_filter="BM_Sort*"
2020-01-19 22:53:42
Running ./cmake-build-release/hyriseMicroBenchmarks
Run on (16 X 2300 MHz CPU s)
CPU Caches:
  L1 Data 32K (x8)
  L1 Instruction 32K (x8)
  L2 Unified 262K (x8)
  L3 Unified 16777K (x1)
Load Average: 3.10, 2.83, 2.60
--------------------------------------------------------------------------------------------------
Benchmark                                                        Time             CPU   Iterations
--------------------------------------------------------------------------------------------------
BM_SortWithVaryingRowCount/4                                  4570 ns         4567 ns       127985
BM_SortWithVaryingRowCount/10                                 6602 ns         6602 ns        87392
BM_SortWithVaryingRowCount/100                               20420 ns        20412 ns        33334
BM_SortWithVaryingRowCount/1000                             197975 ns       197843 ns         3462
BM_SortWithVaryingRowCount/10000                           2196329 ns      2195824 ns          312
BM_SortWithVaryingRowCount/100000                         24868034 ns     24864500 ns           28
BM_SortWithVaryingRowCount/400000                        115027337 ns    114965000 ns            6
[PERF] operator[] used at src/lib/storage/value_segment.cpp:70
    Performance can be affected. This warning is only shown once.

BM_SortNewWithVaryingRowCount/4                               2912 ns         2910 ns       234699
BM_SortNewWithVaryingRowCount/10                              4660 ns         4656 ns       128011
BM_SortNewWithVaryingRowCount/100                            18059 ns        18058 ns        37149
BM_SortNewWithVaryingRowCount/1000                          197950 ns       197835 ns         3476
BM_SortNewWithVaryingRowCount/10000                        2252016 ns      2251502 ns          307
BM_SortNewWithVaryingRowCount/100000                      25065669 ns     25056000 ns           28
BM_SortNewWithVaryingRowCount/400000                     112893218 ns    112844833 ns            6

Notice how the SortNew apparently outperforms the existing Sort operator in sorting a table by two different columns when the table has ≤ 1'000 rows and performs approximately equal to the existing Sort operator in sorting a table (by 2 columns as well) for tables sizes > 1'000 and ≤ 400'000 rows.

jonasnoki commented 4 years ago

After adapting the sort_new operators column materialization (the one before the sort) even large tables improve a little bit in performance:

Bastian.Koenig@vm-appleton:~/hyrise$ cmake-build-release/hyriseMicroBenchmarks --benchmark_filter=BM_Sort*
2020-01-22 12:04:26
Running cmake-build-release/hyriseMicroBenchmarks
Run on (32 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x32)
  L1 Instruction 32K (x32)
  L2 Unified 256K (x32)
  L3 Unified 25600K (x32)
Load Average: 0.02, 2.27, 2.81
-------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
-------------------------------------------------------------------------------
BM_SortWithVaryingRowCount/4               8819 ns         8818 ns        60783
BM_SortWithVaryingRowCount/10             13080 ns        13079 ns        48500
BM_SortWithVaryingRowCount/100            41437 ns        41433 ns        13124
BM_SortWithVaryingRowCount/1000          374867 ns       374864 ns         1650
BM_SortWithVaryingRowCount/10000        3911166 ns      3910816 ns          160
BM_SortWithVaryingRowCount/100000      48473336 ns     48472951 ns           11
BM_SortWithVaryingRowCount/400000     232502381 ns    232475676 ns            3
BM_SortNewWithVaryingRowCount/4            5678 ns         5677 ns       120084
BM_SortNewWithVaryingRowCount/10           8085 ns         8084 ns        70163
BM_SortNewWithVaryingRowCount/100         24213 ns        24208 ns        25058
BM_SortNewWithVaryingRowCount/1000       275335 ns       275334 ns         2267
BM_SortNewWithVaryingRowCount/10000     3212212 ns      3211948 ns          215
BM_SortNewWithVaryingRowCount/100000   34398211 ns     34396340 ns           18
BM_SortNewWithVaryingRowCount/400000  168475986 ns    168469346 ns            4
jonasnoki commented 4 years ago 
Bastian.Koenig@vm-appleton:~/hyrise$ cmake-build-release/hyriseMicroBenchmarks --benchmark_filter=BM_Sort*
2020-01-29 00:17:39
Running cmake-build-release/hyriseMicroBenchmarks
Run on (32 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x32)
  L1 Instruction 32K (x32)
  L2 Unified 256K (x32)
  L3 Unified 25600K (x32)
Load Average: 0.28, 0.39, 1.01
-------------------------------------------------------------------------------------------
Benchmark                                                 Time             CPU   Iterations
-------------------------------------------------------------------------------------------
BM_SortWithVaryingRowCount/4                           9054 ns         9053 ns        73046
BM_SortWithVaryingRowCount/10                         14331 ns        14331 ns        44133
BM_SortWithVaryingRowCount/100                        45684 ns        45677 ns        13209
BM_SortWithVaryingRowCount/1000                      382270 ns       382264 ns         1687
BM_SortWithVaryingRowCount/10000                    4623719 ns      4623636 ns          151
BM_SortWithVaryingRowCount/100000                  50334930 ns     50333797 ns           12
BM_SortWithVaryingRowCount/400000                 234103521 ns    234103708 ns            3
BM_SortNewWithVaryingRowCount/4                        5591 ns         5590 ns       107644
BM_SortNewWithVaryingRowCount/10                       6732 ns         6732 ns        90825
BM_SortNewWithVaryingRowCount/100                     20248 ns        20248 ns        36016
BM_SortNewWithVaryingRowCount/1000                   180303 ns       180304 ns         3513
BM_SortNewWithVaryingRowCount/10000                 2064146 ns      2064148 ns          315
BM_SortNewWithVaryingRowCount/100000               25547165 ns     25545023 ns           26
BM_SortNewWithVaryingRowCount/400000              128593047 ns    128590158 ns            6
BM_SortWithVaryingRowCountTwoColumns/4                10788 ns        10787 ns        61572
BM_SortWithVaryingRowCountTwoColumns/10               12761 ns        12761 ns        44126
BM_SortWithVaryingRowCountTwoColumns/100              57247 ns        57247 ns        13021
BM_SortWithVaryingRowCountTwoColumns/1000            429301 ns       429301 ns         1488
BM_SortWithVaryingRowCountTwoColumns/10000          4654662 ns      4654703 ns          149
BM_SortWithVaryingRowCountTwoColumns/100000        55054049 ns     55049885 ns           12
BM_SortWithVaryingRowCountTwoColumns/400000       265658538 ns    265467470 ns            3
BM_SortNewWithVaryingRowCountTwoColumns/4              6430 ns         6430 ns       100107
BM_SortNewWithVaryingRowCountTwoColumns/10             7918 ns         7917 ns        74352
BM_SortNewWithVaryingRowCountTwoColumns/100           26296 ns        26296 ns        22942
BM_SortNewWithVaryingRowCountTwoColumns/1000         258079 ns       258079 ns         2310
BM_SortNewWithVaryingRowCountTwoColumns/10000       3148583 ns      3148580 ns          203
BM_SortNewWithVaryingRowCountTwoColumns/100000     35998319 ns     35997960 ns           19
BM_SortNewWithVaryingRowCountTwoColumns/400000    175095618 ns    175075593 ns            4
BM_SortWithNullValues/4                               11228 ns        11228 ns        53613
BM_SortWithNullValues/10                              13628 ns        13628 ns        43017
BM_SortWithNullValues/100                             49147 ns        49123 ns        12345
BM_SortWithNullValues/1000                           447635 ns       447387 ns         1786
BM_SortWithNullValues/10000                         4723280 ns      4723180 ns          148
BM_SortWithNullValues/100000                       54532270 ns     54532308 ns           12
BM_SortWithNullValues/400000                      251274586 ns    251269863 ns            2
BM_SortNewWithNullValues/4                             5554 ns         5554 ns        90978
BM_SortNewWithNullValues/10                            6858 ns         6858 ns       100893
BM_SortNewWithNullValues/100                          22170 ns        22170 ns        30102
BM_SortNewWithNullValues/1000                        200598 ns       200582 ns         2887
BM_SortNewWithNullValues/10000                      2304731 ns      2304732 ns          272
BM_SortNewWithNullValues/100000                    28883592 ns     28883618 ns           23
BM_SortNewWithNullValues/400000                   141272962 ns    141272981 ns            4
BM_SortWithReferenceSegments/4                         5190 ns         5189 ns       134607
BM_SortWithReferenceSegments/10                        7308 ns         7308 ns        89028
BM_SortWithReferenceSegments/100                      21249 ns        21239 ns        29666
BM_SortWithReferenceSegments/1000                    191765 ns       191764 ns         3498
BM_SortWithReferenceSegments/10000                  1997696 ns      1997612 ns          364
BM_SortWithReferenceSegments/100000                24718954 ns     24718344 ns           26
BM_SortWithReferenceSegments/400000               110516548 ns    110508640 ns            6
BM_SortNewWithReferenceSegments/4                      5192 ns         5191 ns       109002
BM_SortNewWithReferenceSegments/10                     7165 ns         7165 ns        87963
BM_SortNewWithReferenceSegments/100                   20897 ns        20897 ns        31619
BM_SortNewWithReferenceSegments/1000                 166038 ns       166038 ns         3527
BM_SortNewWithReferenceSegments/10000               2103454 ns      2103453 ns          307
BM_SortNewWithReferenceSegments/100000             24832392 ns     24831420 ns           25
BM_SortNewWithReferenceSegments/400000            105750521 ns    105750517 ns            6
BM_SortWithReferenceSegmentsTwoColumns/4               9679 ns         9679 ns        62770
BM_SortWithReferenceSegmentsTwoColumns/10             14031 ns        14030 ns        45710
BM_SortWithReferenceSegmentsTwoColumns/100            41535 ns        41535 ns        13159
BM_SortWithReferenceSegmentsTwoColumns/1000          429410 ns       429410 ns         1622
BM_SortWithReferenceSegmentsTwoColumns/10000        4431760 ns      4431664 ns          156
BM_SortWithReferenceSegmentsTwoColumns/100000      52094638 ns     52094689 ns           12
BM_SortWithReferenceSegmentsTwoColumns/400000     245393594 ns    245393612 ns            3
BM_SortNewWithReferenceSegmentsTwoColumns/4            6945 ns         6944 ns        95258
BM_SortNewWithReferenceSegmentsTwoColumns/10          10224 ns        10224 ns        72015
BM_SortNewWithReferenceSegmentsTwoColumns/100         27663 ns        27663 ns        23911
BM_SortNewWithReferenceSegmentsTwoColumns/1000       285227 ns       285228 ns         2250
BM_SortNewWithReferenceSegmentsTwoColumns/10000     3256384 ns      3254864 ns          200
BM_SortNewWithReferenceSegmentsTwoColumns/100000   40219461 ns     40219509 ns           17
BM_SortNewWithReferenceSegmentsTwoColumns/400000  187384764 ns    187273666 ns            3
BM_SortWithStrings/4                                  12328 ns        12328 ns        53482
BM_SortWithStrings/10                                 19516 ns        19516 ns        33154
BM_SortWithStrings/100                               111461 ns       111454 ns         5012
BM_SortWithStrings/1000                             1298738 ns      1298629 ns          466
BM_SortWithStrings/10000                           16078877 ns     16062119 ns           40
BM_SortWithStrings/100000                         194340626 ns    194337517 ns            3
BM_SortWithStrings/400000                        1062015057 ns   1061998100 ns            1
BM_SortNewWithStrings/4                                5792 ns         5792 ns       120448
BM_SortNewWithStrings/10                               9358 ns         9358 ns        68224
BM_SortNewWithStrings/100                             56589 ns        56584 ns        10906
BM_SortNewWithStrings/1000                           690180 ns       690180 ns          983
BM_SortNewWithStrings/10000                         8109063 ns      8109082 ns           81
BM_SortNewWithStrings/100000                       92813373 ns     92813585 ns            6
BM_SortNewWithStrings/400000                      515892386 ns    515886386 ns            2

These are the results of the concluded refactoring of the benchmarks.