About sort or hash in a parallel query plan

GokhanVarol 2013-06-13 02:12:11

If a table is parallel scanned and then it's pushed into a hash or a sort, let's say in maxdop = 8 and this is running in 8 threads, I am guessing parallel method is round robbin (not sure if this matters) will there be 8 different memory tables the hash or sort is building on or there is only a single memory table.
Especially for hash if hash is built on table a in 8 threads and table b is pulled into this join how can it be made sure that any data coming from any 8 threads of table b is matched against all data in the hash? If all this is done on 8 threads and pushed into a same memory table then lot's of synchronization would be necessary and how would that (if it's the case) affect the plan/execution?
I am asking this I guess I did not fully understand how a parallel hash or sort work.
Is there an article explaining this?
Thank you
SQLkiwi 2013-06-16 03:50:39
For parallel hash and merge, the partitioning method used by the exchanges feeding the join operator will generally be hash partitioning. Using the same hash functions for both inputs to the joins ensures that rows from either input that might join end up being evaluated by the same instance of the join operator.

Hash parallel join may also use broadcast partitioning, where rows from the build input are sent to all probe-side threads. This eliminates the need for an exchange on the probe input, but the duplication of rows means more memory will be needed. The optimizer generally selects broadcast parallel hash join where the probe input has a low cardinality.

Batch mode parallelism over a columnstore works a bit differently – a single hash table is built and 'lock-free' (compare and exchange) techniques are used to synchronize access to the shared hash table.

Parallel sorts also generally use hash partitioning. They may also use range partitioning in index building plans, but the idea is the same – DOP sorts get a fraction of the rows to be sorted each, as determined by the partitioning scheme used by the exchange.

GokhanVarol 2013-06-16 03:56:27
Is it since the full hash table will be built blocking does not matter which thread builds the hash table, when the hash table be built now it's available to all the threads of the other side of the join to be matched against?
SQLkiwi 2013-06-16 04:13:03
For columnstore or regular hash join? For regular hash join using hash partitioning, there are DOP hash joins, and so DOP hash tables. Using the same hash function means build and probe rows that might join are guaranteed to go to the same instance of the hash join.

For columnstore batch hash table build, all threads contribute to building the single shared hash table.

GokhanVarol 2013-06-16 14:57:19
I think this was what I missed (I think I got it this time), hash partitioning guarantees that a record returning a hash value which causes which backet the hashed probe will be stored or hashed lookup will be made, this way even though there are as many hash backets of the dop setting from both inputs the same input values end up into the same bucket? At the end there are as many backets as the dop setting (and they could be imbalanced caused the the data imbalance) ?
SQLkiwi 2013-06-16 20:31:04
Not quite. DOP determines how many instances of the hash join there are. At DOP 8 there are 8 hash joins, each running on a separate thread. The repartitioning exchanges route rows from the two join inputs based on a hash function applied to the join keys in the rows. Using the same hash function for both ensures that rows that might join (because the join keys match) end up at the same hash join instance.