A chase too far?

TLDR

The paper presents a novel query‑plan generation method that combines chasing with logical constraints, indexes, materialized views, semantic optimization, and join elimination—techniques each known to benefit query optimization. The authors aim to systematically integrate these techniques and assess how far the method can scale with increasing schema and query complexity. They implemented the approach across diverse schemas and queries and introduced a stratification technique to reduce the search space by limiting the constraints used in the (back)chase. Experiments show that semantic constraints enable non‑trivial use of indexes and materialized views, and that the method is both feasible and worthwhile.

Abstract

In a previous paper we proposed a novel method for generating alternative query plans that uses chasing (and back-chasing) with logical constraints. The method brings together use of indexes, use of materialized views, semantic optimization and join elimination (minimization). Each of these techniques is known separately to be beneficial to query optimization. The novelty of our approach is in allowing these techniques to interact systematically, eg. non-trivial use of indexes and materialized views may be enabled only by semantic constraints. We have implemented our method for a variety of schemas and queries. We examine how far we can push the method in term of complexity of both schemas and queries. We propose a technique for reducing the size of the search space by “stratifying” the sets of constraints used in the (back)chase. The experimental results demonstrate that our method is practical (i.e., feasible and worthwhile).