Iterators
Introduction
Execution is guided by a
tree of ``iterators'', each of which supports a ``get-next-tuple''
interface. When an answer tuple is requested by a get-next-tuple
call on the root of the tree, similar
similar calls are generated on iterators lower in the tree.
Leaf level nodes (File Scan iterators and Index Scan iterators)
retrieve tuples from a relation,
and intermediate nodes in the tree (Join iterators)
correspond to
joins.
Selections and projections are ``piggy-backed''
onto these iterators.
Click here for diagrams of some example iterator trees.
Simple Iterator Trees
Larger Iterator Tree
Design Details
The output of one iterator can be made the input of another by using the
uniform "get_next" call.
Types of Iterators
In principle, there are several types of iterators:
- nested loops join
- sort merge join
- sorting utility
- projection
- selection
- duplicate elimination
- file scans
- index scans
However, some of these iterators are not used in Minibase. Projections and selections are actually handled by separate function calls. Also, duplicate
elimination and sorting is triggered by other iterators.
In other words, the
planner will never create a sort iterator. If it passes the appropriate
arguments to a join, for example, the join will create the sort iterator
internally.
As an example, click here to see why a
join iterator in Minibase is really three iterators in one.
Back to the Minibase Home Page
Back to the Components Page
