asked
hash joining to a sorted stream
Can some clever spark out there explain why, when I have a sorted stream (eg. using clustered index) which I then perform a hash join, result in an unordered stream? In the example below, basket table and basket_item table both have clustered indexed sorted by basket_id asc. without the inner hash join between product and basket, the query is happy merge joining without requiring a sort. As soon as I put the the hash join in it performs the hash join on the sorted stream (basket_item) - but then has to sort the resultant stream before merge joining to the basket table. I have over 800M rows in the basket table - so this is not a good plan! The query below is a little contrived to demonstrate the problem - my "real" query does not involve taking the min(major_department_code) - but if anyone has any idea how to remove this redundant sort, then please let me know. I have considered that it may have been to do with a parallel process, but seting MAXDOP to 1 does not resolve the query either. I'm sure there may be a technical reason for this, but the hash join process is described as "use each row from the top input to build a hash table, and each row in the bottom to probe into the hash table, outputing all matched results" - my "top" input is the product table - and my bottom query is the basket_item - so why, if the bottom is sorted, would it want to re-sort itself after the hash join? select bb.basket_id , bi.min_mdc from mart.basket bb left merge join ( select a.basket_id , min_mdc = min(p.major_department_code) from mart.product p inner hash join mart.basket_item a on p.product_id = a.product_id group by a.basket_id ) bi on bi.basket_id = bb.basket_id
"if the bottom is sorted, why would it want to re-sort itself after the hash join" strangely the optimizer doesn't think so. Look at the inputs to the hash join, the optimizer has the Ordered property set to False even though they are both clustered index scans. If I were to speculate, I would say this is because the hash of the key is not ordered the same as the key. Change this to merge join and presto, it is now ordered...I guess to answer your question, to get rid of the sort, change both joins to merge or both joins to hash (but then you will have to sort later anyway). If you post your actual query we may be able help to optimize it.
Thanks for you suggestion however, I think I may not have been precise in my question. In terms of the join strategy, the query above represents what I'm trying to achieve. Basket contains 250M records and has a primary key with a clustered index on basket_id. Basket_item contains 850M records and has a primary key on basket_id+basket_line_number which again is the clustered index. Merge-joining these streams together utilises the fact that the streams are both sorted, by fact of their index. However, adding the hash key lookup seems to remove the knowlege that the input stream is already sorted and forces a sort after the hash join. My understanding is that a hash join loads the top query (in this case the product table) into memory, and uses the bottom query (in this case the basket_item), to probe into it. Therefore if the bottom query is sorted then surely the net result should also be sorted? To simply say "merge-join" the product table to the basket_item table - would result in a sort of 850M records (assuming no covering index) - which would produce an output in product_id order which would then require a further sort of 850M reocrds to return it back to basket_id order.
As far as I understand it, by applying a hash function to your data and thus pushing it into hash buckets, you are removing any sort order that was previously present. The Query Optimiser (QO) then no longer considers the data sorted and has to re-sort after the hash join. This begs the question - Why are you forcing a hash join at all? Query hints should be rarely used (extreme edge cases in my experience), where you *really* know better than the QO. You say that you are running a join on two suitably sorted sets of data with large volumes - a MERGE JOIN is the best join type for this operation. It is not surprising to see the QO making this decision. The only time I have prescribed the use of join hints was when an ad-hoc query was coming into a system where the normal query plan would be incorrect through the parameters being used. Forcing a certain join type and marking the plan for one-time-use was the way to go. In your scenario, I would remove all join hints and let SQL Server decide what is best by running through the schema meta-data and statistics at hand.
The data returned by the hash join is not guaranteed to be in any particular order. As I understand it, the hash join has the following features that may explain your observed behaviour: * memory is pre-allocated based on estimated rowcounts * overspill goes into the TempDB If you're running through an 850M row record set, then the data is certain to be dumped to TempDB, where it is treated just like any other table. And data returned from any table is **not guaranteed to be in any particular order.**
I didn't realize there were that many rows. Certainly it is spilled to multiple work table partitions. Additionally if there are group by columns they are often added to the hash, in the toy example it is simply the id, which is already included
