Join indices

Reviewer: Robert J. Tufts

Since its inception, relational database technology has been plagued with operational efficiency problems for large amounts of data and for complex queries. Much of the operational inefficiency can be attributed to the so-called 80-20 rule (80 percent of the processing is done on 20 percent of the data). Conventional (business) database management systems take advantage of this rule by using indices, linked lists, and built-in data relationships to optimize 80 percent of normal processing. Relational DBMSs, however, have not been able to do this because such optimizing shortcuts violate the mathematical foundation of relational technology and lead to an infinite number of “special case” implementation headaches. Because of join indices, this may not be the case any longer. In this paper, Valduriez proposes a strong argument and the mathematical foundation for including join indices into relational database technology. Join indices will definitely speed up almost all relational database processing. A join index is a binary relation that ties together two other relations into a bidirectional parent-child relationship. In effect, join indices can be used to predefine tree and network data relationships for the most important and/or most often used joins. Join indices are small (containing only two attributes), can be sorted and clustered easily, and can be implemented using inverted indices for secondary key access. As such, they form a tremendous acceleration mechanism for optimizing joins. The basic purpose of this paper is to propose an efficient implementation of join indices, give algorithms for joins and updates, and show the superior performance that join indices give to complex queries. The author admirably fulfills this purpose with a well-written, easily-understood tutorial. The paper contains good examples to explain each algorithm, rigorous proofs of most formulas, and graphs showing performance times against the University of Wisconsin benchmarks. The author concludes that join indices should be employed whenever possible in the implementation of relational DBMSs. The best feature of the presentation is the reference to “real world” operational problems and how join indices provide similar benefits to relational systems that inverted indices, clustered indices, B+ trees, and linked lists provide to CODASYL and hierarchical DBMSs. Perhaps the only shortcoming is the limited amount of performance data plotted against clock times. This would have been a major selling point when compared against other techniques using the Wisconsin benchmarks. The author provides performance statistics relative to the hybrid hash technique and also mentions that additional performance measurements are being conducted. The length of the paper is about right for the discussion given, and the references are up to date. The writing style is aimed at a level such that those with only a few years of experience in relational systems can quickly grasp the concepts. It also contains enough technical discussions to whet the appetite of the most ardent researcher. Overall, this outstanding paper will certainly become a classic reference for relational DBMS vendors, professionals, and researchers in the years to come. I fully expect the concept of join indices to be implemented in most commercially available packages in the near future.