| Abstract:
"plan diagram" is a pictorial enumeration of the execution plan
choices of a database query optimizer over the relational selectivity
space. We have recently developed a tool, called Picasso, for
automatically generating plan diagrams. In this talk, we present
and analyze representative plan diagrams produced by Picasso on a
suite of popular commercial query optimizers for queries based on the
TPC-H benchmark. These diagrams, which often appear similar to
cubist
paintings, provide a variety of interesting insights, including that
current optimizers make extremely fine-grained plan choices, which
may
often be supplanted by less efficient options without substantively
affecting the quality; that the plan optimality regions may have
highly
intricate patterns and irregular boundaries, indicating strongly
non-linear cost models; that non-monotonic cost behavior exists
where increasing result cardinalities decrease the estimated cost;
and, that the basic assumptions underlying the research literature on
parametric query optimization often do not hold in practice. The talk
will conclude with a discussion on the implications of these results
for next-generation database query optimizers.
|