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.

  @inproceedings{sigmod08sereni,
    author="Damien Sereni and Pavel Avgustinov and Oege de Moor",
    title="Adding Magic to an Optimising Datalog Compiler",
    booktitle="Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data",
    editor="Dennis Shasha",
    month="June",
    year="2008"}