PostgreSQL GPU Query Optimization
=====================================

This repository contains the implementation of the new join order optimization 
algorithms described in the paper "Efficient Massively Parallel Join 
Optimization for Large Queries".
It contains:
 - source code for the novel MPDP algorithm, both CPU and GPU
 - source code for the CPU and GPU baseline algorithms (dpsize, dpsub, dpccp, 
   dpe, gpu-dpsize, gpu-dpsub)
 - source code of other experimental algorithms (e.g. dpsub-csg)
 - scripts used for running the tests, creating the synthetic databases, 
   generating the data to plot (inside the misc/ folder)

Documentation details:
---------------------------------------------
1. Read Documentation under DOCS.md
2. Download Dataset generation scripts and queries: https://drive.google.com/file/d/1_iCxt1H0yIIcBDCMcobiPyyQ-BH0JduP/view?usp=sharing
  
For more information about the datasets and commands: [Documentation](DOCS.md)
Contact us for access to .dump datasets 

Building with CUDA
-----------------

In order to build with CUDA, you need to specify the path to CUDA to the 
configure scipt and the cuda version to target, e.g.
```
./configure.sh --enable-cuda=/usr/local/cuda --with-cudasm=61
```
In case CUDA is installed in /usr/local/cuda, and the GPU has compute 
capability 6.1 (e.g. GTX 1080Ti).

Then make and make install.


Other build suggestions
----------------------

The bitmapset implementation can use the Intel bit operation extension, if 
compiled using 
```
CFLAGS="-march=native -mtune=native" CPPFLAGS="-march=native -mtune=native"
```

Timing information can be printed to stdout for gpuqo algorithms setting 
enable_gpuqo_profiling=yes in make:
```
make enable_gpuqo_profiling=yes
```

Other useful make variables:
 - enable_debug=[yes/no]: enable debugging symbols generation
 - cost_function=[cout/simple/postgres]: choose cost function used by gpuqo
   algorithms: cout (C_out), simple (join-order-benchmark paper, with the 
   addition of sort-merge joins), postgres (returns the same cost as 
   Postgres but only supports a limited set of queries)
 - simulate_complex_cost_function=[yes/no]: add overhead to the cost function
 - disable_ccc=[yes/no]: globally disables CCC (warp divergence avoidance 
   method). The gpuqo_dpsub algorithm can be run without ccc at runtime (no 
   need to set this option).

Usage
-----

Configuration:

The following settings can be set in Postgres to use the gpuqo module and 
choose the algorithm and its parameters:
 + GeQo (genetic optimizer):
   - geqo: enable/disable geqo
   - geqo_threshold: number of tables to start using geqo
 + GPU-QO:
   - gpuqo: enable/disable gpuqo module
   - gpuqo_threshold: number of tables to start using gpuqo (set to 2 to always 
                      use it)
   - gpuqo_algorithm: one of:
     * cpu_dpsize:      DPsize on CPU (sequential)
     * cpu_dpsub:       DPsub on CPU (sequential)
     * cpu_dpsub_bicc:  MP-DP (aka DPsub w/ BiConnected Component optimization)
                        on CPU (sequential)
     * cpu_dpccp:       DPccp on CPU (sequential)
     * dpe_dpsize:      DPsize on CPU (parallel) using DPE.
     * dpe_dpsub:       DPsub on CPU (parallel) using DPE.
     * dpe_dpccp:       DPccp on CPU (parallel) using DPE.
     * parallel_cpu_dpsub: DPsub on CPU (parallel) using DPsub-specific 
                           parallelization.
     * parallel_cpu_dpsub_bicc: MP-DP on CPU (parallel) using DPsub-specific 
                                parallelization.
     * dpsize:          DPsize on GPU. See "dpsize\ options" below
     * dpsub:           DPsub on GPU. See "dpsub options" below
   - GPU options:
     * gpuqo_min_memo_size_mb: set (lowerbound) for starting size of memo in MB
     * gpuqo_max_memo_size_mb: set max size of memo hashtable in MB.
                               The memo grows by powers of 2 (of elements).
     * gpuqo_n_parallel: number of items to execute at a time. Set this value 
                         depending on your GPU.
                         Heuristically, this should be set in such a way that 
                         all GPU threads are kept busy, therefore a good value 
                         could be "maximum number of threads per multiprocessor"
                         times "number of multiprocessors".
                         TODO: set it automatically. 
     * gpuqo_scratchpad_size_mb: size of temporary memory location used to store 
                                 intermediate sets. Should be big enough to fit
                                 gpuqo_n_parallel sets.
   - dpsub options (GPU):
     * gpuqo_dpsub_bicc: use MPDP instead of plain dpsub
     * gpuqo_dpsub_csg: (experimental) use csg enumeration
     * gpuqo_dpsub_csg_threshold: (experimental) threshold to start using csg
     * gpuqo_dpsub_tree: (experimental) if set is a tree, use MPDP tree variant 
                         instead of generic one.
   - dpsub advanced options (GPU):
     * gpuqo_dpsub_filter: enable filtering of invalid unranked sets (default: on).
     * gpuqo_dpsub_filter_threshold: minimum number of sets to unrank to use 
                                     filtering (default: 0).
     * gpuqo_dpsub_filter_cpu_enum_threshold: if number of sets is lower than 
                                              this threshold, do filtering on 
                                              CPU.
     * gpuqo_dpsub_filter_keys_overprovisioning: number of sets to unrank at a 
                                                 time as multiple of scratchpad
                                                 size.          
     * gpuqo_dpsub_ccc: enable CCC warp-divergence prevention algorithm (only 
                        works on plain DPsub) (default: on).
   - parallel CPU options:
    * gpuqo_dpe_n_threads: number of threads to use (both dpe_* and parallel_*).
    * gpuqo_cpu_dpsub_parallel_chunk_size: number of sets to unrank at a time 
                                           per worker in DPSUB parallel variant.
   - IDP options:
     * gpuqo_idp_type: IDP1 or IDP2 or IDPMAG or DPDP or UNION_DPDP
     * gpuqo_idp_n_iters: k parameter for IDP, 0 to disable

Example:
running IDP2 with MPDP (GPU) using k = 25:
"""
# to be sure to use gpuqo, disable geqo and set gpuqo threshold to 2
SET geqo TO off; 
SET geqo_threshold TO 2;

# select gpuqo algorithm
SET gpuqo_algorithm TO dpsub;
SET gpuqo_dpsub_bicc TO on;

# make sure other dpsub features are to default values
SET gpuqo_dpsub_filter TO on;
SET gpuqo_dpsub_filter_threshold TO 0;
SET gpuqo_dpsub_csg TO off;
SET gpuqo_dpsub_tree TO off;

# enable IDP
SET gpuqo_idp_type TO 2;
SET gpuqo_idp_n_iters TO 25;

SELECT * FROM ...;
"""

These settings can be set to the best predefined values using the 
run_all_generic.sh script inside misc/analysis/.
The script can be used to run tests on multiple queries.
Example (same as above with ):
"""
idp_type=IDP2 idp_n_iters=25 \
    run_all_generic.sh gpuqo_bicc_dpsub \
    snowflake user \
    60 \
    warmup.sql \ 
    queries/*.sql
"""
Note: the warmup query is called before each query to prevent measuring one-time
overheads of the CUDA driver.
In bash, you can specify also <(echo "SELECT 1;") if you don't want to specify a
query.
   
Limitations
-----------

The current "postgres" cost function implemented in GPU-QO supports only certain
types of joins. It is equivalent to Postgres internal cost function when 
Postgres is run with the following options:

"""
SET enable_seqscan TO on; 
SET enable_indexscan TO on; 
SET enable_indexonlyscan TO off; 
SET enable_tidscan TO off; 
SET enable_mergejoin TO off; 
SET enable_parallel_hash TO off; 
SET enable_bitmapscan TO off; 
SET enable_gathermerge TO off; 
SET enable_partitionwise_join TO off; 
SET enable_material TO off; 
SET enable_hashjoin TO on; 
SET enable_nestloop TO on;
"""

Furthemore, it has only been tested in simple queries of the form:
SELECT * FROM A, B, C WHERE A.col1 = B.col3 AND ...;

Code Structure
--------------

Notes on the code:
a lot of templates are being used in the code to compile the best CUDA code 
for different cases (different bitset sizes and so on).

All gpuqo algorithms are inside src/backend/optimizer/gpuqo/
 - gpuqo_main.c: entry point for the gpuqo module. This file performs all the 
                 glueing with Postgres, like extracting information from the 
                 planner and building the query plan.
 - gpuqo_main_internal.cu: entry point for the C++/CUDA part of the gpuqo module,
                           it is just a proxy to the correct function to be 
                           called. It also performs the conversion from Postgres
                           data structures to GPU-friendly datastructures 
                           (GpuqoPlannerInfo<...>, QueryTree<...>).
 - gpuqo_remapper.cu, gpuqo_remapper.cuh:
    Utility for remapping indexes and creating temporary compound tables to be 
    used in IDP.
 - gpuqo_bfs_indexing.cu:
    Generate a remapper to relabel tables with a BFS-consistent order.
 - gpuqo_spanning_tree.cu
    Compute the spanning tree of a graph. Used in tree mode.
 - gpuqo_bit_manipulation.cuh
    Low-level bit manipulation 
 - gpuqo_bitmapset.cuh
    GPU-efficient bitmapset implementation (32 or 64 bits)
 - gpuqo_bitmapset_dynamic.cuh
    dynamic bitmapset implementation for CPU based on Postgres bitmapset.
    NB: much slower than static bitmapset.
 - gpuqo_cost*:
    Cost functions
 - gpuqo_row_estimation.cuh
    Row estimation of a join
 - gpuqo_binomial.cu, gpuqo_binomial.cuh:
    Binomial coefficient pre-calculation for dpsub unranking.
 - gpuqo_cpu_*:
    Implementation of CPU algorithm. There are some common abstract classes that
    are implemented by the different algorithms so that they could be used in 
    sequential and DPE mode using a common code.
 - gpuqo_cpu_level_hashtable.cuh:
    Memo table where there is one hashtable for each set size, used in parallel 
    MPDP (CPU).
 - gpuqo_dependency_buffer.cu, gpuqo_dependency_buffer.cuh:
    Dependency-aware datastructure used by DPE.
 - gpuqo_dpsize.cu:
    dpsize (GPU)
 - gpuqo_dpsub*:
    dpsub (GPU). There is a common code and then specific enumeration algorithms
    (plain, mpdp aka bicc, csg, tree).
    Code for filtered and unfiltered is divided.
 - gpuqo_filter.cuh:
    Utilities for filtering invalid sets (functions, unary functors, ...).
 - gpuqo_hashtable.cu, gpuqo_hashtable.cuh:
    Simple GPU hashtable using open addressing
 - gpuqo_idp.cu
    IDP1 and IDP2 implementation
 - gpuqo_planner_info.cu, gpuqo_planner_info.cuh:
    Utilities for converting planner info between different sizes
 - gpuqo_postgres.cuh:
    Import some useful macros from postgres
 - gpuqo_query_tree.cuh
    Utilities for converting query trees.
 - gpuqo_debug.cu, gpuqo_debug.cuh, gpuqo_timing.cuh:
    Debugging and profiling macros
 - gpuqo_uninitalloc.cuh
    Thrust vector without initialization

Miscellaneous scripts and files are inside misc/

________________________________________________________________________________

Below is the original README.

PostgreSQL Database Management System
=====================================

This directory contains the source code distribution of the PostgreSQL
database management system.

PostgreSQL is an advanced object-relational database management system
that supports an extended subset of the SQL standard, including
transactions, foreign keys, subqueries, triggers, user-defined types
and functions.  This distribution also contains C language bindings.

PostgreSQL has many language interfaces, many of which are listed here:

	https://www.postgresql.org/download

See the file INSTALL for instructions on how to build and install
PostgreSQL.  That file also lists supported operating systems and
hardware platforms and contains information regarding any other
software packages that are required to build or run the PostgreSQL
system.  Copyright and license information can be found in the
file COPYRIGHT.  A comprehensive documentation set is included in this
distribution; it can be read as described in the installation
instructions.

The latest version of this software may be obtained at
https://www.postgresql.org/download/.  For more information look at our
web site located at https://www.postgresql.org/.