Predicate transformation and factoring

Predicate transformation and factoring improves the number of choices available to the optimizer. It adds clauses that can be optimized to a query by extracting clauses from blocks of predicates linked with or into clauses linked by and. These additional optimized clauses mean that there are more access paths available for query execution. The original or predicates are retained to ensure query correctness.

During predicate transformation:

  1. Simple predicates (joins, search arguments, and in lists) that are an exact match in each or clause are extracted. In the sample query, this clause matches exactly in each block, so it is extracted:

     t.pub_id = p.pub_id

    between clauses are converted to greater-than-or-equal and less-than-or-equal clauses before predicate transformation. The sample query above uses between 15 in both query blocks (though the end ranges are different). The equivalent clause is extracted by step 1:

    price >=15
  2. Search arguments on the same table are extracted; all terms that reference the same table are treated as a single predicate during expansion. Both type and price are columns in the titles table, so the extracted clauses are:

    (type = "travel" and price >=15 and price <= 30)
    (type = "business" and price >= 15 and price <= 50)
  3. in lists and or clauses are extracted. If there are multiple in lists for a table within one of the blocks, only the first is extracted. The extracted lists for the sample query are:

     p.pub_id in ("P220", "P583", "P780")
     p.pub_id in ("P651", "P066", "P629")
  4. These steps can overlap and extract the same clause, so any duplicates are eliminated.

  5. Each generated term is examined to determine whether it can be used as an optimized search argument or a join clause. Only those terms that are useful in query optimization are retained.

  6. The additional clauses are added to the existing query clauses that were specified by the user.