Why are those estimates way off? I have problems understanding the following query plan: https://www.brentozar.com/pastetheplan/?id=SyoD_PosP
First there is the bottom right index seek. The estimation says over 22 million rows but the actual data is less than 2 million rows. My guess is, the estimation is based on just the rows matching the Tag column and a look at the index's histogram seems to corroborate that. Am I right in thinking that no assumption is made about the result of matching those rows to the predicate of the join and that this is what results in the differnce between the estimation and the actual result?
Second and more importantly, the Hash Match estimates that it will return 140k rows when in actuality it is about twelve times that. This leads to the sort operator spilling into tempdb a lot, if I understand what is happening correctly. Why is the estimate so low? And is there any way to improve it?
Update: Coincidentally, the values of Record.Tag are exactly [10399, 10438]. In principle there is no guarantee that it is a continous interval, tho. I tried J.D.'s suggestion and split the query into four queries and UNION ALL'ed them together. No improvement there.
Next I tried filling a temporary table with the Record rows of those Tags:
SELECT * INTO #tmprecord
FROM Record 
WHERE (Record.Tag&gt;=10399 AND Record.Tag&lt;=10438) 

SELECT DateAndTime, r.Reading, r.Tag 
FROM RecordSet 
INNER JOIN #tmprecord AS r 
ON RecordSet.RecordSetId = r.RecordSet 
WHERE RecordSet.Collector=10090
AND RecordSet.DateAndTime &gt;= '20201101 00:00:00' 
AND RecordSet.DateAndTime &lt;= '20210101 00:00:00'
ORDER BY r.RecordId

DROP TABLE #tmprecord

The estimation here seems better (four times instead of twelve times), but the spill takes about the same number of tempdb pages (76xx) and even more memory.
I believe this is due to all the ORs in your WHERE predicate on the Record.Tag field. It's causing a bad cardinality estimate. That is a rather long predicate and set of ORs, could you try breaking it into multiple smaller queries for different sets of Tags and the. UNION ALL the results of each query back together? It may help with the cardinality estimate.
You could also then change the ORs for a range when you break it up to make it less verbose at least, such as:
WHERE Record.Tag &gt;= 10400 AND &lt; 14006