Adobe Inc.
QUERY PROCESSING USING HYBRID INVERTED INDEX OF PREDICATES

Abstract:

A query processing system generates and employs a hybrid inverted index of predicates for predicate statement evaluation. The query processing system converts a collection of predicate statements to two parts, a matrix and a set of reduced predicate statements. The query processing system then generates a hybrid inverted index that maps values for variables to predicates from the matrix and the reduced predicate statements that evaluate to true for corresponding values. When querying data, the query processing system performs a lookup on the hybrid inverted index to identify predicates from the matrix and reduced predicate statements that evaluate to true for values of variables for the data. The query processing system identifies predicate statements that evaluate to true by evaluating the matrix and reduced predicate statements using treating predicates identified from the hybrid inverted index as true.