Output details
11 - Computer Science and Informatics
University of Oxford
Adding magic to an optimising datalog compiler
<08>
The magic-sets transformation is a powerful optimisation, but successful implementations have required integration with the database optimiser to guide the sideways information-passing strategy (SIPS). This paper reports on the addition of magic-sets to a fully automatic optimising compiler from Datalog to SQL with no support from the database optimiser. It presents an algorithm for making a good choice of SIPS using heuristics based on the sizes of relations as estimated using an abstract interpretation of Datalog programs. Evaluation over a substantial set of queries shows that our technique often improves and, more importantly, never significantly degrades query performance.