Database Reference
In-Depth Information
concluSIon And outlook
family of stateful operators are aggregation func-
tions.Arasu and Widom (2004) present techniques
for efficient resource sharing in computation of
aggregation functions. However, here we concen-
trate on sharing of join processing.
Usually in query planning, selections are
pushed down under joins so as to reduce the
amount of tuples that must be processed by the
join operator. In multi-query processing, it may
instead be useful to do the opposite, that is, to pull
up selection predicates over joins so as to reuse
join results for multiple queries with different
selection predicates. Obviously, it is best to pull
down as many selection predicates as possible.
In a DSMS, however, due to windowing it is
not uncommon that simply pulling up the other
predicates produces highly memory- and CPU-
inefficient query plans. Reusing without adapta-
tion view selection or multi-query optimization
algorithms means to assume all window definitions
are identical. However, window definition may
only intersect or even be disjoint. In that case the
supposedly common subexpressions may not be
common at all.
To overcome this problem, Wang et al. (2006)
present a way to push down every selection
predicate as far down as possible by cutting
the windows into pieces and placing selection
operators in between. The windows of a join
operator's input streams are cut into slices. The
slices are handled by distinct join operators that
are pipelined such that each operator contributes
join results to the queries whose windows end with
the corresponding slice. Tuples that do not match
the window slice are pipelined to the subsequent
join operator. Two algorithms are presented, one
to produce a memory-optimal and one to produce
a CPU-optimal query plan for the join.
In fact, both, multi-query optimization or view
selection as well as efficient handling of window
definitions are required to produce efficient
joint query plans for a workload of continuous
queries.
In this chapter we presented a comprehensive
survey on view management and data stream
management systems. View maintenance and
view selection are of particular importance in
data warehouse systems, since decision support
requires complex analytical queries. Whereas
view maintenance addresses efficient methods for
updating views if their base relations are changed,
view selection is the problem of choosing a set of
views to be materialized in order to minimize a
cost function. View selection must carefully trade
off query response time, storage space, and view
maintenance costs.
Data stream management systems deal with
new query planning and processing requirements
in systems generating tremendous amounts of
data that can only be processed once due to high
arrival rates of tuples. Typical applications again
need to pose analytical queries over these streams.
There are special challenges to be solved, such
as dealing with the new data models containing
sliding windows or efficiently creating synopses of
data. Other issues are related to existing problems.
Continuous query planning is highly related to
multi-query optimization and view selection as the
high performance requirements suggest to share
computation and resources in query processing.
On the other hand, continuous query processing
is related to view maintenance.
The relatively new field of stream data man-
agement offers many opportunities for research.
Resource sharing through joint query planning
needs further work. In particular adaptive query
planning for continuous queries is a requirement
since the statistics underlying query plans may
change during execution. As we have seen in the
context of the state-slice operator, query plans
must also deal with the new issues arising from
window models.
View maintenance and processing of continu-
ous queries in data streams can both benefit from
Search WWH ::
Custom Search