Year: 1990

Authors: G Graefe

Summary

Volcano introduces two meta operators to help with control flow (but not actual data processing): choose-plan and exchange.

The exchange abstraction provides an interface for operators that are otherwise meant for single process systems to work in a parallel manner, which isolates the changes needed to be made to parallelize single process query processing code.

Combining those two meta-operators together we achieve self-scheduling: because the evaluation is immediate, the processes could report back when they are done, and the execution graph is all encoded in the relations between the processes there is no need for a centralized manager, which could be good for reducing contention.

The Exchange Meta Operator Model

Streams represent the most efficient execution model in terms of time and space.

Exchange is an extension to the iterator model in that they both implement the open, next and close procedures. The authors enumerate through the different kinds of relational operators to show how they could be supported by exchange:

  1. Scans, Functional Join, and Filter
  2. One-to-One Match (physical operator): implements a variety of set-matching functions such as join, intersection, union, etc, implemented by hashing or sorting.

It is the operator that implements all operations in which an item is included in the output depending on the result of a comparison between a pair of items.

  1. One-to-Many Match: compares each item with a number of other items to determine wh.ether a new item is to be produced. An example is relational devision. (Not discussed in detail and I don’t know how they are used…)

One example below:

Exchange Example

This creates demand-driven dataflow, which makes it easier to combine efficiently with horizontal parallelism and partitioning.

Variants:

  • Sometimes a producer might want to broadcast to all consumers.
  • An exchange module now could interface with multiple consumers based on specification from consumer.
  • And a bunch of other things, showing how flexible Volcano is!

Vertical parallelism

What it is: pipelining between processes. Essentially the parent process forks a child process to help do the work, where the parent process is the consumer and children producers. The children fills in a fixed size bucket and uses a semaphore to inform the parents of the generated packets. The parents closes the children exchange operator once it receives last record signal.

This is different from other models because this is data-driven (not demand driven) and could be viewed as push (and not pull), eager, and not lazy. This is nice for a few reasons:

  • Easier to implement horizontal parallelism
  • Removes the need for request messages: the less they talk the better!

To prevent the push based model to back-pressure too much (e.g. the consumer is too slow and uses up too much pinned buffer space), it uses a flow control semaphore. I think Eddies is basically this flow control on steroids.

Following from the previous illustration (same query), below is a possible vertical parallelism: Exchange Example

Horizontal Parallelism

What it is: intra-operator parallelism (as opposed to Inter-operator Parallelism, which is what vertical parallelism falls under): different CPUs perform the same operator on different subsets of dataset, and to get the subsets we need partitioning. The producer uses a support function to decide which queue the packet should go to. There are many different allocation algorithms for support function, such as round robin, key range or hash partitioning.

So to put horizontal and vertical together: after the parents create the child (vertical) the child becomes a master and creates slaves (horizontal, that is they are the original child’s siblings, but it’s a Machiavellian world alas). They later found that a propagation tree scheme worked better, where the slave structure is hierarchical. Still this had overhead, so they decided to use a thread pool as opposed to creating and destroying new threads.

Following from the previous illustration (same query), below is a possible combined parallelism example:

Exchange Example

Choose-Plan Operator

Here is an illustration of how it fits in:

Choose-Plan Example

the choose-plan operator does not make the policy decision concerning which of several plans to execute; it only provides the mechanism.

Notes: http://people.eecs.berkeley.edu/~brewer/cs262/exchange+eddies.html