{"id":49052,"date":"2022-12-01T08:00:00","date_gmt":"2022-12-01T16:00:00","guid":{"rendered":""},"modified":"2024-02-08T12:21:09","modified_gmt":"2024-02-08T20:21:09","slug":"cardinality-estimation-feedback-in-sql-server-2022","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/sql-server\/blog\/2022\/12\/01\/cardinality-estimation-feedback-in-sql-server-2022\/","title":{"rendered":"Cardinality Estimation Feedback in SQL Server 2022"},"content":{"rendered":"\n

Part of the\u202f<\/em>SQL Server 2022 blog series<\/em><\/a>.<\/p>\n\n\n\n

Cardinality estimation (CE) is a process used by the query optimizer to estimate the number of rows returned by a query or sub-part of a query. These estimates rely on two underlying things: statistics about the data and a set of assumptions\u2014known as the model. The model determines how we interpret statistics and data coming from various sub expressions, and so, for any given set of statistics, different models will arrive at different cardinality estimates. <\/p>\n\n\n

\n\t
\n\t\t
\n\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\"Database\"\t\t\t\t<\/div>\n\t\t\t\n\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t

SQL Server 2022<\/h2>\n\n\t\t\t\t\t
\n\t\t\t\t\t\t

The most Azure-enabled release yet, with continued performance, security, and availability innovation.<\/p>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tLearn more<\/span>\n\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\n\t\t\t\t\t<\/div>\n\t<\/div>\n<\/div>\n\n\n\n

Until SQL Server 2022<\/a>, CE could only have one model. The set of assumptions used was baked into the code of the server, and so whatever model was picked is what was used for all queries. However, we know that not all queries and workloads perform best under one single model. For some queries, the model we use works out well, but for others, a different model would perform better. With CE Feedback in SQL Server 2022, we can now tailor the model used to generate a query play to the specific query.<\/p>\n\n\n\n

CE has always had three basic assumptions that comprise the model: independence (or partial independence), uniformity, and containment. These three assumptions determine how we interpret histograms, and they determine how we combine data during joins or in the presence of multiple predicates. In this blog, I will explain these model variants and what they mean in more detail.<\/p>\n\n\n\n

Uniformity<\/h2>\n\n\n\n

Let\u2019s begin by discussing uniformity assumption. This assumption is used when interpreting data from the on-disk histograms\u2014abstracted data about the columns being queried. We assume that all data within steps, or buckets, of a histogram is uniformly distributed at an average frequency for that bucket. Thus, when we query data, this allows us to determine the number of rows that satisfy the predicate. <\/p>\n\n\n\n

Now, CE Feedback modifies the uniformity assumption only in one special case\u2014that of Row Goal<\/em> queries. These queries look like TOP n,<\/em> or Fast n, <\/em>or IN<\/em>. and there is a special optimization for row goal queries that relies on the independence assumption. Whenever we believe that a particular value occurs at a high enough frequency (based on our interpretation of the histogram using the independence assumption), we choose to do a quick scan of a few pages assuming that we will get enough qualifying rows very quickly. However, if the data is skewed, we may have falsely assumed more qualifying values than were actually present. This means we scan far more pages than expected to get the requisite number of rows.<\/p>\n\n\n\n

\n

CE Feedback can detect such scenarios and turn off the special row goal optimization. If it turns out that the query is indeed faster without this assumption, we keep this change by persisting it in the query store in the form of a query store hint, and the new optimization will be used for future executions of the query.<\/p>\n\n\n\n

\n
\"Non-uniform<\/figure>\n\n\n
\"Uniform<\/figure>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

Independence<\/h2>\n\n\n\n

Consider a where clause with two predicates, combined with an AND. Something like City=\u2019Seattle\u201d AND State=\u2019WA\u2019. Under the model assumption of independence, we would take the selectivity of the individual predicates (City=\u2019Seattle\u2019, State=\u2019WA\u2019) and multiply those probabilities together. Under the model assumption of correlation, we would take the most selective predicate (City=\u2019Seattle\u2019) and use the selectivity of that predicate only to determine the selectivity of the conjunctive clause. There is a third model of partial correlation, in which we multiply the selectivity of the most selective predicate with a weakened selectivity (raised to a power less than 1, to make the selectivity closer to 1) of the successive predicates. <\/p>\n\n\n

\"Chart
Figure 1: Independence. P1 and P2 are independent – that is, the truth (or falsehood) of P1 tells us nothing about the truth or falsehood of P2.<\/em><\/em><\/figcaption><\/figure>\n\n\n\n
\"Chart
Figure 2: Partial Correlation. In cases where we are evaluating P1 = T and P2 = T, you can see that P1 being true gives a higher likelihood of P2 being true. The cases where P1 is false are greyed out because they do not satisfy P1=T<\/em>.<\/figcaption><\/figure>\n<\/div>\n\n\n\n
\n
\n
\"Chart
Figure 3: Complete correlation. When evaluating P1=T and P2 = T, we can see that anytime P1 is true, P2 is also true (P1 implies P2).<\/em><\/figcaption><\/figure>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

CE always starts out with this last model of partial independence (referenced in other places as exponential backoff), but with CE Feedback, we can see if our estimates are too high, meaning the predicates are more independent, or too low, meaning that there is more correlation than expected, and adjust the model used for that query and those predicates accordingly for future executions. If this makes the plan or performance better, we persist this adjustment using a query store hint, and use it for future executions.<\/p>\n\n\n\n

Containment<\/h2>\n\n\n\n

The model assumption of containment means that users query data that is actually in the table. Meaning, if there is a column = constant predicate in the table, we assume that the constant actually exists in the table, at the frequency appropriate for where it falls within the histogram. However, we also assume that there is a containment relationship between joins. Basically, we assume that users wouldn\u2019t join two tables together if they didn\u2019t think there would be matches. However, there are two ways of looking at the containment relationship between joins: Base containment, or Simple containment.<\/p>\n\n\n\n

Base containment assumes that there is an inherent relationship between the tables participating in a join but doesn\u2019t make assumptions about the filters occurring on top of those tables before the join occurs. A good example might be a table of store sales and a table of store returns. We would assume that all things returned were also sold, but we would not assume that any filtering on the sales or returns tables makes containment more or less likely\u2014we just assume containment at the base table level and scale the size of the estimated result up or down based on the filters in play.<\/p>\n\n\n\n

\n
\n
\"Chart<\/figure>\n<\/div>\n\n\n\n
\"Chart<\/figure>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

Simple containment is a bit different\u2014instead of assuming some inherent relationship between the base tables, it assumes that the filters applied to those tables create a containment relationship. For example, querying for graduating seniors from a specific high school and joining that with a query for athletes in a given zip code. While there is some inherent relationship between the two tables a priori, the filters applied specifically limit and create a containment relationship. <\/p>\n\n\n\n

\"Chart<\/figure>\n\n\n
\"Chart<\/figure>\n<\/div>\n\n\n\n

CE starts with the base containment model for all queries. However, if the estimates for the join are \u2018off\u2019 in some way\u2014the incoming estimates are good, the outgoing estimates are bad\u2014we try the alternate containment model. When the query is executed again, we try out the other model, and if it is better, we persist it with a query store hint and use it for future executions.<\/p>\n\n\n\n

Conclusion<\/h2>\n\n\n\n

In summary, CE requires a basic set of assumptions that are used to interpret and combine statistical data about histograms or sub-parts of a query. Those assumptions work well for some queries, and less well for others. In SQL Server 2022, we have introduced a method of CE Feedback which adjusts those assumptions in a per-query way, based on actual performance of the query over time. <\/p>\n\n\n\n

Learn more<\/h2>\n\n\n\n