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_Join
LogOp_Select
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:
- Filter Users.AccountId = 22547 (
LogOp_Select)
- 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.
SELECT
U.DisplayName,
C.PostId,
C.[Text]
FROM dbo.Users AS U
CROSS APPLY
(
SELECT
C1.PostId,
C1.[Text]
FROM dbo.Comments AS C1
WHERE
C1.PostId = U.Reputation
) AS C
WHERE
U.AccountId = 22547
OPTION
(
-- Don't transform the APPLY to a join
QUERYTRACEON 9114
);
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):
