Window Function Optimization: Co-Evaluation and Other Techniques

This repository contains an adapted version of DuckDB with predicate Co-Evaluation for window functions. There are adaptations in multiple places:

• Co-Evaluation with Early Stop: window_rank_function.cpp
• Merge Pruning: sorted_run_merger.cpp
• (Adaptive) Partition Pruning: hashed_sort.cpp

Reproducibility

• Build

  git submodule update --init --recursive
  COMMON_CMAKE_VARS="-DCMAKE_C_COMPILER=<your_c_compiler> -DCMAKE_CXX_COMPILER=<your_cxx_compiler>" \
      DISABLE_SANITIZER=1 DISABLE_VPTR_SANITIZER=1 GEN=ninja make release
  cd evaluation
  mkdir -p build
  cd build
  cmake .. -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=<your_c_compiler> \
      -DCMAKE_CXX_COMPILER=<your_cxx_compiler> -GNinja
  cmake --build .
  cd ../..

• Dependencies

  cmake ninja-build golang python3 texlive texlive-fonts-extra

WF+ Operator

• Data generation

  ./evaluation/scripts/generate_data.sh

• Run the microbenchmarks

  ./evaluation/scripts/run_experiments.sh

  The result data is located in evaluation/experiments. If you run on a multi-socket machine, consider execution within a Docker container to restrict to a NUMA region:

    docker --run -v "$(pwd)":"$(pwd)" --cpuset-cpus <region CPUs> --cpuset-mems <region ID> -it ubuntu:24.04

• Plot

  ./evaluation/scripts/create_plots.sh

  The plots are located in evaluation/figures.

Equivalences

Benchmarks for the equivalence classes are provided on the benchmark-equivalences branch, which runs on unmodified DuckDB code.

git checkout benchmark-equivalences

• Build

  cmake --build build/release --config Release
  cmake --build evaluation/build --config Release

• Data generation

  ./evaluation/scripts/create_equivalence_data.sh

• Run the equivalence benchmarks

  cd evaluation
  ./build/benchmark_equivalences -t 30
  cd ..

• Plot

  cd evaluation
  python3 ./scripts/plot_equivalences.py
  cd ..