-
Notifications
You must be signed in to change notification settings - Fork 980
Runtime Model
The runtime model describes the portion of Drill that executes a query. As described in the Drill documentation, each query is submitted by the user, is parsed, is planned, then is executed. During the planning phase, Drill works with definitions or descriptions of how the query is to be run. At run time, those definitions turn into actual running code distributed across Drillbits. What we call the Runtime Model here is the same the "Execution Operation" query state in the Drill docs.
Drill is one of a large family of big-data tools that use the DAG (directed acyclic graph) execution model. Here we describe the model in very high-level terms. The story here is a gross over-simplification of Drill internals. However, it gives us a framework to build upon as we work through actual Drill implementations.
The runtime model is based on an execution graph composed of three kinds of nodes:
- Sources which read data from outside of Drill,
- Transforms which modify the data in some manner specified by the query, and
- Sinks which write data to a destination outside of Drill.
Drill execution graph nodes are joined by edges realized as tuple sets. (In data base terms, a tuple is a row or record. A tuple set is a collection or rows or records.) Sources produce (but do not consume) tuple sets, sinks consume (but do not produce) tuple sets, and transforms both produce and consume tuple sets. Note that edges are sets of tuples, not a single tuple. Tuple sets themselves are implemented as columnar value vectors, as described here.
The terms used here are generic; Drill itself uses other terms which we'll come to later.
Drill defines two types of sources:
- Record Readers (also called scanners) which read data from files, databases and the like, and
- Receivers which read data over the network from other Drillbits.
Drill defines three types of sinks:
- Writers which write query results to a file (as part of a CREATE TABLE AS, or CTAS, query),
- Senders which transmit data to another Drillbit over the network, and
- Clients which convert results into a form required by a client application.
Drill includes a large set of transforms, many more than can be listed here. Transforms can be characterized by a triple of `(input, operation, output):
- Input: A set of one or more tuple sets. Transforms are characterized as having an input cardinality of 1 (such as a filter), or many.
- Operation: What the transform does.
- Output: A set of one or more tuple sets. Again, Transforms are characterized as having a single output or possibly multiple outputs.
Queries conceptually work with one tuple at a time. In practice, however, considerable efficiencies result from working with batches of tuples in a single operation. Further efficiencies are gained from columnar representation of the data. In theory, a transform can use very efficient code to spin through a single column of data to, say, select rows that meet a filter condition, or to produce a sum.
Drill tuple are best thought of as a set of tuples, represented as column vectors. Conceptually, tuples form a grid: rows horizontally, columns vertically. Every column represents the same number of rows (though the details get quite complex.) Readers often rotate a row-based format to columnar, and clients often rotate the data back to row-based.
((Insert example.))
The result is the classic DAG data flow model:
((Insert picture))
Drill is distributed. This means that the execution graph does not run on a single machine, instead it is split into a series of fragments (sub graphs). Data is sent over the network from one subgraph to another: from a sender in one fragment to a receiver in another.
Because of the way fragments are implemented, you will often see the term "operator tree" used for the sub-graph of nodes that appear within a single fragment. The root of the tree is a sender, the leaves are sources: either readers or receivers. Data flows from the leaves to the root. The term downstream refers to data flow direction (toward the root), while the term upstream refers to the source of data: toward the leaves.
The above is a greatly simplified overview. Let's see how Drill implements the execution graph in practice.