Database Management Systems

by Raghu Ramakrishnan and Johannes Gehrke

[Database Management Systems (3rd Edition)] [The Minibase Distribution] [Minibase Overview] [Minibase Modules] [Minibase Terms and Agreement] [Minibase History] [Minibase Documentation]

 

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