A mutant query plan (MQP) is an XML serialization of a query plan graph,
consisting of regular query operators, plus verbatim pieces of XML data and
references to resources. A mutant query plan can reference a
resource using an abstract, location independent resource
name (URN), or a concrete resource location (URL). Every
mutant query plan is tagged with a target, the network
address of the client interested in the query results.
We can use mutant query plans to represent a distributed query at
every stage of its processing: from regular query plans, containing
just query operators and resource references, to query results,
containing just data, and everything in between.
When a server receives an MQP it partially evaluates as much of
the plan as it can (or is willing to), producing a new,
mutated, plan and routes it to some other server that can
continue processing. The server that eventually evaluates the whole
query routes it back to the target.
Server can mutate a plan in two ways: resolution, and
reduction. In resolution, the server resolves a URN into a
URL, or a URL to its data. In reduction, the server evaluates a
subplan of the query, and inserts the results in its place.
We believe that MQPs offer a more viable solution for large,
heterogeneous, and autonomous distributed systems, than the
traditional, coordinator-based approach.Since mutant query plans are
alternatively optimized and executed on one server at a time, we lose
the benefits of pipelined execution, but gain in flexibility and
autonomy. Mutant query plans allow each server to optimize the parts
of a query it will run independently, and minimize coordination