US 2021/0240706 A1 · 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.

Claims20

Dependent claims

One or more computer storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform operations, the operations comprising:

applying one or more transforms to predicates statements to generate a matrix and a set of reduced predicates statements, the matrix including conjunctive predicates or disjunctive predicates from the predicate statements, the set of reduced predicates generated by removing the conjunctive predicates or disjunctive predicates from the predicate statements added to the matrix;
and
generating a hybrid inverted index that includes a mapping of predicate values for variables to predicates from the matrix and the set of reduced predicate statements;
and
storing the hybrid inverted index, matrix, and set of reduced predicate statements, for use in evaluating the predicate statements for querying data.

2 more elements

A computerized method comprising:

receiving data with a value for each of one or more variables;
performing a lookup on a hybrid inverted index to identify predicates mapped to the value for each of the one or more variable, the predicates from a matrix and a set of reduced predicate statements generated from a set of predicate statements;
identifying one or more candidate predicate statements that can be satisfied for the input data using the matrix by treating each predicate from the matrix identified from the hybrid inverted index as true;
and
evaluating the reduced predicate statement for each of the one or more candidate predicate statements by treating each predicate from the reduced predicate statements identified from the hybrid inverted index as true.

2 more elements

Dependencies are inferred from the claim text.

Query processing using hybrid inverted index of predicates

Life of this patent

Query processing using hybrid inverted index of predicates

Life of this patent

Abstract

Claims20