Query Processing: A Systems View
2010-06-17 09:24:21| 分类:
dbms
| 标签:
|举报
|字号大中小 订阅
Physical (execution) plan
A complex query may involve multiple tables and various query processing processing algorithms
E.g., table scan, index nested-loop join, sort-merge join, hash-based duplicate elimination…
A physical plan for a query tells the DBMS query processor how to execute the query
A tree of physical plan operators
Each operator implements a query processing algorithm
Each operator accepts a number of input tables/streams and produces a single output table/stream
Physical plan execution
How are intermediate results passed from child operators to parent operators?
1).Temporary files
Compute the tree bottom-up
Children write intermediate results to temporary files
Parents read temporary files
2).Iterators
Do not materialize intermediate results
Children pipeline their results to parents
Iterator interface
Every physical operator maintains its own execution state and implements the following methods:
1). open():
Initialize state and get ready for processing
2). getNext():
Return the next tuple in the result (or a null pointer if there are no more tuples);
adjust state to allow subsequent tuples to be obtained
3). close():
Clean up
An iterator for nested-loop join
R: An iterator for the left subtree
S: An iterator for the right subtree
1).open()
R.open(); S.open(); r = R.getNext();
2).getNext()
do {
s = S.getNext();
if (s == null) {
S.close(); S.open(); s = S.getNext(); if (s == null) return null;
r = R.getNext(); if (r == null) return null;
}
} until (r joins with s);
return rs;
3). close()
R.close(); S.close();
Blocking vs. non-blocking iterators
1).A blocking iterator must call getNext() exhaustively (or nearly exhaustively) on its children
before returning its first output tuple
Examples: sort, aggregation
2).A non-blocking iterator expects to make only a few getNext() calls on its children before returning its first (or next) output tuple
Examples: filter, merge join with sorted inputs
Reference: Query Processing: A Systems View (CPS 216 Advanced Database Systems)
评论这张
转发至微博
转发至微博
评论