The Tukwila Execution Interface

Zack Ives, May 1999 / Updated August 2001

Introduction

The Tukwila query processing components are designed to be self-contained modules that can be swapped out as needed. Each of the main components (reformulator, optimizer, execution engine, and wrappers) are separate code modules, each optionally in a different language and on a different platform. A sockets-based communication interface with a standardized request model allow us to interchange parts.

Executing a Query

Tukwila now uses a subset of the W3C XQuery (formerly Quilt) XML query language to specify queries. The optimizer component of the system includes a Java Swing-based GUI that allows the user to interactively pose queries and see results. The optimizer JAR file also includes library routines to directly invoke the optimizer and the execution system from within your own applications. See the tukwila.InvokeXQuery documentation for more details.

Currently the query optimizer only understands queries without nesting. Nested queries are supported by the underlying execution system, and if demand is sufficient, I will add support to the optimizer for this feature.

Executing a Plan

The query execution engine constantly monitors port 7776 (by default) for query execution requests. A request is simply a physical query plan in the format described later in this document. The request is encapsulated in a SOAP HTTP request, and the result is returned in XML as a SOAP HTTP response.

A query response will generally contain data (i.e. query results), unless the query does not execute to completion. The state of individual operators in a query plan (including their cardinalities) is also returned.

The query result string, which is described in a later section, will begin with an execution status. This status should be used as the basis for the optimizer's decision to terminate successfully, terminate with error, or re-optimize a query. If re-optimization is performed, the optimizer will simply send a new query plan through the same socket to the execution system.

Query Plans in Tukwila

The basic layout for a query plan is as follows:

Header and user information
Query requests (generally only one per plan):
1. Fragments (may be multiple per plan):
  1. Query operator graph
  2. Fragment-local execution rules
2. Global execution rules (i.e. rules across fragments)

More Detailed Sketch of a Plan

The header is fairly simple, and most of it can be repeated verbatim. Much of the header information is for the benefit of XML parsers and for future use. Note that "auser" is the default user ID for many of the wrappers we have, so you should use that by default.


<?xml version="1.0"?>

<!DOCTYPE PLAN SYSTEM "plan.dtd">
<PLAN ID="PlanName" VERSION="1.10" REQUESTOR="RequestID" 
RESULT="QueryRootNodeID" USER="auser">

<FRAGMENT NUM="ExecutionStep"> <GRAPH>  <XML SOURCE="FragmentRootNodeID" /> | <OUTPUT NODE="FragmentRootNodeID" /> <N ID="NodeID" OP="Operator" attributes CARD="EstimatedSize"> </N>  </GRAPH> <RULES> <R ID="RuleID"> <WHEN>Event</WHEN> <IF>ConditionTest</IF> <THEN>Action</THEN> <ELSE>Action</ELSE> </R>  </RULES> </FRAGMENT> 

 <RULES> <R ID="RuleID" ACTIVE="state"> <WHEN>Event</WHEN> <IF>ConditionTest</IF> <THEN>Action</THEN> <ELSE>Action</ELSE> </R>  </RULES> </PLAN>

Creating Plans by Hand for Tukwila

For the most part, constructing a plan is simply a matter of "filling in the template" above. Each plan and request will get a unique ID.

Each fragment within a request is given a number representing an execution step, and it materializes its results. Fragments are sequenced in order by execution step, and then executed from lowest to highest step number. (A future extension to Tukwila may allow for multiple fragments to execute in the same step, but that is not currently supported.) The use of rules and fragments is likely to be minimal in a hand-authored plan.

Within the fragment are an operator graph and a set of rules specific to the fragment. The operator graph includes an <OUTPUT> or <XML> element which specifies which node is the root of the fragment (and whose output should thus be written to disk), and the NODE/SOURCE parameter of this attribute must reference one of the nodes in the fragment graph. Nodes are specified with the <N> element, and include operator type, expected cardinality of result, any children, and various other parameters.

The Operators

Join (with specific type including HASH, DOUBLE_PIPELINED, NESTED_LOOPS). The <WHERE> clause specifies an equality constraint between attributes in each of the children. Note that each attribute must be specified fully with the ChildNodeID.Attribute syntax. Only the NESTED_LOOPS join is allowed to contain conjunction (the OR operator), arithmetic operations, or non-equality comparisons.


    <N ID="NodeID" OP="JOIN" TYPE="HASH" 
CHILDREN="LeftChildNodeID RightChildNodeID" SPACE="KBytesToUse" 
CARD="ExpectedCard">

        <WHERE>LeftChildNodeID.LeftChildAttrib =

        RightChildNodeID.RightChildAttrib</WHERE>

... </N>

Select. As with Join, note that the <WHERE> clause fully specifies each attribute with the ChildNodeID.Attribute syntax.

<N ID="NodeID" OP="SELECT" CHILD="ChildID" CARD="ExpectedCard"> <WHERE>ChildID.Attrib {relop} {expression}</WHERE> </N>

Wrapper. Specifies an SQL-syntax query to be sent to a specific host URL and a wrapper-specific service ID (which is usually a table name). Also specifies a timeout in ms, after which an event is triggered. Wrappers can be prefetching (the PREFETCH operator) or non-prefetching (the WRAPPER operator). Note that you should not use the prefetching wrapper as a source for either the double pipelined join or the collector, as in both cases you are simply adding extra threads at the cost of performance. (Note additionally that relational wrappers of this fashion are being phased out of Tukwila -- for XML, use the x-scan operator below.) Moreover, the TIMEOUT operator is no longer active in the current version, for cross-platform compatibility reasons.

<N ID="NodeID" OP="PREFETCH" TIMEOUT="TimeIn_ms" CARD="ExpectedCard"> <HOST>HostName:Port</HOST> <SERVICE>WrapperService</SERVICE> <QUERY>SQLQuery</QUERY> </N> <N ID="NodeID" OP="WRAPPER" TIMEOUT="TimeIn_ms" CARD="ExpectedCard"> <HOST>HostName:Port</HOST> <SERVICE>WrapperService</SERVICE> <QUERY>SQLQuery</QUERY> </N>

Project. Specifies a series of attributes to project from the child node. Note that, as in all other cases, the projected attributes must be fully specified with ChildNodeID.attribute syntax.

<N ID="NodeID" OP="PROJECT" CHILD="ChildNodeID" CARD="ExpectedCard"> <ATTR>ChildNodeID.attribute</ATTR> <ATTR>ChildNodeID.attribute</ATTR> ... </N>

Collector. Specifies a series of child nodes for the collector operator. Note that a collector node by default has all children disabled, and rules must be used to enable one or more children (usually based on the OPEN event, described later in this document).


    <N ID="NodeID" OP="COLLECTOR" CHILDREN="ChildNodeID1
ChildNodeID2 ..." 

     SPACE="KBytesToUse" CARD="ExpectedCard">

    </N>

Sort. Does an external mergesort on the child's tuples, given some amount of space as a work area.


    <N ID="NodeID" OP="SORT" CHILD="ChildNodeID" 
ORDER="ASCENDING | DESCENDING" SPACE="KBytesToUse" CARD="ExpectedCard">

        <ATTR>ChildNodeID.attribute</ATTR>

        <ATTR>ChildNodeID.attribute</ATTR>

    </N>

Aggregate. Performs a hash-based aggregation operation.
<N ID="NodeID" OP="AGGREGATE" CHILD="ChildNodeID" SPACE="KBytesToUse" CARD="ExpectedCard"> <SUM>ChildNodeID.attribute</SUM> | <MAX>ChildNodeID.attribute</MAX> | <MIN>ChildNodeID.attribute</MIN> | <COUNT>ChildNodeID.attribute</COUNT> | <AVG>ChildNodeID.attribute</AVG> ... </N>
Union. Unions two subquery results, removing duplicates. WARNING: Expects results to fit in memory provided.
<N ID="NodeID" OP="UNION" CHILDREN="ChildNodeID1 ChildNodeID2" SPACE="KBytesToUse" CARD="ExpectedCard"> </N>
X-scan. Performs pattern matching on a specified document and returns a tuple containing bindings between variable names and subtrees/subgraphs within the document. X-scan can use a validating or non-validating parser, it can "inline" variables that are leaf (PCDATA) nodes, and it can handle hierarchical and sibling bindings. The TYPE for inlining can be STRINGlength, INTEGER, DOUBLE, etc. There is an additional type UPSTRINGlength, which converts the string to uppercase as it inlines (this can be useful for case-insensitive compares).

Use "/" for subelement, "=>" for IDREF, "/@" for attribute delimiters within a path, "." for subelement or IDREF.



  <N ID="NodeID" OP="XSCAN" FILE="http://location/file.xml" 
  VALIDATE="YES | NO" CARD="ExpectedCard">

      <PATH NAME="Binding1">root/path1</PATH>

      <PATH NAME="Binding2" INLINE="TYPE">Binding1/path2</PATH>

  </N>

Indirect-scan. Allows the substitution of variables into a URL that is to be x-scanned. This allows us to specify input bindings for CGI-based or web-based queries.
Literal. Outputs a literal value in the XML output.
<N ID="NodeID" OP="XLITERAL" CHILD="ChildNodeID" VALUE="LiteralString" CARD="ExpectedCard"> </N>
Lookup. Takes a binding from the tuple, looks up its value, and copies it to the XML output.

<N ID="NodeID" OP="XLOOKUP" CHILD="ChildNodeID" CARD="ExpectedCard"> <ATTR>ChildNodeID.attribute</ATTR> </N>

Attribute. Constructs an attribute "over" the last XML result output from the current tuple. (Note: this content should only be a lookup or a literal -- the execution system will support embedding of an element, but this results in invalid XML!)
<N ID="NodeID" OP="XATTRIBUTE" CHILD="ChildNodeID" LABEL="Label" CARD="ExpectedCard"> </N>
Element. Constructs an element "over" the last count XML results output from the current tuple. The XML output tree is encoded in postorder fashion, so all that is required is a count specifying how many children should be "popped" off the stack and added as children. (See the paper for more details.)
<N ID="NodeID" OP="XELEMENT" CHILD="ChildNodeID" LABEL="Label" COUNT="count" CARD="ExpectedCard"> </N>
Nest. Nests one XML output within another according to an equijoin predicate. (Hash-based join.)
<N ID="NodeID" OP="XNEST" CHILD="OuterNodeID1 InnerNodeID2" CARD="ExpectedCard"> <WHERE>OuterNodeID.LeftChildAttrib = InnerNodeID.RightChildAttrib</WHERE> ... </N>
ForAll.
Split.
Share.
DSelect, DProject, DJoin, DTransduce, DAggregate, DExpand, DForAll. Reserved.

Rules

A rule R is formally a quintuple <event, condition, action, active_flag, owner>, where the owner is a node, fragment, or plan; and the active_flag must be TRUE for the rule to be in the active set.

As an event E occurs, it is sent to the Tukwila event handler. The event handler checks a hash table to see if any rules in the active set match E; if so, it places the event into the event queue. Each event is individually dequeued in the order it was detected, and now all matching rules are triggered serially before the next event is processed. The condition for each rule is tested, and if it is met the actions are executed sequentially. If the optional ELSE clause is used, an alternate series of actions may be executed. Formally, the rules' conditions should all be tested in parallel, and all actions should be executed in parallel; our implementation does both of these serially.

There are no synchronization or locking semantics, so rules are not allowed to have conflicting actions; the rule generator must prevent this from happening. Rules are not executed for operators which have been terminated, in order to prevent deadlock and race conditions. Once a rule has been executed, it becomes inactive, unless one of its composite actions is to reactivate the same rule.

Events

STATE_BECOMES(node, stateval)
END_OF_FRAGMENT
OUT_OF_MEMORY
WRAPPER_TIMEOUT(node, intval)
EVERY_N_TUPLES(node, intval)
EVERY_N_MS(intval)

Conditions

condition ::= <bool>
bool ::=
- TRUE
- FALSE
- <intval> <relop> <intval>
- (<bool> AND <bool>)
- (<bool> OR <bool>)
- NOT <bool>
- STATE(node) = stateval
intval ::=
- GLOBAL_MEMORY
- MEMORY_ALLOCATED(node)
- MEMORY_USED(node)
- CARD(node) - true cardinality at this moment
- ESTIMATED_CARD(node) - estimated cardinality (though optimizer probably knows this)
- TIMEOUT(node) - timeout count
- TIME_SINCE_LAST_TUPLE(node) - time since last tuple produced
- NEXT_CHILD_INDEX(collector) - next unopened collector child
- NUM_OPEN_CHILDREN(collector) - number of collector children open
- integer value or expression formed with constants
stateval ::=
- OUT_OF_MEMORY
- TIMEOUT
- ERROR
- NOT_OPEN
- OPEN
- CLOSED
activity ::=
- ACTIVE
- INACTIVE

Actions

OVERFLOW_SYMMETRIC_HASH(node) - specify that a DPJoin overflow using symmetric overflow strategy
OVERFLOW_SINGLE_HASH(node) - specify that a DPJoin overflow using left flush overflow strategy
REPLAN - re-optimize the plan
SET_TIMEOUT(node, intval) - changes a wrapper timeout interval
ADD_MEMORY(node, intval) - attempts to grant more memory to a join operator
REDUCE_MEMORY(node, intval) - attempts to steal memory from a join operator
ERROR(string) - sends an error back to the optimizer
ACTIVATE(collector, node) - activates node, the child of collector collector
ACTIVATE_NEXT(collector) - activates the next untouched child of collector collector, in left-to-right order
ACTIVATE(rule) - activates a rule
DEACTIVATE(collector, node) - deactivates node, the child of collector collector
DEACTIVATE(rule) - deactivates a rule

Format

<RULES>

<R ID=ruleID [STATE=activity]>

<WHEN>event</WHEN>; <IF>condition</IF>; <THEN>action{;action}</THEN>; [<ELSE>action{;action}</ELSE></R>]
...

</RULES>

Execution Results

The execution system returns results and a status message within a SOAP envelope. Ordinarily, the results will be enclosed first, and then status messages will come afterwards.

Status:

PARSE_ERROR - an invalid query plan was submitted; see the error log for results.
REPLAN - plan needs incremental reoptimization. See status of operators to see what has completed.
CLOSED - plan successfully executed to completion.
EXECUTION_ERROR - error executing plan.

One status line (with terminating newline) per node in the query plan, with the following items, each separated by a space:

nodeId - the node ID in the query plan
status - execution status, one of:
- ERROR - error executing operator
- TIMEOUT - operator timed out
- OPEN - operator still not complete
- CLOSED - operator execution complete
- OUT_OF_MEMORY - operator (join or collector) ran out of memory
- TERMINATED - operator terminated by rule or execution error
- UNKNOWN - undefined state
cardinality - number of tuples output by node, as of termination of execution

A series of messages generated during parsing and execution, preceded by the header "EXECUTION_MESSAGES" and a newline. These should be ignored by the optimizer, but are provided for debugging purposes.

A termination line reading "DONE" followed by a newline. This marks the end of the results.

Sample Plan

Click here to download the sample plan. It does a self-join of the personal.xml file on data.

<?xml version="1.0"?>
<!DOCTYPE plan SYSTEM "plan.dtd">
<!--Query execution plan for Tukwila System, zives 8/31/98 -->

<!-- Header: user, requesting machine, etc. -->
<PLAN ID="Example" VERSION="1.10" REQUESTOR="127.128.129.130" RESULT="result" USER="auser">

<FRAGMENT NUM="0">
<GRAPH>
 <XML SOURCE="result"/>
 <N ID="result" OP="XELEMENT" CHILD="inner2" LABEL="outer" COUNT="2"
CARD="150"></N>
 <N ID="inner2" OP="XELEMENT" CHILD="lookup2" LABEL="firstname" COUNT="1"
CARD="150"></N>
 <N ID="lookup2" OP="XLOOKUP" CHILD="inner" CARD="150">
  <ATTR>inner.ng</ATTR>
 </N>
 <N ID="inner" OP="XELEMENT" CHILD="text" LABEL="lastname" COUNT="2"
CARD="150"></N>
 <N ID="text" OP="XLITERAL" CHILD="lookup" VALUE="myText" CARD="150"></N>
 <N ID="lookup" OP="XLOOKUP" CHILD="joins" CARD="150">
  <ATTR>joins.nf</ATTR>
 </N>
 <N ID="joins" OP="JOIN" TYPE="DOUBLE_PIPELINED" CHILDREN="sel node2"
SPACE="300" CARD="150">
  <WHERE>sel.nf = node2.nf</WHERE>
 </N>
 <N ID="sel" OP="SELECT" CHILD="node1" CARD="300">
  <WHERE>node1.nf = "Boss"</WHERE>
 </N>
 <N ID="node1" OP="XSCAN" FILE="personal.xml" VALIDATE="YES" CARD="1000">
  <PATH NAME="p">root."personnel"."person"</PATH>
  <PATH NAME="n">p."name"</PATH>
  <PATH NAME="nf">n~"family"</PATH>
  <PATH NAME="ng">n~"given"</PATH>
  <PATH NAME="w">p~"name"</PATH>
  <PATH NAME="wf">w~"family"</PATH>
  <PATH NAME="wg">w~"given"</PATH>
 </N>
 <N ID="node2" OP="XSCAN" FILE="personal2.xml" VALIDATE="YES" CARD="1000">
  <PATH NAME="p">root."personnel"."person"</PATH>
  <PATH NAME="n">p."name"</PATH>
  <PATH NAME="nf">n~"family"</PATH>
 </N>
</GRAPH>
</FRAGMENT>
</PLAN>