hyrise · niklasmohrin · Aug 16, 2023 · Aug 16, 2023 · Aug 16, 2023 · Aug 1, 2023
diff --git a/hyrise:master b/hyrise:master
@@ -4,13 +4,13 @@
 | ------------------------- | ---------------- | -------- | ------------------------------------- |
 | autoconf                  | >= 2.69          |    All   |                                    No |
 | boost                     | >= 1.70.0        |    All   |                                    No |
-| clang                     | >= 11.0          |    All   |                 Yes, if gcc installed |
-| clang-format              | >= 11.0          |    All   |                      Yes (formatting) |
-| clang-tidy                | >= 11.0          |    All   |                         Yes (linting) |
+| clang                     | >= 13.0          |    All   |                 Yes, if gcc installed |
+| clang-format              | >= 13.0          |    All   |                      Yes (formatting) |
+| clang-tidy                | >= 13.0          |    All   |                         Yes (linting) |
 | coreutils                 | any              |    Mac   |                         Yes (scripts) |
 | cmake                     | >= 3.18          |    All   |                                    No |
 | dos2unix                  | any              |    All   |                         Yes (linting) |
-| gcc                       | >= 9.1           |    All   | Yes, if clang installed, not for OS X |
+| gcc                       | >= 10.0          |    All   | Yes, if clang installed, not for OS X |
 | gcovr                     | >= 3.2           |    All   |                        Yes (coverage) |
 | graphviz                  | any              |    All   |             Yes (query visualization) |
 | libnuma-dev               | any              |    Linux |                            Yes (numa) |

@@ -9,16 +9,16 @@ RUN apt-get update \
         autoconf \
         bash-completion \
         bc \
-        clang-11 \
+        clang-13 \
         clang-14 \
         clang-format-14 \
         clang-tidy-14 \
         cmake \
         curl \
         dos2unix \
-        g++-9 \
+        g++-10 \
         g++-11 \
-        gcc-9 \
+        gcc-10 \
         gcc-11 \
         gcovr \
         git \

@@ -88,9 +88,9 @@ try {
             // If you want to upgrade compiler versions, please update install_dependencies.sh,  DEPENDENCIES.md, and
             // the documentation (README, Wiki).
             clang = '-DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++'
-            clang11 = '-DCMAKE_C_COMPILER=clang-11 -DCMAKE_CXX_COMPILER=clang++-11'
+            clang13 = '-DCMAKE_C_COMPILER=clang-13 -DCMAKE_CXX_COMPILER=clang++-13'
             gcc = '-DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++'
-            gcc9 = '-DCMAKE_C_COMPILER=gcc-9 -DCMAKE_CXX_COMPILER=g++-9'
+            gcc10 = '-DCMAKE_C_COMPILER=gcc-10 -DCMAKE_CXX_COMPILER=g++-10'
 
             debug = '-DCMAKE_BUILD_TYPE=Debug'
             release = '-DCMAKE_BUILD_TYPE=Release'
@@ -113,8 +113,8 @@ try {
             mkdir clang-relwithdebinfo-thread-sanitizer && cd clang-relwithdebinfo-thread-sanitizer &&   ${cmake} ${relwithdebinfo} ${clang}            -DENABLE_THREAD_SANITIZATION=ON .. &\
             mkdir gcc-debug && cd gcc-debug &&                                                           ${cmake} ${debug}          ${gcc}              .. &\
             mkdir gcc-release && cd gcc-release &&                                                       ${cmake} ${release}        ${gcc}              .. &\
-            mkdir clang-11-debug && cd clang-11-debug &&                                                 ${cmake} ${debug}          ${clang11}          .. &\
-            mkdir gcc-9-debug && cd gcc-9-debug &&                                                       ${cmake} ${debug}          ${gcc9}             .. &\
+            mkdir clang-13-debug && cd clang-13-debug &&                                                 ${cmake} ${debug}          ${clang13}          .. &\
+            mkdir gcc-10-debug && cd gcc-10-debug &&                                                       ${cmake} ${debug}          ${gcc10}             .. &\
             wait"
           }
 
@@ -123,20 +123,20 @@ try {
               sh "cd clang-debug && make all -j \$(( \$(nproc) / 4))"
               sh "./clang-debug/hyriseTest clang-debug"
             }
-          }, clang11Debug: {
-            stage("clang-11-debug") {
-              sh "cd clang-11-debug && make all -j \$(( \$(nproc) / 4))"
-              sh "./clang-11-debug/hyriseTest clang-11-debug"
+          }, clang13Debug: {
+            stage("clang-13-debug") {
+              sh "cd clang-13-debug && make all -j \$(( \$(nproc) / 4))"
+              sh "./clang-13-debug/hyriseTest clang-13-debug"
             }
           }, gccDebug: {
             stage("gcc-debug") {
               sh "cd gcc-debug && make all -j \$(( \$(nproc) / 4))"
               sh "cd gcc-debug && ./hyriseTest"
             }
-          }, gcc9Debug: {
-            stage("gcc-9-debug") {
-              sh "cd gcc-9-debug && make all -j \$(( \$(nproc) / 4))"
-              sh "cd gcc-9-debug && ./hyriseTest"
+          }, gcc10Debug: {
+            stage("gcc-10-debug") {
+              sh "cd gcc-10-debug && make all -j \$(( \$(nproc) / 4))"
+              sh "cd gcc-10-debug && ./hyriseTest"
             }
           }, lint: {
             stage("Linting") {
@@ -272,29 +272,6 @@ try {
                 Utils.markStageSkippedForConditional("clangRelWithDebInfoThreadSanitizer")
               }
             }
-          }, clangDebugCoverage: {
-            stage("clang-debug-coverage") {
-              if (env.BRANCH_NAME == 'master' || full_ci) {
-                sh "./scripts/coverage.sh --generate_badge=true"
-                sh "find coverage -type d -exec chmod +rx {} \\;"
-                archive 'coverage_badge.svg'
-                archive 'coverage_percent.txt'
-                publishHTML (target: [
-                  allowMissing: false,
-                  alwaysLinkToLastBuild: false,
-                  keepAll: true,
-                  reportDir: 'coverage',
-                  reportFiles: 'index.html',
-                  reportName: "Llvm-cov_Report"
-                ])
-                script {
-                  coverageChange = sh script: "./scripts/compare_coverage.sh", returnStdout: true
-                  githubNotify context: 'Coverage', description: "$coverageChange", status: 'SUCCESS', targetUrl: "${env.BUILD_URL}/RCov_20Report/index.html"
-                }
-              } else {
-                Utils.markStageSkippedForConditional("clangDebugCoverage")
-              }
-            }
           }
 
           // We run this test in an own stage since we encountered issues with multiple concurrent calls to the external DB generator.

@@ -50,7 +50,7 @@ if echo $REPLY | grep -E '^[Yy]$' > /dev/null; then
             echo "Installing dependencies (this may take a while)..."
             if sudo apt-get update >/dev/null; then
                 # Packages added here should also be added to the Dockerfile
-                sudo apt-get install --no-install-recommends -y autoconf bash-completion bc clang-11 clang-14 clang-format-14 clang-tidy-14 cmake curl dos2unix g++-9 gcc-9 g++-11 gcc-11 gcovr git graphviz libboost-all-dev libhwloc-dev libncurses5-dev libnuma-dev libnuma1 libpq-dev libreadline-dev libsqlite3-dev libtbb-dev lld man parallel postgresql-server-dev-all python3 python3-pip valgrind &
+                sudo apt-get install --no-install-recommends -y autoconf bash-completion bc clang-13 clang-14 clang-format-14 clang-tidy-14 cmake curl dos2unix g++-10 gcc-10 g++-11 gcc-11 gcovr git graphviz libboost-all-dev libhwloc-dev libncurses5-dev libnuma-dev libnuma1 libpq-dev libreadline-dev libsqlite3-dev libtbb-dev lld man parallel postgresql-server-dev-all python3 python3-pip valgrind &
 
                 if ! git submodule update --jobs 5 --init --recursive; then
                     echo "Error during git fetching submodules."
@@ -70,8 +70,8 @@ if echo $REPLY | grep -E '^[Yy]$' > /dev/null; then
                 fi
 
                 sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-11 90 --slave /usr/bin/g++ g++ /usr/bin/g++-11
-                # we use llvm-profdata-11 and llvm-cov-11 due to an unresolved issue with coverage under clang14 (https://github.com/llvm/llvm-project/issues/54907)
-                sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-14 90 --slave /usr/bin/clang++ clang++ /usr/bin/clang++-14 --slave /usr/bin/clang-tidy clang-tidy /usr/bin/clang-tidy-14 --slave /usr/bin/llvm-profdata llvm-profdata /usr/bin/llvm-profdata-11 --slave /usr/bin/llvm-cov llvm-cov /usr/bin/llvm-cov-11 --slave /usr/bin/clang-format clang-format /usr/bin/clang-format-14
+                # we use llvm-profdata-13 and llvm-cov-13 due to an unresolved issue with coverage under clang14 (https://github.com/llvm/llvm-project/issues/54907)
+                sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-14 90 --slave /usr/bin/clang++ clang++ /usr/bin/clang++-14 --slave /usr/bin/clang-tidy clang-tidy /usr/bin/clang-tidy-14 --slave /usr/bin/llvm-profdata llvm-profdata /usr/bin/llvm-profdata-13 --slave /usr/bin/llvm-cov llvm-cov /usr/bin/llvm-cov-13 --slave /usr/bin/clang-format clang-format /usr/bin/clang-format-14
             else
                 echo "Error during installation."
                 exit 1

@@ -33,16 +33,16 @@ fi
 mkdir -p build-coverage
 cd build-coverage
 
-# We use clang 11 for the coverage check as clang 14 (the default clang version for Ubuntu 22.04) has an unresolved
+# We use clang 13 for the coverage check as clang 14 (the default clang version for Ubuntu 22.04) has an unresolved
 # issue (see https://github.com/llvm/llvm-project/issues/54907).
 path_to_compiler=''
-c_compiler='clang-11'
-cxx_compiler='clang++-11'
+c_compiler='clang-13'
+cxx_compiler='clang++-13'
 
 unamestr=$(uname)
 if [[ "$unamestr" == 'Darwin' ]]; then
    # Use homebrew clang for OS X
-   path_to_compiler="$(brew --prefix llvm@11)/bin/"
+   path_to_compiler="$(brew --prefix llvm@13)/bin/"
    c_compiler='clang'
    cxx_compiler='clang++'
 fi

@@ -591,6 +591,7 @@ set(
     utils/assert.hpp
     utils/check_table_equal.cpp
     utils/check_table_equal.hpp
+    utils/comparator_concepts.hpp
     utils/copyable_atomic.hpp
     utils/date_time_utils.cpp
     utils/date_time_utils.hpp
@@ -655,6 +656,8 @@ set(
     utils/settings_manager.hpp
     utils/singleton.hpp
     utils/size_estimation_utils.hpp
+    utils/small_min_heap.hpp
+    utils/sort_utils.hpp
     utils/sqlite_add_indices.cpp
     utils/sqlite_add_indices.hpp
     utils/sqlite_wrapper.cpp

@@ -0,0 +1,20 @@
+#pragma once
+
+#include <compare>
+#include <type_traits>
+
+namespace hyrise {
+
+template <typename Comparator, typename T>
+concept BooleanComparator = requires(Comparator comparator, const T& lhs, const T& rhs) {
+                              { comparator(lhs, rhs) } -> std::same_as<bool>;
+                              // NOLINTNEXTLINE(readability/braces)
+                            };
+
+template <typename Comparator, typename T>
+concept ThreeWayComparator = requires(Comparator comparator, const T& lhs, const T& rhs) {
+                               { comparator(lhs, rhs) } -> std::convertible_to<std::partial_ordering>;
+                               // NOLINTNEXTLINE(readability/braces)
+                             };
+
+}  // namespace hyrise
@@ -0,0 +1,76 @@
+#pragma once
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <functional>
+#include <ranges>  // NOLINT(build/include_order)
+#include <span>    // NOLINT(build/include_order)
+
+#include "assert.hpp"
+#include "comparator_concepts.hpp"
+
+namespace hyrise {
+
+// Min-Heap optimized for small number of elements that are cheap to move around. Instead of using a complicated layout,
+// the elements of the heap are stored in order in an array and moved back and forth in linear time.
+template <uint8_t max_size, typename T, BooleanComparator<T> Compare = std::less<T>>
+class SmallMinHeap {
+ public:
+  // Constructs a `SmallMinHeap` from a range of initial elements.
+  template <typename R>
+    requires std::ranges::input_range<R> && std::ranges::sized_range<R>
+  explicit SmallMinHeap(R&& initial_elements, Compare init_compare = {}) : _compare(std::move(init_compare)) {
+    const auto size = std::ranges::size(initial_elements);
+    Assert(size <= max_size, "SmallMinHeap got more than max_size initial elements.");
+    _size = static_cast<uint8_t>(size);
+    std::ranges::move(initial_elements, _elements.begin());
+    std::ranges::sort(std::span(_elements).subspan(0, _size), _compare);
+  }
+
+  // Constructs an empty `SmallMinHeap`.
+  explicit SmallMinHeap(Compare init_compare = {}) : SmallMinHeap(std::array<T, 0>{}, std::move(init_compare)) {}
+
+  // Returns the number of elements. Runs in constant time.
+  uint8_t size() const {
+    return _size;
+  }
+
+  // Returns true, if the heap contains any elements. Runs in constant time.
+  bool empty() const {
+    return size() == 0;
+  }
+
+  // Adds an element to the heap. Uses `O(size())` many moves of `T` and `O(log(size()))` many calls to `compare`.
+  void push(T element) {
+    DebugAssert(size() < max_size, "Pushed into already full SmallMinHeap");
+
+    const auto insertion_point =
+        std::ranges::partition_point(_elements.begin(), _elements.begin() + _size,
+                                     [&](const auto& contained) { return !_compare(element, contained); });
+    std::ranges::move_backward(insertion_point, _elements.begin() + _size, _elements.begin() + _size + 1);
+    *insertion_point = std::move(element);
+    ++_size;
+  }
+
+  // Returns the minimal element according to `compare`. Runs in constant time.
+  const T& top() const {
+    return _elements.front();
+  }
+
+  // Removes and returns the top element (see `top()`). Uses `O(size())` many moves of `T`.
+  T pop() {
+    DebugAssert(size() > 0, "Popped from empty SmallMinHeap");
+    auto result = std::move(_elements.front());
+    std::ranges::move(_elements.begin() + 1, _elements.begin() + _size, _elements.begin());
+    --_size;
+    return result;
+  }
+
+ private:
+  std::array<T, max_size> _elements;
+  Compare _compare;
+  uint8_t _size;
+};
+
+}  // namespace hyrise