Introduction to query optimization

We can see that the cost of a query depends greatly on both the scheme used, and on the particular operators in the query. Sometimes, a query can be rearranged to lower the time or the space needed. For example,

            (K1 = KV1) and ((K2 = KV2) or (K3 = KV3)))

requires determination and storage of a large intermediate result (the "or" part), while

            ((K1 = KV1) and (K2 = KV2)) or ((K1 = KV1) and (K2 = KV2))

although it requires access to the inverted list for (K1,KV1) twice, will tend to be significantly less expensive. Another possible optimization is to group operations of the same type (unions, intersections) to be solved by a single multi-way merge.