You've actually got a few questions in here, so I'll break 'em out individually.
My problem/question is that the estimated number of rows for the above
query is 256, the actual number of rows is 560K. I want to understand
why there is such a big difference between these two numbers?
In order to answer that question, the first thing we would need is the actual execution plan for the query. In SQL Server Management Studio, you can get that by clicking Query, Include Actual Execution Plan. Run the query, click on the Execution Plan tab, and right-click anywhere in the whitespace to click Save Plan As. Save that, and post it somewhere for people to download and examine.
The next thing we would need is the output from DBCC SHOW_STATISTICS for the stats on that table. You've hinted at the output, and that's a good start, but the raw output will help us understand exactly what's going on.
If I run a DBCC SHOW_Statistics, the density section has both columns
in it, the histogram does not. Does SQL server produce a histogram for
the combination of columns in multi-column statistics?
No.
I have an index on (TaskExecStatusID,TaskExecUpdatedDate),
If you frequently use the query in the example (with TaskExecUpdateDate IS NULL), then you might check out filtered indexes. They're a new feature in SQL Server 2008 that allows you to put a where clause on your index, basically.
http://sqlfool.com/2009/04/filtered-indexes-what-you-need-to-know/
Up to date statistics does not necessarily imply perfect estimation. If you try to represent a range of 170 million values with 200 samples, even a small skew can throw you off by a factor of 10.
Here is a hint: time series are almost always accessed by time. Very likely DateStamp should be clustered key. For more detailes, post the exact DDL and actual execution plan (XML, not picture).
Best Answer
Cardinality estimates are just numbers. They don't matter unless you have a performance problem. You state in your question that there's a difference between the actual number of rows and estimated number of rows at some steps in the query plan. That's certainly true, but it's pretty uncommon to see non-trivial query plans for which estimates match the actual number of rows exactly. I wouldn't focus on a difference of a thousand rows unless you've identified that difference to be the root cause of a query performance issue.
Let's consider updating statistics: why might you see inaccurate cardinality estimation even after updating statistics? Statistics often don't fully describe the column's data. They could be sampled, 201 steps could be insufficient for some data sets, density isn't a good metric if there's skew in the data, and so on. Join cardinality estimation and combining filters on multiple columns is difficult even with perfect statistics objects because histograms are only available on one column. SQL Server often doesn't have information about the level of correlation between columns, so it needs to make a guess.
If you'd like to learn more I recommend taking a look at Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator by Joe Sack. Here's a quote on one of the many differences between the legacy CE and the new CE:
The CEs use different models. One model may be a better fit than the other for your data or even for just a single join. In this case, it has very little to do with statistics. Updating statistics just isn't enough to result in good estimates for all cases.
On the other hand, if you have a specific performance that you'd like help with, you'll need to give more information. I don't see anything alarming in the query plan that you posted. What is the performance problem that you have with the query?