Adding magic to an optimising datalog compiler

ABSTRACT

The magic-sets transformation is a useful technique for dramatically improving the performance of complex queries, but it has been observed that this transformation can also drastically reduce the performance of some queries. Successful implementations of magic in previous work require integration with the database optimiser to make appropriate decisions to guide the transformation (the sideways information passing strategy, or SIPS).

This paper reports on the addition of the magic-sets transformation to a fully automatic optimising compiler from Datalog to SQL with no support from the database optimiser. We present an algorithm for making a good choice of SIPS using heuristics based on the sizes of relations. To achieve this, we define an abstract interpretation of Datalog programs to estimate the sizes of relations in the program.

The effectiveness of our technique is evaluated over a substantial set of over a hundred queries, and in the context of the other optimisations performed by our compiler. It is shown that using the SIPS chosen by our algorithm, query performance is often significantly improved, as expected, but more importantly performance is never significantly degraded on queries that cannot benefit from magic.

REFERENCES

• 1: I. Balbin , G. S. Port , K. Ramamohanarao , K. Meenakshi, Efficient bottom-up computation of queries on stratified databases, Journal of Logic Programming, v.11 n.3-4, p.295-344, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90030-S]
• 2: François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In SIGMOD Conference, pages 1--16. ACM, 1986.
• 3: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 4: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 5: Oege de Moor , Damien Sereni , Pavel Avgustinov , Mathieu Verbaere, Type inference for datalog and its application to query optimisation, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376957]
• 6: Oege de Moor, Damien Sereni, Mathieu Verbaere, Elnar Hajiyev, Pavel Avgustinov, Torbjörn Ekman, Neil Ongkingco, and Julian Tibble. .QL: Object-oriented queries made easy. In Generative and Transformational Techniques for Software Engineering (GTTSE '07), 2007.
• 7: Jack Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards -- B. Mathematics and Mathematical Physics, 71B(4):233--240, October-December 1967.
• 8: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 9: Leonidas Georgiadis, Arborescence optimization problems solvable by Edmonds' algorithm, Theoretical Computer Science, v.301 n.1-3, p.427-437, 14 May 2003 [doi>10.1016/S0304-3975(02)00888-5]
• 10: H2 Database Engine. Website with documentation and downloads. http://www.h2database.com, 2007.
• 11: Elnar Hajiyev, Mathieu Verbaere, and Oege de Moor. CodeQuest: scalable source code queries with Datalog. In Proceedings of ECOOP, volume 4067 of LNCS, pages 2--27. Springer, 2006.
• 12: Jakob Henriksson and Jan Małuszy\’nski. Static type-checking of datalog with ontologies. In Principles and Practice of Web Reasoning, volume 3208 of LNCS, pages 76--89, 2004.
• 13: JFreeChart. Website with documentation and downloads. http://www.jfree.org/jfreechart/, 2007.
• 14: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 15: Monica S. Lam , John Whaley , V. Benjamin Livshits , Michael C. Martin , Dzintars Avots , Michael Carbin , Christopher Unkel, Context-sensitive program analysis as database queries, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065169]
• 16: R. J. Lipton , J. F. Naughton, Estimating the size of generalized transitive closures, Proceedings of the 15th international conference on Very large data bases, p.165-171, July 1989, Amsterdam, The Netherlands
• 17: Microsoft. SQL server website with documentation and downloads. http://www.microsoft.com/sql, 2007.
• 18: Katherine A. Morris, An algorithm for ordering subgoals in NAIL?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.82-88, March 1988, Austin, Texas, United States [doi>10.1145/308386.308419]
• 19: I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.247-258, May 23-26, 1990, Atlantic City, New Jersey, United States
• 20: Inderpal Singh Mumick , Hamid Pirahesh, Implementation of magic-sets in a relational database system, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.103-114, May 24-27, 1994, Minneapolis, Minnesota, United States
• 21: PostgreSQL. Documentation and downloads. http://www.postgresql.org, 2007.
• 22: Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan , Praveen Seshadri, The CORAL deductive system, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.2, April 1994
• 23: Semmle Ltd. Collection of .QL queries used in benchmarks, 2007. http://semmle.com/benchmarks/defaultqueries.tar.gz.
• 24: Semmle Ltd. Company website with free downloads, documentation, and discussion forums. http://semmle.com, 2007.
• 25: Semmle Ltd. Database schema with annotations, 2007. http://semmle.com/benchmarks/semmlecode.dbscheme.
• 26: Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Cost-based optimization for magic: algebra and implementation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.435-446, June 04-06, 1996, Montreal, Quebec, Canada
• 27: A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
• 28: John Whaley, Dzintars Avots, Michael Carbin, and Monica S. Lam. Using datalog and binary decision diagrams for program analysis. In Proceedings of APLAS, volume 3780 of LNCS, pages 97--118. Springer, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Performance

Keywords:
datalog, magic sets, query optimisation