AQO - PostgreSQL Adaptive Query Optimization

When performing queries, modern DBMSs use the cost optimization model - based on the coefficients stored in the configuration files and the collected statistics, they calculate the “price” of receipt and the volume of the resulting row sets. When queries are run again, cost and selectivity are recalculated. You can run a query and see the real values ​​of these parameters, however, the DBMS optimizer does not use this information during (standard) rescheduling.



But what if the optimizer saved the real values ​​of cost, selectivity and other necessary parameters of the query execution and, when it is executed again, it was guided not only by the standard collected statistics, but also by those saved after the previous execution?



This is called adaptive query optimization and is promising. Some DBMSs already use such technologies.



Company Postgres Professional for several years working on AQO extension for PostgreSQL, which implements (in some form) adaptive optimization. Work is still underway, but there is already something to test.



First, let's take a closer look at the subject area of ​​query optimization.

Why the planner might choose a suboptimal plan

The SQL query can be executed in different ways. For example, when there is a join of two tables, it can be done in several different ways - using nested loops, merging, hashing. The more tables involved in the query, the more variations of their joins. The task of the planner is to choose the execution plan of the query with the lowest cost from many variations.



As already mentioned, during their work, the planners of many DBMSs use statistical information collected either automatically or manually. The planner calculates an estimated cost based on these statistics.



In general, modern DBMS schedulers work well in most situations. However, in some cases, the chosen plan may be very far from optimal.



For example,the lack of relevant statistical information leads to the fact that the planner focuses on (most likely) incorrect data on the number of rows in the joined tables. Excessive underestimation (or overestimation) of cardinality leads to the choice of non-optimal methods for accessing data in tables.



Another important reason may be the lack of necessary indexes . In the absence of indexes, the scheduler has a limited choice of data access methods.



Using dependent (correlated) conditionscan also negatively affect the operation of the DBMS. The scheduler (by default) considers that all conditions in the request are independent of each other, that is, the value of one condition does not affect the other in any way. This is not always the case. If dependent conditions are used (for example, zip code and city), the scheduler will also calculate the wrong cost and cardinality of the connections.



The scheduler may also be affected by the use of functions in the environment . The function for the scheduler is a “black box”, he does not know how many lines the function will return, which can also lead to an erroneous cost of the plan.

Ways to influence the scheduler

Up-to-date statistics are an indispensable condition for the adequate work of the scheduler. First of all, make sure that the system is configured to regularly collect statistical information.

There are several ways to fix the above situations and to help the planner choose more optimal query execution plans.



Without indexes, the scheduler has only one way to obtain data - sequential table scanning (and this is not always bad and expensive). In some cases, creating the necessary indexes helps to speed up access to data - no need to scan the entire table. But the use of indexes (the search for the necessary, the creation, maintenance) is not free. Ideally, they should be used exactly where they are needed. And where not needed - do not use.



Using correlated connection conditions in queries, you can generate advanced statistics- explicitly “prompt” the optimizer that the conditions are related to each other. To do this, the database administrator (or developer) needs to know his data well and monitor the dependent conditions in queries, since it is difficult to predict the number of combinations of dependent columns in advance. Advanced statistics will have to be created manually for each such option.



When creating a function, you can specify an approximate cost of execution and / or an estimate of the number of lines produced by the function. In version 12 , it became possible to use auxiliary functions to improve scheduler estimates depending on the arguments. This is also a manual way, which does not always give an optimal result.



If all else fails, you can manually rewrite the query, for example, using materialized views, Common Table Expressions (CTE). Or to clarify the requirements of the subject area and, possibly, radically rewrite the logic of the request.



And there is another way of “hints” to the scheduler - adaptive query optimization ( a daptive q uery o ptimization). The idea of ​​this method is that after the query is executed, real statistical information is saved and, when the given (or similar) query is repeated, the optimizer can rely on it.



The DBMS Postgres Pro Enterprise is an extension for adaptive query optimization called AQO... This extension is posted on the github: github.com/postgrespro/aqo , it can also be tried with vanilla PostgreSQL, more on that below.

The principle of operation of the module

The AQO module uses machine learning in its work. You can read more about the principle of operation in an article by Oleg Ivanov Using machine learning to increase PostgreSQL productivity and in more detail in the presentation Adaptive query optimization (report on YouTube ).



The essence of this method is briefly described below:



To estimate the cost, the planner needs an estimate of cardinality, and for this, in turn, an estimate of the selectivity of conditions is needed.



For simple conditions (such as "attribute = constant" or "attribute> constant"), the planner has a model by which it estimates selectivity. To do this, he uses statistical information: the number of unique attribute values, histograms, etc.

For conditions that are made up of simple elements using logical connectives, the scheduler applies easily calculated formulas:

• sel (not A) = 1 - sel (A)
• sel (not A) = 1 - sel (A)
• sel (A and B) = sel (A) * sel (B)
• sel (A or B) = sel (not (not A and not B)) = 1 - (1 - sel (A)) * (1 - sel (B))

These formulas assume the independence (uncorrelatedness) of conditions A and B, which is why we get incorrect estimates in the case when this assumption is violated.

AQO complicates the formula: it introduces its own coefficient for each simple condition. Using machine learning (using nearest-neighbor regression), AQO selects these coefficients so that the selectivity calculated by the formula best matches the real selectivity that AQO observed previously.



For this, the module saves:

• , ;
• .

In its work, AQO distinguishes between conditions up to constants. This makes it possible to reduce the complexity of the problem being solved, and besides, in most cases, information is still not lost: AQO does not “see” the value of the constant, but it “sees” the selectivity of the condition.

The situation in which the loss does occur is the conditions that are evaluated as a constant regardless of the specific values. For example, for some conditions, the scheduler cannot make any reasonable estimates and chooses the default constant (for example, the selectivity of the condition “expression1 = expression2” is always evaluated as 0.005, and “expression1> expression2” as 1/3).



Thus, AQO improves the selectivity estimate of complex conditions (and, as a consequence, the cost estimate, which may lead to the choice of a more adequate execution plan).

Installing the module

To try the module's functionality on vanilla PostgreSQL, you need to use a special patch and then build the system from source. Read more in the README file on github.



If Postgres Pro Enterprise is used, the installation of the AQO module will proceed in standard mode:



shared_preload_libraries = 'aqo'



After that, you can create an extension in the required database.

Database Preparation

Let's look at a concrete example of how the AQO module works in a demo database . We will use a large database containing information on flights for the year, from September 2016 to September 2017.



First, let's create an extension:

CREATE EXTENSION aqo;

Next, turn off parallel query processing - so that the display of parallel plans does not distract from the main task:



max_parallel_workers_per_gather = 0;



In order for the PostgreSQL scheduler to have more options for joining tables, we will create two indexes:

CREATE INDEX ON flights (scheduled_departure );
CREATE INDEX ON ticket_flights (fare_conditions );

When analyzing the results, we will focus on the value of BUFFERS as the number of pages that must be read to do the job. We’ll also look at the runtime (but the time on a loaded system and on a home laptop can vary greatly).



Let's increase the buffer cache and work_mem so that all work is done in RAM:



shared_buffers = '256MB';

work_mem = '256MB';

Using AQO Module

Let's form a request: you need to get passengers who flew in business class starting from a certain date, and arrived with a delay of no more than an hour.

Let's execute the query without using AQO (hereinafter, some of the information that does not affect the understanding of the module operation has been removed from the plans):

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF) SELECT t.ticket_no
  FROM flights f
   	JOIN ticket_flights tf ON f.flight_id = tf.flight_id
   	JOIN tickets t ON tf.ticket_no = t.ticket_no
 WHERE f.scheduled_departure > '2017-08-01'::timestamptz
   AND f.actual_arrival < f.scheduled_arrival + interval '1 hour'
   AND tf.fare_conditions = 'Business';

And let's see the resulting plan: In this case, the scheduler considered the optimal plan, in which, first, using a bitmap scan ( ), we get a set of rows from the flights table, which we connect by hashing (a node ) with a set of rows from the ticket_flights table obtained using the index scan ( ). The resulting result will be used as the outer rowset for the final nested loop join (node ). The internal set for this connection is obtained by an exclusive index scan of the tickets ( ) table . The most “voluminous" operation is to obtain an internal rowset for Nested Loop - 106,205 buffers are read on it.



Nested Loop (rows=33210) (actual rows=31677)

  Buffers: shared hit=116830 read=1

  ->  Hash Join (rows=33210) (actual rows=31677)

        Hash Cond: (tf.flight_id = f.flight_id)

        ->  Index Scan ... on ticket_flights tf  

              Index Cond: fare_conditions = 'Business'

        ->  Hash

              ->  Bitmap Heap Scan on flights f (rows=8331) (actual rows=7673)

                    Recheck Cond: scheduled_departure > '2017-08-01'

                    Filter: actual_arrival < scheduled_arrival + '01:00:00'::interval

                    ->  Bitmap Index Scan on ... [flights]

                          Index Cond: scheduled_departure > '2017-08-01'

                          Buffers: shared hit=44 read=1

  ->   Index Only Scan  ... on tickets t (rows=1 width=14) (actual rows=1 loops=31677)

        Index Cond: (ticket_no = tf.ticket_no)

        Buffers: shared hit=106205

 Planning Time: 9.326 ms

 Execution Time: 675.836 ms



Bitmap Heap Scan on flightsHash JoinIndex Scan ... on ticket_flightsNested LoopIndex Only Scan ... on tickets





This plan can be called relatively good, since a relatively small number of rows in an external set are processed by a nested loop join.



Now we’ll conduct an experiment and see how the proposed plan will (or will not) change depending on the change in dates in the request. The dates are selected in such a way as to sequentially increase the range of rows of the Flights table that satisfy the condition, which leads to a planner error in assessing the cardinality of access to this table. In the plan above, you can see that with the first date, the optimizer is almost not mistaken in cardinality ( ). Let us substitute the following dates in the request one by one:Bitmap Heap Scan on flights f (rows=8331) (actual rows=7673)

• 2017-04-01
• 2017-01-01
• 2016-08-01

And let's see the result:





To summarize, without using the AQO module, the planner works as follows:



Let's look at the result again:

With AQO turned on, the scheduler quickly realizes that you need to switch from a nested loop connection and using an index to a hash connection and sequential scanning.

Summarize

Using the AQO module for adaptive query optimization has both advantages and disadvantages.



One of the benefits of using a module is that you don't have to keep track of dependent conditions in queries. In some cases, the speed of query execution can increase. And there are different modes of using the module. For example, you can use AQO to optimize only certain types of queries.



Among the shortcomings of the module, we can distinguish additional overhead costs for training and storing statistics in the module structures. And the statistical information collected by the module is not transmitted to replicas.



The AQO module is not a silver bullet against all possible scheduling problems. For example, in some situations, the module can replace extended statistics (if it is not created by hand), or will not pay attention to irrelevant statistics. But the module will not create the necessary indexes and, moreover, will not rewrite the query text.



Therefore, you should not enable the module for all requests. Ideal candidates for optimization for AQO are queries, where the error of the scheduler in calculating the cardinality of nodes leads to the choice of a bad plan. And, for some reason, it is not possible to influence the refinement of this estimate.