Table 2: Costs of Data Access for Boolean Queries with Ranges

This table considers the case when the second clause is a range clause, e.g., (K2 > KV2). We assume that v key values and N records satisfy the query, M of which satisfy the K1 clause.

Notes:

1. Again, inverted lists which retain (K,KV) pairs can use the multilist approach for intersection or difference queries.
2. If the same records have multiple K2 keys, the multilist algorithm may operate more efficiently.