decompositions ensure that the root node does not contain
any unit decompositions, so it is always possible to represent the empty relation.
To insert a tuple t into an instance d of a decomposition
dˆ, for each node v: B C in the decomposition we need
to find or create a node instance vs in the decomposition
instance, where s is tuple t restricted to columns B. For each
edge in the decomposition we also need to find or create an
instance of the edge connecting the corresponding pair of
node instances. We perform insertion over the nodes of a
decomposition in topologically sorted order. For each node
v we locate the existing node instance vs corresponding to
tuple t, if any. If no such vs exists, we create one, inserting
vs into any data structures that link it to its ancestors. For
example, inserting the tuple ns: 2, pid: 1, state: S, cpu: 5 into
the decomposition instance shown in Figure 3(a) yields the
state shown in Figure 3(b).
We next consider the dremove and dupdate operations.
Operation dremove removes tuples matching tuple s from
an instance d of decomposition dˆ.
To remove tuples matching a tuple t, we compute a cut
of the decomposition between those nodes that can only be
part of the representation of tuples matching t, and those
nodes that may form part of the representation of tuples
that do not match t. We then break any edge instances
crossing the cut. To find the edge instances to break we
can reuse the query planner. Once all such references are
removed, the instances of nodes in Y are unreachable from
the root of the instance and can be deallocated. We can
also clean up any map nodes in X that are now devoid of
Operation dupdate updates tuples matching s using values from u in an instance d of decomposition dˆ. Semantically,
updates are a removal followed by an insertion. In the implementation we can reuse the nodes and edges discarded in
the removal in the subsequent insertion—that is, we can
perform the update in place.
4. 3. soundness of relational operations
Finally we show that the operations on decompositions
faithfully implement their relational specifications.
Theorem 2. Let C be a set of columns, a set of FDs, and dˆ
figure 3. example of insertion and removal. inserting the tuple t =
〈ns: 2, pid: 1, state: S, cpu: 5〉 into instance (a) produces instance
(b); conversely removing tuple t from (b) produces (a). Differences
between the instances are shown using dashed lines.
;cpu: 7ñ ;cpu: 4ñ
w1 1 w2 1
1, 1 2, 1
;cpu: 7ñ ;cpu: 4ñ
w1 1 w21
a decomposition adequate for C and . Suppose a sequence
of insert, update and remove operators starting from the
empty relation produce a relation r, and each intermediate
relation satisfies FDs . Then the corresponding sequence of
dinsert, dupdate, and dremove operators given dempty dˆ
as input produce an instance d such that a(d) = r.
Thus far we have concentrated on the problem of compiling relational operations for a particular decomposition of
a relation. However, a programmer may not know, or may
not want to invest time in finding the best possible decomposition for a relation. We have therefore constructed an
auto-tuner that, given a program written to the relational
interface, attempts to infer the best possible decomposition
for that program.
The auto-tuner takes as input a benchmark program
that produces as output a cost value (e.g., execution time),
together with the name of a relation to optimize. The auto-tuner then exhaustively constructs all decompositions for
that relation up to a given bound on the number of edges,
recompiles and runs the benchmark program for each
decomposition, and returns a list of decompositions sorted
by increasing cost. We do not make any assumptions about
the cost metric—any value of interest such as execution time
or memory consumption may be used.
We have implemented a compiler, named RelC, that takes
as input a relational specification and a decomposition,
and emits C++ code implementing the relation. We evaluate our compiler using micro-benchmarks and three real-world systems. The micro-benchmarks (Section 6. 1) show
that different decompositions have dramatically different
performance characteristics. Since our compiler generates
C++ code, it is easy to incorporate synthesized data representations into existing systems. We apply synthesis to three
existing systems (Section 6. 2), namely a Web server, a network flow accounting daemon, and a map viewer, and show
that synthesis leads to code that is simultaneously simpler,
correct by construction, and comparable in performance to
the code it replaces.
We chose C++ because it allows low-level control over
memory layout, has a powerful template system, and has
widely used libraries of data structures from which we
can draw. Data structure primitives are implemented as
C++ template classes that implement a common associative container API. The set of data structures can easily
be extended by writing additional templates and providing the compiler some basic information about the data
structure’s capabilities. We have implemented a library
of data structures that wrap code from the C++ Standard
Template Library and the Boost Library, namely doubly
binary trees (std::map, boost::intrusive::set
hash-tables (boost::unordered_map), and vectors
(std::vector). The library includes both nonintru-sive containers, in which elements are represented
out-of-line as pointers, and intrusive containers, in