Optimization of multi-version expensive predicates

Modern query optimizers need to take into account the performance of expensive user-defined predicates. Existing research has shown how to incorporate such predicates in a traditional cost-based query optimizer. In this paper we deal with the optimization of the expensive predicates themselves, showing how their cost can be reduced by utilizing cheaper, but less accurate, versions of the predicates to pre-filter tuples. We discuss the generalized tuple handling mechanism, which processes tuples along a fixed sequence of versions, as well as adaptive approaches that either split tuple streams into groups, or make routing decisions at the individual tuple level. We identify the lower bound to the problem of evaluating a multi-version selection predicate by an ideal individualized plan (IIP), and develop an optimal generalized plan (OGP). We then show how realistic individualized or grouped schemes can produce an intermediate cost between OGP and IIP, if tuples substantially deviate from the average stream behavior. Our algorithms are tested experimentally, identifying many of the issues that arise whenever multi-version predicates are used.