Why do SQL Server row estimates change when I add a join hint?
From reading different articles and books, I assumed that the cardinality estimations are performed before the plan is built.


Not exactly. An initial cardinality estimate is derived (after simplifications and other work), which influences the initial join order chosen by the optimizer.

However, subsequent explorations (during cost-based optimization) can, and often do, result in new cardinality estimations being calculated. These later CEs may be more or less 'accurate'. If an under-estimate results, the optimizer may choose a plan that looks cheaper, but in fact runs for much longer.

In general, there is no guarantee that cardinality estimations for semantically identical subtrees will produce the same results. It is a statistical process, after all, and some operations have deeper CE support than others.

In your case, there appears to be another factor - the optimizer introduces (or moves around) a Top, which sets a row goal on the subtree beneath it:



If you were to enable trace flag 4138 (on 2008 R2 or later), you may find the estimates more in-line with expectations, or perhaps even that the optimizer would no longer choose nested loops.


  What I see, however, is that Merge hint causes all estimations to become pretty much perfect.


There is an element of luck involved here. People tend to write queries, or at least the joins, in the order they expect them to be performed physically. Using a join hint comes with an implied FORCE ORDER, thereby fixing the join order to match the textual form, and switching off many optimizer exploration rules that can lead to cardinality re-estimation.


  Besides that, I tried running the query with OPTION (FORCE ORDER) - it runs even faster than using merge join, choosing HASH MATCH for every join.


This is the same as hinting a join, but does not restrict the choice of physical join operator. Again, if you happened to write the query join order in a logical way, it is quite likely you will get a reasonable plan. Of course, you miss out on much of the optimizer's abilities this way, which may not produce optimal results in more general situations.

You will probably not want to use FORCE ORDER very often because it is an extremely powerful hint (directive) that has wider effects than simple forcing the order of joins; for example, it prevents the optimizer moving aggregates around and introducing partial aggregations. I very much advise against using this hint except in very exceptional circumstances, and by truly expert tuners.

A detailed analysis would require more time than I have right now, and access to a statistics-only copy of the database.