This thesis presents the design and implementation of a database query
processing engine that is optimized for access to tertiary memory
devices.  Tertiary memory devices provide a cost-effective solution for
handling the on-going information explosion.  While cheap and
convenient, they pose new optimization challenges.  Not only are
tertiary devices three orders of magnitude slower than disks, but they
also have a highly non-uniform access latency.  Therefore, it is crucial
to carefully reduce and reorder I/O on tertiary memory using effective
query scheduling, batching, caching, prefetching and data placement
techniques.

We make two key modifications to an existing query processing
architecture to support such aggressive optimizations: The first is a
scheduler that uses system-wide information to make query scheduling,
caching and device scheduling decisions in an integrated manner.  The
second is a reorderable executor that can process each query plan in the
order in which data is made available by the scheduler rather than
demand and process data in a fixed order, as in most conventional query
execution engines.  The two together provide unprecedented opportunities
for optimizing accesses to tertiary memory.  We have extended the
Postgres database system with these optimizations.
Measurements on the prototype yielded almost an order of magnitude
improvement on the Sequoia benchmark and on queries over synthetic
datasets.

We explore data placement techniques on tertiary memory devices to
enable better clustering. This thesis concentrates on data placement
issues for large multidimensional arrays --- one of the largest
contributors of data volume in many database systems.  We discuss
four techniques for doing this: (1) storing the array in
multidimensional ``chunks'' to minimize the number of blocks fetched,
(2) reordering the chunked array to minimize seek distance between
accessed blocks, (3) maintaining redundant copies of the array, each
organized for a different chunk size and ordering and (4) partitioning
the array onto platters of a tertiary memory device so as to minimize
the number of platter switches.  Measurements on  data obtained from
global change scientists show that accesses on arrays organized using
these techniques are often an order of magnitude faster than on the
unoptimized data.