I am trying to understand how SQL Server estimates cardinality on the below Stack Overflow database query

Firstly, I create the index

CREATE INDEX IX_PostId ON dbo.Comments

And here is the query:

SELECT  u.DisplayName,
FROM    Users u
        JOIN Comments c
            ON u.Reputation = c.PostId
WHERE   u.AccountId = 22547

The execution plan is here

First of all, SQL Server scans the Clustered index on the users table to return the users that match the AccountId predicate. I can see that it uses this statistic: _WA_Sys_0000000E_09DE7BCC

enter image description here

I can see that this user doesn't have a range high key, so SQL Server uses the avg_range rows and estimates 1

enter image description here

The seek predicate on the comments index seek is

enter image description here

so Scalar Operator([StackOverflow2010].[dbo].[Users].[Reputation] as [u].[Reputation] represents the reputation value of the User(s) in the users table with the accountId of 22547

I can see three stats loaded in total :

_WA_Sys_0000000E_09DE7BCC - Users.AccountId (Used to estimate the Clustered index seek predicate)

IX_PostId - Comments.PostId (Used to estimate the Index seek predicate)

_WA_Sys_0000000A_09DE7BCC - Users.Reputation (?)

how does SQL server come up with the estimate on the index seek? It cannot know the reputation of accountId 22547 at compile time as the Account ID stat does not show that, so it cannot perform a lookup on the histogram for IX_PostId. I can see that the reputation stat is also loaded so does it use both somehow?

This query was run against CE 150


1 Answer 1


how does SQL server come up with the estimate on the index seek? It cannot know the reputation of accountId 22547 at compile time as the Account ID stat does not show that, so it cannot perform a lookup on the histogram for IX_PostId.

In this particular case, SQL Server doesn't derive a cardinality estimate for the index seek on the Comments table because it doesn't need to. Let me explain that statement a bit:

The compilation process always involves an initial round of cardinality estimation, where estimates are derived based on the early shape of the logical representation of the query after simplification. The logical tree in your example is:

    LogOp_Get TBL: dbo.Users(alias TBL: U)
        ScaOp_Comp x_cmpEq
            ScaOp_Identifier [U].AccountId
            ScaOp_Const Value=22547
    LogOp_Get TBL: dbo.Comments(alias TBL: C)
        ScaOp_Comp x_cmpEq
        ScaOp_Identifier QCOL: [C].PostId
        ScaOp_Identifier QCOL: [U].Reputation

Two initial estimates are needed:

  1. Filter Users.AccountId = 22547 (LogOp_Select)
  2. Inner join on Comments.PostId = Users.Reputation (LogOp_Join)

Leaving aside the details of those calculations for a moment, the fact is SQL Server does derive an estimated selectivity (and cardinality) for both, somehow. Let's say the cardinality estimate after the filter is C1 and the one after the join is C2.

During later cost-based optimisation, SQL Server considers different ways to implement the join. For example, it might derive estimated costs for a Merge Join, Hash Join, Nested Loops Join, or Apply (correlated loops join).

When it comes to consider an Apply (using a rule like JNtoIdxLookup), the optimizer already has an estimate for the top input to the join, C1. It also already knows the cardinality of the result of the join, C2. Let's say C1 is 10 and C2 is 250 for the sake of argument.

There's no need to produce a fresh estimate for the lower Apply input. We know it will execute 10 times (once per upper input row) and the join will produce 250 rows in total. Each iteration of the lower input therefore needs to produce 25 rows to make the numbers add up, 10 * 25 = 250.

The simple answer to your question is that in this case, the optimizer does not produce a cardinality estimate for the index seek—it is derived directly the from already existing join and filter estimates, by a rule that considers implementing a logical join as an Apply with Index Lookup.

Other details

There's no getting away from the fact that selectivity computations can be extremely complex. I have given you a simple answer above because that seems to address your question. Others might want a bit more detail.

I cannot describe the entire estimation framework here because I don't know all the details and even if I did, it would require several books to cover. That said, there are some things worth saying and some other resources to link to for the interested reader.

AccountId in the Stack Overflow sample database is an undeclared key—it is unique per user. That information should be enforced and communicated to the optimizer with a unique constraint or index.

Sampled statistics are handy to avoid excessive compilation times but they can present a misleading picture. Unless you are particularly looking to understand the highly involved world of statistics sampling, you should create or update statistics with a full scan to get repeatable, high-quality results.

SQL Server attempts to transform subqueries and applies to joins before initial estimation. This isn't always possible, so there are occasions where an estimate for an apply (possibly with an inner-side index seek) is derived directly. This is typically modelled as a series of point lookups. If you rewrite your query to an apply form that cannot be transformed by SQL Server to a join, you'll get different estimates using a different method. This is just the nature of the beast.

FROM dbo.Users AS U
    FROM dbo.Comments AS C1
        C1.PostId = U.Reputation
) AS C
    U.AccountId = 22547
    -- Don't transform the APPLY to a join

Deriving estimates is an expensive process, so SQL Server looks to avoid it where it can. In general, there's no particular reason to favour one estimate over another. It's perfectly possible to come up with 'n' different estimates using 'n' different (but equally logically sound) methods. Complex execution plans sometimes contain apparently contradictory estimates because different parts of the tree used different approaches at different times. Again, this is the way of things.

SQL Server may not derive a fresh estimate for the inner side of the apply in your example, but it does perform some related calculations to estimate the cost of the inner side seek, and how many times it would be rewound or rebound if a spool were introduced. Similar calculations are performed when estimating the cost savings for a 'missing index' suggestion.

Related Q & A and further reading (by me unless otherwise stated):

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.