Databases Reference
In-Depth Information
7
Range Partitioning
The best armor is to keep out of range.
—Italian proverb
he idea is simple and powerful: divide data into ranges so that the database can
make intelligent decisions at processing time on what segments of the data to
completely ignore or completely focus on. For example, by dividing data by date
ranges (January data over here, February data over there, etc.) the database can com-
pletely focus on the ranges that are specific to incoming queries. This is another clear
variant of a nonrecursive divide-and-conquer strategy, and the operational details will
be discussed below.
Range partitioning has become such a ubiquitous notion in database design that
we had a hard time tracing back its origins—a bit like trying to discover who invented
the sailboat. To find out where the idea came from we contacted one of the world's
leading database researchers, David DeWitt. DeWitt is the John P. Morgridge Profes-
sor of Computer Science at the University of Madison at Wisconsin, author of over
100 technical papers, a member of the National Academy of Engineering, and was
named a Fellow of the AC in 1995. According to DeWitt, a graduate student named
Bob Epstein as part of his thesis proposed the idea of range partitioning for distribut-
ing tuples of tables among different nodes of a distributed database system (distrib-
uted Ingres). DeWitt was the first to apply this idea to parallel database systems as
part of the Gamma project. The paper on Gammma [DeWitt 1986] published at the
1986 VLDB conference discusses the three forms of horizontal partitioning that
T
125
