Google-Capstone

Setup

1. Clone TPC-H tools:

If cmake is not installed (Mac): brew install cmake

git clone [https://github.com/eyalroz/tpch-dbgen.git](https://github.com/eyalroz/tpch-dbgen.git)
cd tpch-dbgen && cmake -B build && cmake --build build
cd ..
cp tpch-dbgen/build/dbgen tpch-dbgen/.

If you get a subprocess error in notebook run this:

cp tpch-dbgen/build/dbgen .
./dbgen -f -s 0.1

2. Postgre setup (MAC)

brew install postgresql
brew services start postgresql
psql -h localhost -p 5432 -d postgres -c "CREATE DATABASE tpch_capstone;"

3. System prerequisites for Python PostgreSQL driver (psycopg2)

Install libpq and OpenSSL with Homebrew and expose their paths so psycopg2 can find the runtime libraries:

# install system libraries
brew install libpq openssl@3

# Make lib directories visible to the dynamic loader (current shell)
export PATH="$(brew --prefix libpq)/bin:$PATH"
export DYLD_LIBRARY_PATH="$(brew --prefix libpq)/lib:$(brew --prefix openssl@3)/lib:$DYLD_LIBRARY_PATH"

# Persist for future shells (optional)
echo 'export PATH="$(brew --prefix libpq)/bin:$PATH"' >> ~/.zshrc
echo 'export DYLD_LIBRARY_PATH="$(brew --prefix libpq)/lib:$(brew --prefix openssl@3)/lib:$DYLD_LIBRARY_PATH"' >> ~/.zshrc

Notes:

• You do not need to brew link --force libpq; the env vars above are sufficient and safer.
• Alternative: if you prefer not to install system libs, you can use psycopg2-binary in requirements.txt instead of psycopg2.

4. Install python libraries

pip install -r requirements.txt

5. Run UI

python join_optimizer_ui.py

Overview

This project explores the application of quantum computing to optimize SQL join order selection - a critical problem in database query optimization. We implement and compare quantum algorithms (QAOA and VQE) against classical approaches for determining the most efficient order to execute multi-table joins.

Problem Statement

Join order optimization is an NP-hard problem that becomes exponentially complex as the number of tables increases. For a query joining N tables, there are factorial(N) possible join orders. Traditional databases use heuristics or exhaustive search for small N, but both approaches have limitations:

• Heuristics are fast but may miss optimal solutions
• Exhaustive search guarantees optimality but becomes computationally infeasible beyond ~10 tables

Quantum algorithms offer a promising middle ground: finding near-optimal solutions faster than exhaustive search while potentially outperforming classical heuristics.

Technical Approach

1. Problem Formulation

We formulate join order optimization as a QUBO (Quadratic Unconstrained Binary Optimization) problem:

• Input: Set of relations (tables) and their pairwise join costs
• Variables: Binary indicators for each possible join subset
• Objective: Minimize total join cost while satisfying tree structure constraints
• Output: Valid join tree representing optimal execution order

2. Cost Collection

Join costs are obtained directly from PostgreSQL using EXPLAIN:

# Build join SQL for each relation subset
cost_matrix = collect_costs_from_postgres(
    relations=['orders', 'lineitem', 'customer'],
    joins=[('orders', 'o_custkey', 'customer', 'c_custkey'), ...]
)

3. Quantum Mapping

The QUBO matrix is converted to a quantum Hamiltonian:

• Linear terms (diagonal) → Pauli-Z operators
• Quadratic terms (off-diagonal) → Pauli-ZZ interactions
• Constraints enforced through penalty terms

4. Quantum Algorithms

QAOA (Quantum Approximate Optimization Algorithm)

• Parameterized quantum circuit with alternating problem and mixer Hamiltonians
• Classical optimizer tunes circuit parameters to minimize energy
• Good for finding approximate solutions quickly

VQE (Variational Quantum Eigensolver)

• Uses a customizable ansatz (circuit template)
• Variational approach to find ground state
• More flexible but potentially slower

5. Classical Baselines

• Greedy Heuristic: Iteratively select cheapest valid joins
• Exact Solver: Exhaustive enumeration (feasible for N ≤ 4)

User Interface (UI)

Purpose

An interactive dashboard (join_optimizer_ui.py) that visualizes and compares join order optimization results between classical and quantum algorithms.

Features

• Query Builder – Select tables and join keys interactively
• Algorithm Selector – Run Classical, QAOA, or VQE optimizers
• Visualization Panel – Displays join trees, cost curves, and timing comparisons
• Console Output – Shows PostgreSQL cost fetch logs and optimizer performance

How to Run

python join_optimizer_ui.py

References

• Qiskit Documentation
• Qiskit Algorithms
• PostgreSQL Query Planning

Benchmarks

• TPC-H Benchmark Specification
• Join Order Benchmark (JOB)

---

Contributors

Project Team:

• Shivam Agarwal
• Ruby Jiang
• Vaibhav Agarwal
• Jash Ravani
• Michael Wang
• Jeff Wu

Course Information:

• Course: CS620 - Quantum Computing
• Instructor: Amber Horvath
• Semester: Fall 2025