Metadata-Version: 2.4
Name: PostBOUND
Version: 0.22.0
Summary: PostBOUND is a research framework to prototype and benchmark database query optimizers
Author-email: Rico Bergmann <rico.bergmann1@tu-dresden.de>
License-Expression: Apache-2.0
Project-URL: Homepage, https://github.com/Optimizer-Playground/PostBOUND
Classifier: Programming Language :: Python :: 3
Classifier: Intended Audience :: Science/Research
Classifier: Topic :: Database :: Database Engines/Servers
Classifier: Topic :: Scientific/Engineering
Classifier: Operating System :: OS Independent
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE.txt
Requires-Dist: lazy-loader~=0.4
Requires-Dist: levenshtein~=0.27
Requires-Dist: natsort~=8.4
Requires-Dist: networkx~=3.5
Requires-Dist: numpy~=2.3
Requires-Dist: pandas~=2.3
Requires-Dist: pglast~=7.10
Requires-Dist: psycopg[binary]~=3.2
Requires-Dist: quacklab~=1.5
Requires-Dist: tqdm~=4.67
Provides-Extra: vis
Requires-Dist: matplotlib~=3.10; extra == "vis"
Requires-Dist: seaborn~=0.13; extra == "vis"
Requires-Dist: graphviz~=0.21; extra == "vis"
Provides-Extra: mysql
Requires-Dist: mysql-connector-python~=9.5; extra == "mysql"
Dynamic: license-file

# PostBOUND

![GitHub License](https://img.shields.io/github/license/Optimizer-Playground/PostBOUND)
![GitHub Release](https://img.shields.io/github/v/release/Optimizer-Playground/PostBOUND?color=blue)

<p align="center">
    <img src="https://raw.githubusercontent.com/Optimizer-Playground/PostBOUND/refs/heads/main/docs/figures/postbound-logo.svg" style="width: 150px; margin: 15px;" alt="PostBOUND logo">
</p>

PostBOUND is a Python framework for studying query optimization in database systems.
At a high level, PostBOUND has the following goals and features:

- 🏃‍♀️ **Rapid prototyping:** PostBOUND allows researchers to implement specific phases of the optimization process, such
  as the cardinality estimator or the join order optimization. Researchers can focus precisely on the parts that they are
  studying and use _reasonable_ defaults for the rest. See [🧑‍🏫 Example](#-example) for how this looks in practice.
- 🧰 **No boilerplate:** to ease the implementation of the optimizers, PostBOUND provides a large toolbox of
  support functionality, such as query parsing, join graph construction, relational algebra or database statistics.
- 📊 **Transparent benchmarks:** once a new optimizer prototype is completed, the benchmarking tools allow to compare this
  prototype against other optimization strategies in a transparent and reproducible way. As a core design principle,
  PostBOUND executes queries on an actual database system such as PostgreSQL, or DuckDB, rather than research systems or
  artificial "lab" comparisons. See [💡 Essentials](#-essentials) for more information on this.
- 🔋 **Batteries included:** in addition to the Python package, PostBOUND provides a lot of utilities to setup databases
  and load commonly used benchmarks (e.g., JOB, Stats and Stack).

| **[💻 Installation](https://postbound.readthedocs.io/en/latest/setup.html)**
| **[📖 Documentation](https://postbound.readthedocs.io/en/latest/)**
| **[🧑‍🏫 Examples](https://github.com/Optimizer-Playground/PostBOUND/tree/main/examples)** |

## ⚡️ Quick Start

An installation of PostBOUND consists of two parts: the PostBOUND framework itself, as well as a running database instance
(such as PostgreSQL or DuckDB) that is used to actually execute the optimized queries (see [💡 Essentials](#-essentials)
below).

The easiest way to install PostBOUND is via pip or [uv](https://docs.astral.sh/uv/):

```sh
pip install postbound
```

Once installed, check out the [10 minutes to PostBOUND](https://postbound.readthedocs.io/en/latest/10minutes.html) guide.

If you prefer a more integrated setup, we provide a Docker image that contains PostBOUND as well as a readily-configured
Postgres server or DuckDB installation.
The [documentation](https://postbound.readthedocs.io/en/latest/setup.html) provides more details on setup options.

## 💡 Essentials

As a central design decision, PostBOUND is not integrated into a specific database system.
Instead, it is implemented as a Python framework operating on top of a running database instance.
In the end, all query plans generated by PostBOUND should be executed on a real-world database system.
This decision was made to ensure that the optimization strategies are actually useful in practice and we treat the execution
time as the ultimate measure of optimization quality.

However, this decision means that we need a way to ensure that the optimization decisions made within the framework are
actually used when executing the query in the context of the target database.
This is achieved by using query hints which typically encode the optimization decisions in comment blocks within the query.

In the case of Postgres, this interaction roughly looks like this:

<p align="center">
  <img src="https://raw.githubusercontent.com/Optimizer-Playground/PostBOUND/refs/heads/main/docs/figures/postbound-pg-interaction.svg" style="width: 600px; margin: 15px;">
</p>

Users implement their optimization strategies in terms of
[optimization pipelines](https://postbound.readthedocs.io/en/latest/core/optimization.html).
For an incoming SQL query, the pipeline computes an abstract representation of the resulting query plan without user
intervention.
This plan is automatically converted into equivalent hints for the target database system such as Postgres or DuckDB.
Afterwards, the hints ensure that the database system executes the query plan that was originally computed in the optimization
pipeline.

Depending on the actual database system, the hints might differ in syntax as well as semantics.
Generally speaking, PostBOUND figures out which hints to use on its own, without user intervention.
In the case of PostgreSQL, PostBOUND relies on either [pg_hint_plan](https://github.com/ossc-db/pg_hint_plan) or
[pg_lab](https://github.com/rbergm/pg_lab) to provide the necessary hinting functionality when targeting Postgres.
For DuckDB, PostBOUND uses [quacklab](https://github.com/rbergm/quacklab) hints to guide the optimizer.

> [!NOTE]
> PostBOUND's database interaction is designed to be independent of a specific system (such as PostgreSQL, Oracle, ...).
> However, the current implementation is most complete for PostgreSQL and DuckDB with limited support for MySQL.
> This is due to practical reasons, mostly our own time budget and the popularity of the two systems in the optimizer research
> community.

## 🧑‍🏫 Example

The typical end-to-end workflow using PostBOUND looks like this:

1. **Implement your new optimization strategy**. To do so, you need to figure out which parts of the optimization process you
   want to customize and what the most appropriate optimization pipeline is. In a nutshell, the optimization pipeline is
   a mental model of how the optimizer works. Commonly used pipelines are the textbook-style pipeline (i.e. using plan
   enumerator, cost model and cardinality estimator), or the multi-stage pipeline which first computes a join order and
   afterwards selects the best physical operators. The pipeline determines which interfaces can be implemented.
2. Select your **target database system** and **benchmark** that should be used for the evaluation.
3. Optionally, select different optimization strategies that you want to compare against.
4. Use the **benchmarking tools** to execute the workload against the target database system.

For example, a random join order optimizer could be implemented like this:

```python
import random

import postbound as pb


# Step 1: define our optimization strategy.
# In this example we develop a simple join order optimizer that
# selects a linear join order at random.
# In order to do so, we implement the JoinOrdering interface, which
# requires us to provide an optimize_join_order() method.
class RandomJoinOrder(pb.JoinOrdering):
    def optimize_join_order(self, query: pb.SqlQuery) -> pb.JoinTree:
        if not pb.qal.is_select_query(query):
            raise pb.OptimizationError("Expected a SELECT query")

        initial_table, *free_tables = random.sample(
            list(query.tables()), k=len(query.tables())
        )
        join_tree = pb.JoinTree(base_table=initial_table)

        while free_tables:
            candidates = [
                table for table in free_tables
                if query.joins_between(table, join_tree.tables())
            ]
            next_table = random.choice(candidates)
            join_tree = join_tree.join_with(next_table)
            free_tables.remove(next_table)

        return join_tree


# Step 2: connect to the target database, load the workload and
# setup the optimization pipeline.
# In our case, we evaluate the Stats workload on Postgres
pg_stats = pb.postgres.connect(config_file=".psycopg_connection_stats")
stats = pb.workloads.stats()

optimization_pipeline = (
    pb.MultiStageOptimizationPipeline(pg_stats)
    .use(RandomJoinOrder())
    .build()
)

# (Step 3): in this example we just compare against the native Postgres optimizer
# Therefore, we do not need to setup any additional optimizers.

# Step 4: execute the workload.
# We use the QueryPreparation to prewarm the database buffer and run all
# queries as EXPLAIN ANALYZE.
query_prep = pb.bench.QueryPreparation(
    prewarm=True, analyze=True, preparatory_statements=["SET geqo TO off;"]
)
native_results = pb.bench.execute_workload(
    stats,
    on=pg_stats,
    query_preparation=query_prep,
    workload_repetitions=3,
    progressive_output="stats-results-native.csv",
    logger="tqdm",
)
optimized_results = pb.bench.execute_workload(
    stats,
    on=optimization_pipeline,
    query_preparation=query_prep,
    workload_repetitions=3,
    progressive_output="stats-results-optimized.csv",
    logger="tqdm",
)

```

## 🤬 Issues

Something feels wrong or broken, or a part of PostBOUND is poorly documented or otherwise unclear?
Please don't hestitate to file an issue or open a pull request!
PostBOUND is not one-off software, but an ongoing research project.
We are always happy to improve both PostBOUND and its documentation and we feel that the user experience (specifically,
_your_ user experience) is a very important part of this.

## 📖 Documentation

A detailed documentation of PostBOUND is available [here](https://postbound.readthedocs.io/en/latest/).

## 🛠️ Contributing

PostBOUND is developed with [uv](https://docs.astral.sh/uv/). To get set up:

```sh
uv sync --dev               # creates .venv with the package, all extras and the dev tools
uv run pre-commit install   # enables the formatting/linting/type-checking git hooks
```

Formatting (`ruff format`), linting (`ruff check`) and type checking (`ty`) are enforced on every
commit and configured in `pyproject.toml`, so your editor and the hooks always agree.
See [CONTRIBUTING.md](CONTRIBUTING.md) for the details.

## 📑 Repo Structure

The repository is structured as follows.
The `postbound` directory contains the actual source code, all other folders are concerned with "supporting" aspects
(which are nevertheless important..).
Almost all of the subdirectories contain further READMEs that explain their purpose and structure in more detail.

| Folder       | Description                                                                                                                                                                      |
| ------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `postbound`  | Contains the source code of the PostBOUND framework                                                                                                                              |
| `docs`       | contains the high-level documentation as well as infrastructure to export the source code documentation                                                                          |
| `examples`   | contains general examples for typical usage scenarios. These should be run from the root directory, e.g. as `python3 -m examples.example-01-basic-workflow`                      |
| `tests`      | contains the unit tests and integration tests for the framework implementatino. These should also be run from the root directory, e.g. as `python3 -m unittest tests`            |
| `db-support` | Contains utilities to setup instances of the respective database systems and contain system-specific scripts to import popular benchmarks for them                               |
| `workloads`  | Contains the raw SQL queries of some popular benchmarks                                                                                                                          |
| `tools`      | Provides different other utilities that are not directly concerned with specific database systems, but rather with common problems encoutered when benchmarking query optimizers |

## 🫶 Reference

If you find our work useful, please cite the following paper:

```bibtex
@inproceedings{bergmann2025elephant,
  author       = {Rico Bergmann and
                  Claudio Hartmann and
                  Dirk Habich and
                  Wolfgang Lehner},
  title        = {An Elephant Under the Microscope: Analyzing the Interaction of Optimizer
                  Components in PostgreSQL},
  journal      = {Proc. {ACM} Manag. Data},
  volume       = {3},
  number       = {1},
  pages        = {9:1--9:28},
  year         = {2025},
  url          = {https://doi.org/10.1145/3709659},
  doi          = {10.1145/3709659},
  timestamp    = {Tue, 01 Apr 2025 19:03:19 +0200},
  biburl       = {https://dblp.org/rec/journals/pacmmod/BergmannHHL25.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}
```
