General consistency
SQL Server does not make any general guarantees about the consistency of estimates in execution plans. The estimates do start off being consistent because cardinality estimation is performed on the entire original tree early on. Thereafter, different subtrees (parts of the visible plan) can be re-estimated at different times and in different ways.
As you may know, the cost-based optimizer can explore logically equivalent representations for parts of the tree. When a new logical equivalence is generated for some part of the query tree, the optimizer may need to derive new cardinality estimates and other local properties to work out the cost of the new alternative. Bear in mind, the logical alternative may have quite different operators from the original tree fragment, and more or fewer of them.
Since such derivations are statistical by nature and sensitive to the replacement subtree shape, the new estimates and properties may be quite different from the originals. There's no general way to know which to prefer, even where there is a straight choice to be made.
Ultimately, the optimizer chooses the cheapest option according to its cost model for each part of the tree it considers separately. The final plan is a 'stitched together' patchwork of the cheapest per-group options. There can easily be mismatches in cardinality estimation and other properties at the seams.
This example
Looking at the estimated row counts in Plan Explorer:
You can see the 25 and 41 row estimates are popular. This is a strong indication those numbers featured in the initial round of cardinality estimation.
Focusing on the estimates in the area of interest:
The much larger estimates are indicative of a re-estimation on a new candidate sub-tree, with a different shape and potentially different predicates. This is just the normal operation of a cost-based optimizer with exploration capabilities.
Both sets of estimates will be logically sound and defensible, given the context they were derived in. They disagree with each other, but that's just the nature of such things. One estimate turned out to be closer to reality than the other. The trick would be to know which estimate was better in advance.
As an aside, the low initial estimate of 41 rows caused the optimizer to prefer a nested loops (or a rather an apply) physical implementation in that area of the plan. It also ultimately causes the sort to spill since memory is assigned proportional to cardinality and average row size.
Other details
The index seek at node 22 is subject to an optimized bitmap filter, pushed down from the probe side of the hash join at node 8. Further, it has the IN ROW optimization applied, which means it is pushed right down into the storage engine and evaluated by the access method, before any qualifying rows are surfaced to the query processor.
This is an optimized bitmap filter, so it was present, and its effects considered, during query optimization. This is different from a static bitmap filter introduced heuristically after optimization is complete. The static type of bitmap doesn't affect cardinality estimates for that reason.
However, it is more complex that than. An IN ROW bitmap has two components: a small bitmap capable of being evaluated in the storage engine, and the full bitmap, which is applied by the query processor as a residual. That difference only manifests in post-execution 'actual' row count effects (e.g. the Number of Rows Read) but I mention it for completeness.
The effect of a bitmap filter is usually evaluated at an exchange operator (repartition streams) on the probe side of the hash join. The cost of this alternative helps the optimizer decide whether to use a hash join with bitmaps or not.
As a separate optimization, subsequent processing tries to push this filter as far down the tree from the exchange as possible. This later processing is quite basic and does not attempt to re-derive costs or estimates for dependent operators. It falls into the class of things considered 'always good'.
There happens to be no exchange on the probe side of the hash join in this plan because the optimizer ultimately chose to use Broadcast partitioning for the exchange at node 10. All rows are sent to all threads, so no probe-side partitioning is needed. Nevertheless, the bitmap filter is pushed down from where the exchange would have been.
The optimizer doesn't start with a hash join + bitmaps plan. It's only ever considered as an alternative during a parallel-enabled run of cost-based exploration.
I can't give you a precise answer with all the numbers and transformation details without access to the database producing this plan. Even so, it is a pattern that's familiar to me through experience: Some of the estimates were derived early on and survived the optimization process. Others were derived during cost-based optimization. The final franken-plan includes aspects from each.
You also mention FK relationships. These are considered by the optimizer during cardinality estimation (though not always as fully as we might like), but it does not go back and try to 'rationalize' the final plan based on those constraints. As I said at the beginning, there is no general guarantee of consistency.
Additional example
Using the AdventureWorks sample database:
SELECT P.ProductID
FROM Production.Product AS P
JOIN
(
SELECT TH.TransactionID, TH.ProductID
FROM Production.TransactionHistory AS TH
UNION ALL
SELECT THA.TransactionID, THA.ProductID
FROM Production.TransactionHistoryArchive AS THA
) AS U
ON U.ProductID = P.ProductID
OPTION (FORCE ORDER);
I'm using a FORCE ORDER hint to prevent several optimizer explorations so we end up with a plan shape close to the original written form of the query featuring initial cardinality estimates:
The final estimate of 142,412 rows is based on a join over the union of two tables.
Removing the FORCE ORDER hint allows the optimizer to consider a number of alternatives. The one chosen in my case is:
This is the result of considering the union of two joins rather than the original join over a union. There are two new joins requiring fresh estimates. The new joins produce 113,443 and 89,253 rows.
These feed into a concatenation that retains the original estimate of 142,412 rows, which is no longer the sum of its inputs. An inconsistency.
We could re-estimate the concatenation as 113,443 + 89,253 = 202,696 rows, but in general there is no way to know which estimate is better: the one derived from a join over a union, or the union over two separate joins.
The optimizer could choose to have a higher level of confidence in less derived estimates or more confidence in estimates based on known truths (like trusted foreign keys). Some internal changes have already been implemented in that general direction, but it is a fundamentally hard problem nowhere near fully solved or implemented in SQL Server yet.
This example is very simplified. Real-world plans will usually feature many independent (and recursive!) explorations and re-estimations in different small areas of the overall final plan.
For an overview of SQL Server optimizer operation, please see my Optimizer Deep Dive series.
