Scalable computation of acyclic joins

ABSTRACT

The join operation of relational algebra is a cornerstone of relational database systems. Computing the join of several relations is NP-hard in general, whereas special (and typical) cases are tractable. This paper considers joins having an acyclic join graph, for which current methods initially apply a full reducer to efficiently eliminate tuples that will not contribute to the result of the join. From a worst-case perspective, previous algorithms for computing an acyclic join of k fully reduced relations, occupying a total of n≥k blocks on disk, use Ω((n+z)k) I/Os, where z is the size of the join result in blocks.In this paper we show how to compute the join in a time bound that is within a constant factor of the cost of running a full reducer plus sorting the output. For a broad class of acyclic join graphs this is O(sort(n+z)) I/Os, removing the dependence on k from previous bounds. Traditional methods decompose the join into a number of binary joins, which are then carried out one by one. Departing from this approach, our technique is based on computing the size of certain subsets of the result, and using these sizes to compute the location(s) of each data item in the result.Finally, as an initial study of cyclic joins in the I/O model, we show how to compute a join whose join graph is a 3-cycle, in O(n²/m+sort(n+z)) I/Os, where m is the number of blocks in internal memory.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: I. Baran, E. D. Demaine, and M. Patrascu. Subquadratic algorithms for 3SUM. In Proceedings of WADS, volume 3608 of Lecture Notes in Computer Science, pages 409--421, 2005.
• 3: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 4: Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564699]
• 5: Joseph M. Hellerstein , Michael Stonebraker, Readings in Database Systems: Fourth Edition, The MIT Press, 2005
• 6: Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
• 7: Y. E. Ioannidis. Query optimization. In Computer Science Handbook, Second Edition, chapter 55. Chapman & Hall/CRC, 2004.
• 8: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
• 9: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• 10: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 11: Sakti Pramanik , David Vineyard, Optimizing join queries in distributed databases, Proc. of the seventh conference on Foundations of software technology and theoretical computer science, p.282-304, December 1987, Pune, India
• 12: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 13: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 14: D. E. Willard. An algorithm for handling many relational calculus queries efficiently. J. Comput. System Sci., 65(2):295--331, 2002.
• 15: M. Yannakakis. Algorithms for acyclic database schemes. In 7th International Conference on Very Large Data Bases (VLDB), pages 82--94. IEEE, 1981.
• 16: C. T. Yu and M. Z. Ozsoyoglu. An algorithm for tree-query membership of a distributed query. In Proceedings of Computer Software and Applications Conference, pages 306--312. IEEE, 1979.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
acyclic join, algorithm, external memory, relational algebra