PostgreSQL Query Optimizer Observability

Typ: Masterarbeit
Betreuer: Jan Nidzwetzki

The Structured Query Language (SQL) is a declarative language. An SQL statement only describes the result of the query and not the exact way how a database management system (DBMS) should calculate the result. Several ways exist to calculate the desired result. Like most relational DBMS, PostgreSQL uses cost-based optimization to determine the best query plan. During query planning, so-called paths are generated that describe one step of the query (e.g., a sequential scan of a base table, an index scan, a hash join, …). These paths are annotated with costs. When the used query plan is chosen, the best path to calculate the query result is selected.

In PostgreSQL, the EXPLAIN keyword can be used to understand which steps are performed to calculate a particular query; instead of the query result, the query plan is returned together with the predicted costs. Unfortunately, there are some situations where the cost estimation is wrong, and the query optimizer has not selected the fastest plan. Unfortunately, the EXPLAIN output does not show which other query plans were considered by PostgreSQL. However, this information might be helpful for database administrators to properly tune the optimizer of the database system for the used hardware.

A related problem exists for extension developers. PostgreSQL can be extended by extensions, which can modify the behavior of the database server by using hooks. Some of these hooks allow it to alter the generated query plan by rewriting the output of the query optimizer. However, to implement proper rewrite logic, the extension developer has to understand which possible query plans are considered by PostgreSQL.

These two examples show that the query optimizer internals are often a black box for administrators and developers. The goal of this thesis is to improve the observability (i.e., expose internals to make software activity understandable) of the query optimizer. The idea is to expose some of the query optimizer internals and show possible ways to calculate a particular query and which costs these ways have (e.g., by rendering a graph with costs annotated edges).

In the first part of the implementation, the PostgreSQL source code should be modified, and the query optimizer should be enhanced to output all possible paths together with the costs. Unfortunately, most paths are freed as soon as PostgreSQL detects that there is a better (cheaper or differently sorted) path. So, no data structure can be used to get this information directly, and this information must be collected during query planning. A starting point is the function add_path(), which accepts or rejects a new path based on the costs and sorting. Afterward, a program (e.g., a Python script) should be developed that consumes this information and generates an understandable output (e.g., an image of a graph that shows
all possible query plans with annotated costs).

The second part of the implementation should focus on the usability of the developed solution. Modifying the PostgreSQL source code restricts the usability of this solution (e.g., it is impossible in many environments to patch and re-compile the PostgreSQL server). So, the information should be collected without patching PostgreSQL. The eBPF framework allows it
to monitor applications, perform actions when a function is called (using an uprobe), and observe the provided parameters. This might be enough to get the information from the query optimizer. However, there are some limitations with uprobes (e.g., the functions have to be visible in the binary). If this approach does not work, other approaches should be explored. For instance, User Statically-Defined Tracing (USDT) points can be defined to expose the needed information in a standardized way. This still requires the patching of the database server, but it opens the solution to a wide range of software that can consume the data.
In addition, PostgreSQL already exposes some of these trace points to export some internals (e.g., LW lock activity).

Research questions:

• What other methods exist to observe the query planner activity? What are the advantages and disadvantages?
• How do other open-source DBMS deal with this problem?
• Can the extracted information be used to improve PostgreSQL's query planner?

This thesis requires skills in C development, python, operating system internals, and
knowledge of database internals.

Literature:

• The eBPF framework of the Linux kernel
• A tool that uses uprobes to observe some parts of the query planning of PostgreSQL
• Another tool that observes PostgreSQL internals using eBPF
• A script that renders graphs based on eBPF events
• Introduction into User Statically-Defined Tracing
• Static Trace Points in PostgreSQL
• The Internals of PostgreSQL - Creating the Plan Tree of a Single-Table Query
• Brendan Gregg. 2019. BPF Performance Tools: Linux System and Application Observability (1st. ed.). Addison-Wesley Professional. - General information about the possible ways of application observability