Join ordering for constraint handling rules
Leslie De Koninck, Jon Sneyers · Lirias · 2007
Abstract. Join ordering is the problem of finding cost optimal execution plans for matching multi-headed rules. In the context of Constraint Handling Rules, this topic has received limited attention so far, even though it is of great importance for efficient CHR execution. We present a formal cost model for joins and investigate the possibility of join optimization at runtime. We propose some heuristic approximations of the parameters of this cost model, for both the static and dynamic case. We discuss an O(n log n) optimization algorithm for the special case of acyclic join graphs. However, in general, join order optimization is an NP-complete problem. Finally, we identify some classes of cyclic join graphs that can be reduced to acyclic ones. 1 Introduction Constraint Handling Rules (CHR) [4] is a high-level language extension basedon multi-headed guarded committed-choice rewrite rules. While originally designed for the implementation of constraint solvers, CHR is increasingly used asa general purpose programming language. Much work has been devoted to the optimized compilation of CHR [1, 5, 10]. A crucial aspect of CHR compilationis finding matching rules efficiently. Given an active constraint, searching for matching partner constraints corresponds to joining relations-- a well-studiedtopic in the context of databases [8, 9, 12-14]. The performance of join methods depends on indexing and join ordering. In the context of CHR, join ordering has been discussed in [1, 5]. In that work,only static (compile-time) information is used in determining the optimal join