Helping the Planner Help You: Extended Statistics in PostgreSQL

This talk covers the topic of extended statistics in PostgreSQL and its role in improving query planner performance. The speaker discusses the critical importance of cardinality estimation, explaining how inaccuracies can lead to suboptimal execution plans and slow queries. They present examples of various join types, particularly nested loop joins and hash joins, highlighting how incorrect estimates can significantly affect execution times. The speaker then introduces extended statistics for correlated columns, detailing how to create and analyze these statistics to enhance query planning. They also propose potential improvements for join statistics and discuss alternative approaches for optimizing cardinality estimation, underlining the significance of adapting to modern hardware capabilities.

Um my name is Alex and I'm a Postgress developer at EDB and today I'm going to talk about extended statistics in Postgress SQL and how it helps the planner help you. So the plan for today um is here and I want to say that if anybody has any questions along the way feel free to ask. You don't have to wait until the end. Um so I'm going

to first talk about the importance uh briefly of the cardality in cardality estimation and when and then I'll we'll look at when estimate works and when they don't and then we'll I'll briefly talk about a well I'll talk about a practical approach join statistics that could fix um the estimates when they don't work today And then um finally we'll also briefly talk about some other approaches that

can improve cardality estimation and what I think Postgress should do next. So let's get started. Um I found this code that dates back to um by Guy Loman and he said the root of old evil the Achilles skill of query optimization is the estimation of the size of intermediate results known as cardalities and it's been more than 10 years since someone said this and I today can

still relate to this statement because as the database developer. I see uh lots of time when customer complain about a uh query optimization issue, it was caused by inaccurate cardality estimation which then lead to a suboptimal plan that run the query really slow or consume lots of resources. So I will give a really simple example here where I have uh join join I'm join two I'm join

three tables here. Um the movie keyword table here is the larger one and it serves more like a fact table and then the title and the keyword table are more our smaller uh dimension tables and then in this query there's only one filter predicate on the keyword column um and it has um equality comparison with some uh with three uh constant values which happened to be very

co popular in the other table. Um, so here is the explain analyze result. I'm aware that the explain text is very dense, but I really only want to say three things on this slide. Um, number one is that there is two nest loop joins here. And number two, um, the execution time is,300 plus milliseconds. And uh lastly um I want to point out the bitmap hip scan

node in this plan um which is at the inner side of the inner nest loop join and you can see that the estimate row is 307 rows but the actual rows during execution is 57,594 rows. Um, I'm gonna pause here a little bit and ask if anyone here needs like a quick review on what is nest loop join, what is hash uh hash join? Okay, then anybody

feel fine to just skip this slide for now because you know. >> Okay. Oh, okay. So, okay. Yeah. So um really there are different ways to implement a logical join uh different physical implementations of a logical join. Um two of two of a few popular ones will be nest loop join and hash join. Um so for hash join really what it does is that for each row

for example you're drawing two tables A and B um and really um for nest loop join what is that what what it does is that for each row in A it will look up matches in table B. So it works best when the outer side is smaller meaning you're doing less lookups in the inner side and also when the inner lookup is cheap for example you are

doing a index lookup rather than a sequential um scan. And for hash join um what it does is that it build the hash table on the inner side in this case the B the B table and then for each row in the outer side the A table it it probe the hash table that we built. So a hash ring is best when both sides are large and

it als it is also more compatible with parallel scans. So going back to the plan we just looked at it has two nest loop joints and we see there is two orders of magnitude of um cardality underestimation. So that usually indicate that the plan might not be the best plan and so we can just explore a little bit and see how other plan does. So I set

this guck called enable nestloop jo enable nestl loop to off which disables the nestloop joins and after that I get a plan of two hash joints here and the execution time is reduced to 581 milliseconds. Well you can we only like disabled some certain plans. We did we didn't change any estimates. So the estimate is so wildly off. Um so to summarize what here when the the

planner's estimate for rows um could be really inaccurate in some case in this case and and that leads to the planner to choose a uh two nestloop joins versus in reality if we had we use a plan with two hash joints the execution time would be a lot faster than the default setting. So now that we have an idea of the importance of cardality estimation, I will

then talk about when the estimates work in Postgress and when they don't. So really for single column, single table, single column, usually the selectivity is very accurate. So here is an example of a single predicate. Um the for example this query you have like a wear clause of column smaller than the value and what happens during planning um to decide the selectivity of this particular predicate is

that the planner will look up the existing statistics of this column in the system catalog and um here I have the entry for this column in PG stats view. It has uh the per per the per column statistics of this column. Um it has information such as the the fraction of non values and the number of distinct values, the most common values and their frequencies and the

cost and the histogram bounds that notates the lower and upper bound of uh the equals based histogram buckets of the non non most common values and correlation is something about the physical order of the data. And there's other metrics for fields for range or array types. Um so really for this very simple rare predicate uh we really only need to sum up the frequencies of the most

frequent values. usually is 100 at most. And then and then for the rest since this is a range query, we can leverage the histogram as the histogram buckets as well to sum up the not so frequent values. And then adding the map together, we get a selectivity really close to the actual selectivity. Well, that's the single column. and for multiple columns um by default postgress assumes independence

until told otherwise. So if I have a query like select star from customers where city is Seattle and state is Washington um like we know that almost every Seattle is in Washington but planner doesn't know so it will just multiply the selectivity of these two pic case and we got a a very a much lower estimates in this case. for those kind of cases within a single

table we can actually work with planner and we can create extended statistics for correlated columns. In this case, we can use the create statistics command to create uh statistics on three columns here, the CD, the state and zip from the customer's table and then we analyze this table and after that for the query we had before we will have a much accurate estimates. So here are some

different types of extended statistics the planner use. um it has functional dependencies. It captures the correlation between columns in the same table. In this example, pretty much we these three columns we pretty much are going to get a uh the parameter very close to one uh which means four dependence and we can the planner also keep track of the most common value list of different combinations of

the column pairs. And whenever there's a multicolumn wear clause, usually the planner would first look up the most common value match from this combination of columns and then um and then also look at the dependencies if any and if none of these exist it will fall back to the independence assumption and do and multiplying the predicate the selectivity. So, and there's also the end distinct stats as

well that is really useful for queries with the group back clause. And so far we've been looking at the extended statistics within a table. Uh what about the data that are correlated but they're across a t a join boundary? Um right now there's no join statistics in Postgress. So whenever you have a query like this like select star from A join B on uh the join keys

and you have a wear clause with a filter with a very simple simple equality filter. Um what happens here is that the filter is on the dimension to table B and then the joint key correlation is like lies between these two tables. Um really this table the foreign key in table A is actually correlated to the filter column you in table B. But because right now the

statistics are stored all all stored per relation, the cross table correlation is invisible at the moment. So I guess it's probably pretty straightforward to think about creating joint statistics. So I went this way to try to solve the problem. And the goal for join statistics is to capture the join correlations between tables. And um I want to start with the joined um most common values and later

extend to other statistic types such as indistinct and And we also want to have low overhead during analyze because analyzing a drawing is probably going to be more expensive than analyzing a single table. And also we wanted to have a simple and extensible design. For example, we could start from collecting stats for a drawing between two tables. But later on we want to have the ability to

stay to store stats uh correlated stats uh for joins of more than two tables. And the not go here includes auto automatically collect um candidate columns and create the joint statistics. These are also important things but um we think it's better to separate this issue from from enabling the creation of the statistics. itself. So, um here's a proposed syntax for creating joined most common value statistics for

um and we could do something like create statistics and then specify the statistics name and the type. Right now we could probably start with MCV. And then the UN clause specifies the target column or columns for which we would store the frequencies for the most common values and the from clause um has the join of the two tables that are correlated through the join keys. Um so

here's an example of how to use this syntax. Um I want to mention that is even though we are for the first example where we have the on k keyword where there's only a single field fill uh filter column it still serves as a multicolumn statistics because this column is correlated with the other columns on the other side of the drawing through the join. And now that

we have uh so the next thing would be figure out how do we actually collect the join statistics. So think about um having a join between three tables A. Oh let's look at the left diagram and we are doing a join between three tables A, B and C. Um the most naive way of collecting the joint sets would be um sample collecting some sample rows from table

A and then collect sample rows from table B and then we join these sample rows and then we get the join samples and then again we collect samples from table C and then join with the previous sample rows and get the final results. And the problem with this approach is that we are only sampling a small portion of each of the table and we're doing them independently.

So that means the sample process will um skip some of the important correlations we actually wanted to capture. So really the better way of doing it is to use a uh approach called indexbased sampling. And what it does is that it first take the random samples from the outermost table, table A. And then we make sure that we we can either make sure we create an index

on table B on the join column. And then with that we can look up the sampled the previously sampled rows from A in table B. And then we can collect the matched result and count the numbers as well. And similarly we can have a index on table C on the join column and and join that with the previously sampled result and get the final uh match rows.

So um this approach was first introduced by this paper on the right hand side and it has tried to change the sample size as well from like 10k to 100k uh even no budget and the result is that using this index based sampling method the the result uh the of the estimates are uh improved from using just the na the naive sampling of postquest. So now that

we have better idea on how to implement it um I have uh implemented a prototype and it is attached in this uh email thread. Um so I I'll show the result of that patch. Really I wanted going back to the example we saw in the very beginning of the three table join. Um this is before this is with the patch but before creating any of the join

statistics. We get the same cardality underestimate and the long execution time from two nest loop joins. And then with the patch, I create a statistic a join statistics object on the keyword column um with the join between the keyword movie keyword table and the keyword table. And we can see that the plan has changed from two nestloop joins to uh the outer join is still nest loop

join but the inner join is uh replaced with a hash join. And we can also see that the estimate is a lot more accurate than before and the execution time is down to 251 And for my curiosity, I tried again to set the enable nest loop join to off. and again, we see the two hash joints, but the execution time is actually so is actually slightly higher

than the the one that just use the join statistics. So I'm pretty happy with this result. And um we move on to test the performance and in a bigger scale using the join order benchmark framework. So this join order benchmark framework was introduced by the paper on the right hand side and um it uses the real data from the internet med um what is it called AMDB

>> internet movie database. I'm leaving. Yeah. Yeah. Yeah. From internet movie database. And um the um have between three to 16 joins um with the average of eight joins per query. And um it what it trying to what it says is that this benchmark uh for the join kind of queries with correlation correlated data is better than benchmarks such as TPCH or TPCDS because TPCH and TPC

DS are using run like random generated data rather than using real data. Um so using the JB benchmark you can see that the with the number of drawings increase the underestimation of the cardality is just just increase as well whereas for TPCH queries the the number of join the change the increase of the number of joints doesn't really change the cardality underestimation because probably there are not

correlated in these benchmark TPC that's a good question I don't know it's it's a okay thank you wait transaction wait transaction processing console right so it's like a standard benchmark where you like have a certain schema schema, usually transactional schema or sometimes analytical for TBCDS and you can specify the scale like how many how much data you want to generate and then it can like randomly randomly

generate data for you and then it has a set of queries that you can run just is it's been using as like a standard way to test performance of databases. So yeah, so this slide is really just trying to say that for the problem we are trying to solve with the join correlations, we want to use join order benchmark because it can better review the the problem

and it can really demonstrate if we have solved the So um here is the setup I I used. I run the benchmark on my own laptop and with the def with the ri uh retail build and I did code runs where I restart the database and clear the system cache each time before I run the test and I did warm runs as well um with the repeated

run of the entire test suite and then I have the average of three runs per test and um for the joints that I wanted to test I only added a single join statistic object which is the one that we talked about earlier on on the keyword table and between the join of the movie keyword table and the keyword Um so this is the result of the total

execution time. The baseline is on the the latest Postquest uh development branch and I also have the same for that disabled nest loop join for reference and then and then applying my my patch. Um the result is pretty promising with cold runs. It um 39 it is 39% f faster than baseline and warm run is 45% faster than baseline. And if we look at the per query

execution times um I picked the top 10 slowest query using the baseline. So for the top tens is the query we can the blue is the baseline the red is the net the nost loop um case and the yellow is with the join st and we can see the with the join st all these queries execution time has um reduced. Um some of them are even lower

than the known nest loop cases and sometimes and some of them are still uh longer than the no nest loop case but but all of them are better than the Um so that's the prototype we have for join statistics. I also want to take some time to talk about other alternatives to improve cardality Um, one approach actually this is two approaches are learned and feedback based optimization

for the learned case a learn cardality. So you could do you could learn the cardality from from data by uh training a model that can predict the row counts of different expressions um and predates. So the example are mostly from research. Um for example you can learn um from a query learn from like different queries and learn the cardality of them or you can just directly learn

the data distribution of the data data you have where you could do like maybe the combination of them using some generative model mostly like to generate lots of queries and different expressions and just study the cardality coming out of um predicates and there's one that is in production called back card and the other subgroup of this approach is learn learning from past executions uh or feedback based

optimizations. In this case um the database can store the execution statistics for example like we can store we have an estimate and then we have the actual result uh during analyze or during the actual run using those past result um it can learn to improve the future plans and this has been um implemented in some production databases. and even for a while in some of for some

of them like SQL server has a cardality estimation feedback um method and Postquest has there is an extension called a query optim adaptive query um in postquest but to the best of my knowledge it's not really widely used in production and so probably in development and Presto also claims that they have something like history based optimization. The challenges of do of this approach for Postgress is I

think there is no existing pluggable query estimation interface in the planner right now and also um the model training is pretty time consuming costing and when the data change um you have to redo the work again. And another approach is runtime adaptation. Uh what it does is that instead of making the planner to know beforehand and having the the good estimates, it tries to correct the mistake

uh during the execution. For example, if it has chose a if it has chosen a nest loop join plan and then after while executing this plan, it after seeing like 40k rows instead of 34 rows, it decide to use the news that used the new number to to either either drop the previous plan entirely and replan again or Maybe for the part that hasn't been executed in

the plan, for the remaining part of the plan, it can do something else using this new information. So there are some production systems that applies this approach including the Oracle adaptive joins and spark adaptive query execution. And there is a research paper that did the same for Postgress as well using um simple tech simple techniques like early filtering using bloom filter. Uh which really is to look

ahead the how the filter look ahead the number of rows coming out of a join before even executing it. So it has a better idea and the ability to change to to do the adaptive ch uh join switching. So the paper claims that this method is um about the same or even better than the learned optimizers for the join for the uh joint order benchmark workflows. And

the third approach is called pessimistic bounce. Um, usually instead of focusing on getting the perfect estimates, it really tries to just get the upper bound of the estimate because often times really it was the it is the underestimation that will cause catastrophic problem um but not the um not the overestimation. So there is also some research and numbers here that claims claims that it is like 80%

lower end to end runtime on join order benchmark and sometimes as and nearly as good as using the true colonalities. So um these are the the the alternative approaches that I've researched lately and here is what I think Postgress really I want one thing I need to I wanted to add is regarding hardware timeline. Um really many of the optimizer op uh assumptions that we have today

were um designed when the random IO was expensive. For example, analyze sample size. The default analyze sample size is uh 30k rows and that that is based on a paper back in 1998 and for there are some parameters in the cost model. For example, the default random page cost value that was based off a experiment or some experiment that was done back in 2000. So um well

we know that in since last 2000 the hardware has improved quite a lot. Um for example the random read latency has increased from about 10 milliseconds to 20 microsconds. um which is like 500 times faster today. So maybe some of so somebody actually think thought about doing exact cardality estim exact cardalities rather than doing estimations. Um but still those are mostly for testing the testing the performance

of optimizer but not really use as used in production but but I think that as the hardware getting better in the future maybe we can for some of the cases maybe we don't even need to do do estimate and we can just do the use the the real number. Um so here is my opinionated possible directions for postquest. I think we still need want to make as

estimation as good as we can. So that means we could do we could do drawing statistics as what my prototype my prototype does and in the meanwhile we could leverage some learned cardality estimations. Um but that I think requires more work and more comp more complexity and then I think adapt during optimiz adapt during um runtime adaptation is also a direction worth exploring because it is already

used in some other databases and um there are also ways to avoid worse plans such as the pessimism bounds we just talked about and I just I didn't talk about PG plan in earlier but I added it because it is also a way to avoid um bad plans by giving the user the flexibility to um to control or fall back to a previously a previous safer plan.

And finally, we also want to keep ourself up to date regarding the cost model and regarding the the modern hardware. So yeah, I think this is the end of the talk and um I have more I have this slide itself and more resources and references I use while making the talk. So if you're interested, you can uh scan the QR code here. And this is the end

and I'm happy to take any questions.