The Parallelism Operator (aka Exchange)
As I noted in my Introduction to Parallel Query Execution post, the parallelism (or exchange) iterator actually implements parallelism in query execution. The optimizer places exchanges at the boundaries between threads; the exchange moves the rows between the threads.
The iterator that’s really two iterators
The exchange iterator is unique in that it is really two iterators: a producer and a consumer. We place the producer at the root of a query sub-tree (often called a branch). The producer reads input rows from its sub-tree, assembles the rows into packets, and routes these packets the appropriate consumers. We place the consumer at the leaf of the next query sub-tree. The consumer receives packets from its producer(s), removes the rows from these packets, and returns the rows to its parent iterator. For example, a repartition exchange running at degree of parallelism (DOP) two, consists of two producers and two consumers:
Note that while the data flow between most iterators is pull based (an iterator calls GetRow on its child when it is ready for another row), the data flow in between an exchange producer and consumer is push based. That is, the producer fills a packet with rows and “pushes” it to the consumer. This model allows the producer and consumer threads to execute independently. (We do have flow control to prevent a fast producer from flooding a slow consumer with excessive packets.)
How many different types of exchanges are there?
Exchanges can be classified in three different ways.
First, we can classify exchanges based on the number of producer and/or consumer threads:
| Type | # producer threads | # consumer threads |
|---|---|---|
| Gather Streams | DOP | 1 |
| Repartition Streams | DOP | DOP |
| Distribute Streams | 1 | DOP |
A gather streams exchange is often called a “start parallelism” exchange since the operators above it run serially while the operators below it run in parallel. The root exchange in any parallel plan is always a gather exchange since the results of any query plan must ultimately be funneled back to the single connection thread to be returned to the client. A distribute streams exchange is often called a “stop parallelism” exchange. It is the opposite of a gather streams exchange: the operators above a distribute steams exchange run in parallel while the operators below it run serially.
Second, we can classify exchanges based on how they route rows from the producer to the consumer. We refer to this property as the “partitioning type” of the exchange. Partitioning type only makes sense for a repartition or a distribute streams exchange since there is only one way to route rows in a gather exchange: to the single consumer thread. SQL Server supports the following partitioning types:
| Partitioning Type | Description |
|---|---|
| Broadcast | Send all rows to all consumer threads. |
| Round Robin | Send each packet of rows to the next consumer thread in sequence. |
| Hash | Determine where to send each row by evaluating a hash function on one or more columns in the row. |
| Range | Determine where to send each row by evaluating a range function on one column in the row. (A range function splits the total possible set of values into a set of continguous ranges. This partition type is rare and is used only by certain parallel index build plans.) |
| Demand | Send the next row to the next consumer that asks. This partition type is the only type of exchange that uses a pull rather a push model for data flow and is used only in query plans with partitioned tables. |
Third, we can classify exchanges as merging (or order preserving) and non-merging (or non-order preserving). The consumer in a merging exchange ensures that rows from multiple producers are returned in a sorted order. (The rows must already be in this sorted order at the producer; the merging exchange does not actually sort.) A merging exchange only make sense for a gather or a repartition streams exchange; with a distribute streams exchange, there is only one producer and, thus, only one stream of rows and nothing to merge at each consumer.
Showplan
SQL Server includes all of the above properties in showplan (graphical, text, and XML).
Speaking of showplan, in graphical showplan you can also tell at a glance which operators are running in parallel (i.e., which operators are between a start exchange and a stop exchange) by looking for a little parallelism symbol on the operator icons:
In my next post about parallelism, I’ll begin to explore some parallel query plans and demonstrate the different types of exchanges in action.