Constant propagation versus join reordering in Datalog

Abstract

Constant propagation and join reordering are two standard optimization techniques used for Datalog programs. These techniques have typically been studied independently of one another. However, in order to achieve constant propagation it is sometimes necessary to impose a certain join ordering on a given program. In the worst case this ordering may result in efficiencies which overcome the benefit of constant propagation. Thus the goal of constant propagation should not necessarily be pursued to the exclusion of all else. We study this problem in the context of GraphLog, a visual language whose queries are graphical notations which are translated into Datalog. We study two translation schemes from GraphLog to Datalog, one which always achieves constant propagation and another which does not. We show that each translation can significantly outperform the other. We demonstrate this by both measuring execution times using actual application data, and by providing analytical formulae to explain the trade-off between constant propagation and join reordering.

Most of this work was done while the author was on sabbatical at the University of Toronto.