Optimized exclusion filters for multistage filter processing in queries

Patent metadata

Field	Value
Publication number	US-2016299947-A1
Application number	US-201514681282-A
Country	US
Kind code	A1
Filing date	Apr 8, 2015
Priority date	Apr 8, 2015
Publication date	Oct 13, 2016
Grant date	—

Abstract

A computer-implemented method for querying a data source using an optimized exclusion filter expression created from a full filter expression is described. The method includes receiving one or more queries defined by the full filter expression, wherein the one or more queries are for obtaining an output from the data source; performing a reduction on the full filter expression to determine the optimized exclusion filter expression; applying the optimized exclusion filter expression in the data source to exclude data; and applying the full filter expression to data not excluded by the optimized exclusion filter expression.

First claim

What is claimed is:

1 . A computer-implemented method for querying a data source using an optimized exclusion filter expression created from a full filter expression, the method comprising:
receiving one or more queries defined by the full filter expression, wherein the one or more queries are for obtaining an output from the data source; performing a reduction on the full filter expression to determine the optimized exclusion filter expression; applying the optimized exclusion filter expression in the data source to exclude data; and applying the full filter expression to data not excluded by the optimized exclusion filter expression.

2 . The computer-implemented method of claim 1 , wherein if a result of the optimized exclusion filter expression is FALSE, then the full filter expression also yields a result of FALSE; and
wherein if the result of the optimized exclusion filter expression is TRUE, then the full filter expression does not have a definitive result and must be evaluated.

3 . The computer-implemented method of claim 1 , wherein the one or more queries comprise two separate queries that are combined in a same optimized exclusion filter expression for the applying the optimized exclusion filter, and evaluated separately for the applying the full filter expression.

4 . The computer-implemented method of claim 1 , wherein the full filter expression and the optimized exclusion filter expression are each a combination of predicates and logical operators comprising AND, OR, and NOT, each of the predicates is an expression that evaluates to TRUE or FALSE, and each of the predicates has an associated cost which is used in the reduction.

5 . The computer-implemented method of claim 4 , wherein the reduction comprises a combination of expanding NOT expressions, setting high cost predicates to TRUE, and adjusting an associated expression tree based thereon.

6 . The computer-implemented method of claim 4 , wherein the data source comprises a plurality of physically separate databases, and the optimized exclusion filter expression is determined for each individual separate database.

7 . The computer-implemented method of claim 4 , wherein the reduction is performed iteratively by reducing threshold costs to remove more predicates and reduce the overall cost, to determine a minimization of the optimized exclusion filter expression.

8 . The computer-implemented method of claim 4 , wherein the associated expression tree is adjusted by modifying nodes where the high cost predicates are set to TRUE.

9 . A system configured to query a data source using an optimized exclusion filter expression created from a full filter expression, the system comprising:
a network interface, the data store, and a processor, each communicatively coupled to one another; and memory storing instructions that, when executed, cause the processor to:
receive one or more queries defined by the full filter expression, wherein the one or more queries are for obtaining an output from the data source;
perform a reduction on the full filter expression to determine the optimized exclusion filter expression;
apply the optimized exclusion filter expression in the data source to exclude data; and
apply the full filter expression to data not excluded by the optimized exclusion filter expression.

10 . The system of claim 9 , wherein if a result of the optimized exclusion filter expression is FALSE, then the full filter expression also yields a result of FALSE; and
wherein if the result of the optimized exclusion filter expression is TRUE, then the full filter expression does not have a definitive result and must be evaluated.

11 . The system of claim 9 , wherein the one or more queries comprise two separate queries that are combined in a same optimized exclusion filter expression to apply the optimized exclusion filter, and evaluated separately to apply the full filter expression.

12 . The system of claim 9 , wherein the full filter expression and the optimized exclusion filter expression are each a combination of predicates and logical operators comprising AND, OR, and NOT, each of the predicates is an expression that evaluates to TRUE or FALSE, and each of the predicates has an associated cost which is used in the reduction.

13 . The system of claim 12 , wherein the reduction comprises a combination of expanding NOT expressions, setting high cost predicates to TRUE, and adjusting an associated expression tree based thereon.

14 . The system of claim 12 , wherein the data source comprises a plurality of physically separate databases, and the optimized exclusion filter expression is determined for each individual separate database.

15 . The system of claim 12 , wherein the reduction is performed iteratively by reducing threshold costs to remove more predicates and reduce the overall cost, to determine a minimization of the optimized exclusion filter expression.

16 . The system of claim 12 , wherein the associated expression tree is adjusted by modifying nodes where the high cost predicates are set to TRUE.

17 . Software stored in a non-transitory computer readable medium and comprising instructions executable by a processor, and in response to such execution causes the processor to perform operations comprising:
receiving one or more queries defined by the full filter expression, wherein the one or more queries are for obtaining an output from the data source; performing a reduction on the full filter expression to determine the optimized exclusion filter expression; applying the optimized exclusion filter expression in the data source to exclude data; and applying the full filter expression to data not excluded by the optimized exclusion filter expression.

18 . The software stored in a non-transitory computer readable medium of claim 17 , wherein if a result of the optimized exclusion filter expression is FALSE, then the full filter expression also yields a result of FALSE; and
wherein if the result of the optimized exclusion filter expression is TRUE, then the full filter expression does not have a definitive result and must be evaluated.

19 . The software stored in a non-transitory computer readable medium of claim 17 , wherein the one or more queries comprise two separate queries that are combined in a same optimized exclusion filter expression for the applying the optimized exclusion filter, and evaluated separately for the applying the full filter expression.

20 . The software stored in a non-transitory computer readable medium of claim 17 , wherein the full filter expression and the optimized exclusion filter expression are each a combination of predicates and logical operators comprising AND, OR, and NOT, each of the predicates is an expression that evaluates to TRUE or FALSE, and each of the predicates has an associated cost which is used in the reduction.

Assignees

• Pangeni Sushil
• Balaiah Chakkaravarthy Periyasamy
• BATHLA Abhishek
• Zscaler Inc

Inventors

• Pangeni Sushil
• Balaiah Chakkaravarthy Periyasamy
• BATHLA Abhishek

Classifications

• G06F16/24537 Primary

  of operators · CPC title

• G06F16/24545

  Selectivity estimation or determination · CPC title

• G06F17/30867

  Physics · mapped topic

• G06F17/30454 Primary

  Physics · mapped topic

• G06F17/30469

  Physics · mapped topic