Optimizations for a behavior analysis engine

Patent metadata

Field	Value
Publication number	US-10915535-B2
Application number	US-201815983404-A
Country	US
Kind code	B2
Filing date	May 18, 2018
Priority date	Jun 16, 2017
Publication date	Feb 9, 2021
Grant date	Feb 9, 2021

Abstract

Systems and methods for optimizing query execution to improve query processing by a computer are provided. A query is analyzed and translated into a logical plan. A runtime query optimizer is applied to the logical plan to identify a physical plan including operators for execution. The logical plan is translated into the physical plan. Execution of the query is scheduled according to the physical plan.

First claim

What is claimed is:

1. A computer-implemented method for optimizing query execution to improve query processing by a computer, comprising:
analyzing, by at least one processor device operatively coupled to a memory, a temporal query for querying at least one temporal relationship between at least first data and second data stored in a database based on one or more local rules stored in a local rule-base and one or more global rules stored in a global rule-base, the one or more local rules being received via a user interface and the one or more global rules being created by one or more distributed applications;
translating, by the at least one processor device, the temporal query into a logical plan;
applying, by the at least one processor device, a runtime query optimizer to the logical plan to identify a physical plan including temporal operators for execution, including designing temporal join processes to optimize execution of the temporal operators by:
extracting keys from constraints, including extracting one or more partition keys from one or more normal constraints and one or more sorting keys from one or more temporal constraints;
partitioning data into partitions using a hash-based function and shuffling the partitions based on the one or more partition keys to obtain one or more row groups;
sorting rows in each of the one or more row groups based on the one or more sorting keys to obtain sorted rows;
implementing a partition merging phase by finding matched rows among the sorted rows; and
filtering results of the partition merging phase;

translating, by the at least one processor device, the logical plan into the physical plan; and
scheduling, by the at least one processor device, execution of the query according to the physical plan.

2. The method of claim 1 , wherein the constraints further include key temporal constraints.

3. The method of claim 1 , wherein applying the runtime query optimizer to the logical plan to find the physical plan includes determining whether to implement a plan modification phase.

4. The method of claim 3 , wherein determining whether to implement the plan modification phase includes:
scheduling a first execution plan according to primitive information;
collecting samples of data;
applying operators to the samples of data to generate statistics;
generating a second execution plan based on the statistics;
comparing a ratio of a cost of the first plan to a cost of the second plan to a threshold; and
implementing the plan modification phase based on the second execution plan in response to the ratio exceeding the threshold.

5. The method of claim 4 , further comprising loading, by the at least one processor device, the data into memory and pre-partitioning, by the at least one processor device, the data in response to the scheduling of the first execution plan.

6. The method of claim 1 , wherein the temporal operators include at least one operator selected from the group consisting of: Leadto, LeadtoPair, During, Overlap, Startwith, Endwith, and Equal.

7. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform a method for optimizing query execution to improve query processing by a computer, the method comprising:
analyzing a temporal query for querying at least one temporal relationship between at least first data and second data stored in a database based on one or more local rules stored in a local rule-base and one or more global rules stored in a global rule-base, the one or more local rules being received via a user interface and the one or more global rules being created by one or more distributed applications;
translating the temporal query into a logical plan;
applying a runtime query optimizer to the logical plan to identify a physical plan including temporal operators for execution, including designing temporal join processes to optimize execution of the temporal operators by:
extracting keys from constraints, including extracting one or more partition keys from one or more normal constraints and one or more sorting keys from one or more temporal constraints;
partitioning data into partitions using a hash-based function and shuffling the partitions based on the one or more partition keys to obtain one or more row groups;
sorting rows in each of the one or more row groups based on the one or more sorting keys to obtain sorted rows;
implementing a partition merging phase by finding matched rows among the sorted rows; and
filtering results of the partition merging phase;

translating the logical plan into the physical plan; and
scheduling execution of the query according to the physical plan.

8. The computer program product of claim 7 , wherein the constraints further include key temporal constraints.

9. The computer program product of claim 7 , wherein applying the runtime query optimizer to the logical plan to find the physical plan includes determining whether to implement a plan modification phase.

10. The computer program product of claim 9 , wherein determining whether to implement the plan modification phase includes:
scheduling a first execution plan according to primitive information;
collecting samples of data;
applying operators to the samples of data to generate statistics;
generating a second execution plan based on the statistics;
comparing a ratio of a cost of the first plan to a cost of the second plan to a threshold; and
implementing the plan modification phase based on the second execution plan in response to the ratio exceeding the threshold.

11. A system for optimizing query execution to improve query processing by a computer, comprising:
at least one processor device operatively coupled to a memory and configured to:
analyze a temporal query for querying at least one temporal relationship between at least first data and second data stored in a database based on one or more local rules stored in a local rule-base and one or more global rules stored in a global rule-base, the one or more local rules being received via a user interface and the one or more global rules being created by one or more distributed applications;
translate the temporal query into a logical plan;
apply a runtime query optimizer to the logical plan to identify a physical plan including temporal operators for execution by designing temporal join processes to optimize execution of the temporal operators by:
extracting keys from constraints, including extracting one or more partition keys from one or more normal constraints and one or more sorting keys from one or more temporal constraints;
partitioning data into partitions using a hash-based function and shuffling the partitions based on the one or more partition keys to obtain one or more row groups;
sorting rows in each of the one or more row groups based on the one or more sorting keys to obtain sorted rows;
implementing a partition merging phase by finding matched rows among the sorted rows; and

filtering results of the partition merging phase;
translate the logical plan into the physical plan; and
schedule execution of the query according to the physical plan.

12. The system of claim 11 , wherein the constraints further include key temporal constraints.

13. The system of claim 11 , wherein the at least one processor device is further configured to apply the runtime query optimizer to the logical plan to find the physical plan by determining whether to implement a plan modification phase.

14. The system of claim 13 , wherein the a

Assignees

• Nec Lab America Inc
• Nec Corp

Inventors

• Chen Haifeng
• Li Youfu
• Cho Daeki
• Zong Bo
• Arora Nipun
• Lumezanu Cristian

Classifications

• G06F16/2455

  Query execution · CPC title

• G06F16/2453

  Query optimisation · CPC title

• G06N5/046

  Forward inferencing; Production systems · CPC title

• G06F16/24564 Primary

  Applying rules; Deductive queries · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title