Internal Language Transformations
Page 3 of 8

Transitive Closure

The transitive property of numbers states that if A = B and B = C, then A = C.

Cloudscape applies this property to query predicates to add additional predicates to the query in order to give the optimizer more information. This process is called transitive closure. There are two types of transitive closure:

  • transitive closure on join clauses

    Applied first, if applicable

  • transitive closure on search clauses

Transitive Closure on Join Clauses

When a join statement selects from three or more tables, Cloudscape analyzes any equijoin predicates between simple column references within each query block and adds additional equijoin predicates where possible if they do not currently exist. For example, Cloudscape transforms the following query:

SELECT * FROM Groups, HotelBookings, FlightBookings
WHERE Groups.group_id = HotelBookings.group_id
AND HotelBookings.group_id = FlightBookings.group_id

into the following:

SELECT * FROM Groups, HotelBookings, FlightBookings
WHERE Groups.group_id = HotelBookings.group_id
AND HotelBookings.group_id = FlightBookings.group_id
AND Groups.group_id = FlightBookings.group_id

On the other hand, the optimizer knows that one of these equijoin predicates is redundant and will throw out the one that is least useful for optimization.

Transitive Closure on Search Clauses

Cloudscape applies transitive closure on search clauses after transitive closure on join clauses. For each sargable predicate where a simple column reference is compared with a constant (or the IS NULL and IS NOT NULL operators), Cloudscape looks for an equijoin predicate between the simple column reference and a simple column reference from another table in the same query block. For each such equijoin predicate, Cloudscape then searches for a similar comparison (the same operator) between the column from the other table and the same constant. Cloudscape adds a new predicate if no such predicate is found.

Cloudscape performs all other possible transformations on the predicates (described in Predicate Transformations) before applying transitive closure on search clauses.

For example, given the following statement:

SELECT * FROM HotelBookings, FlightBookings
WHERE HotelBookings.group_id = FlightBookings.group_id
AND HotelBookings.group_id BETWEEN 1 AND 3
AND HotelBookings.group_id <> 2
AND FlightBookings.group_id <> 4

Cloudscape first performs any other transformations:

  • the BETWEEN transformation on the second predicate:

    AND HotelBookings.group_id >= 1
    AND HotelBookings.group_id <= 3

Cloudscape then performs the transitive closure:

SELECT * FROM HotelBookings, FlightBookings
WHERE HotelBookings.group_id = FlightBookings.group_id
AND HotelBookings.group_id >= 1
AND HotelBookings.group_id <= 3
AND HotelBookings.group_id <> 2
AND HotelBookings.group_id <> 4
AND FlightBookings.group_id >= 1
AND FlightBookings.group_id <= 3
AND FlightBookings.group_id <> 2
AND FlightBookings.group_id <> 4

When a sargable predicate uses the = operator, Cloudscape can remove all equijoin predicates comparing that column reference to another simple column reference from the same query block as part of applying transitive closure, because the equijoin predicate is now redundant, whether or not a new predicate was added. For example:

SELECT * FROM HotelBookings, FlightBookings
WHERE HotelBookings.group_id = FlightBookings.group_id
AND HotelBookings.group_id = 1

becomes (and is equivalent to)

SELECT * FROM HotelBookings, FlightBookings
WHERE FlightBookings.group_id = 1
AND HotelBookings.group_id = 1

The elimination of redundant predicates gives the optimizer more accurate selectivity information and improves performance at execution time.