SCAN SHARING FOR QUERY PREDICATE EVALUATIONS IN COLUMN-BASED IN-MEMORY DATABASE SYSTEMS

• US 20120084278A1
• Filed: 09/30/2010
• Published: 04/05/2012
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Franke, Hubertus, Min, Hong
• Granted Patent: US 8,631,000 B2
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models

Abstract

A plurality of queries of an in-memory column-oriented database are obtained. Each of the queries has at least one column predicate. For each of the queries, it is determined which of a plurality of columns in the in-memory column-oriented database need to be scanned. The plurality of queries are grouped into a plurality of scan groups, based at least in part on the determining step. The column predicates are evaluated for those of the queries in a given one of the scan groups in accordance with a scheduling scheme. The grouping step and the scheduling scheme take into account real time scan information.

Claims

1. A method comprising:

obtaining a plurality of queries of an in-memory column-oriented database, each of said queries having at least one column predicate;

determining, for each of said queries, which of a plurality of columns in said in-memory column-oriented database need to be scanned;

grouping said plurality of queries into a plurality of scan groups, based at least in part on said determining step; and

evaluating said column predicates for those of said queries in a given one of said scan groups in accordance with a scheduling scheme;

wherein said grouping step and said scheduling scheme take into account real time scan information.

2. The method of claim 1, wherein said grouping comprises determining whether a given one of said queries should be assigned to an existing one of said scan groups or a new one of said scan groups.

3. The method of claim 2, wherein said determining, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, is based on an estimated query cost and said real time scan information.

4. The method of claim 3, wherein said determining, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, comprises:

for a given one of said queries, ranking those of said plurality of columns in said in-memory column-oriented database that need to be scanned, based upon a number of records in said in-memory column-oriented database qualified by those of said plurality of columns in said in-memory column-oriented database that need to be scanned, to obtain at least a first ranked column and a second ranked column; and

determining whether said first ranked column should be scanned first or whether said first and second ranked columns should be scanned simultaneously.

5. The method of claim 4, wherein said determining whether said first ranked column should be scanned first or whether said first and second ranked columns should be scanned simultaneously takes into account whether there exists at least one of:

an existing one of said scan groups which scans said first ranked column; and

an existing one of said scan groups which scans said first and second ranked columns simultaneously.

6. The method of claim 3, wherein said determining, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, comprises:

for a given one of said queries, ranking those of said plurality of columns in said in-memory column-oriented database that need to be scanned, based upon a number of records in said in-memory column-oriented database qualified by those of said plurality of columns in said in-memory column-oriented database that need to be scanned, to obtain at least a first ranked column and a second ranked column; and

if said first ranked column has a predicate type that is more costly to operate on first in terms of overall query cost than said second ranked column, not scanning said first ranked column first.

7. The method of claim 3, wherein said determining whether said given one of said queries should be assigned to said existing one of said scan groups or said new one of said scan groups comprises:

determining whether adding said given one of said queries to said existing one of said scan groups would cause a size of said existing one of said scan groups to exceed a size of a cache level at which access latencies can be tolerated; and

if said adding said given one of said queries to said existing one of said scan groups would cause said size of said existing one of said scan groups to exceed said size of said cache level at which said access latencies can be tolerated, assigning said given one of said queries to said new one of said scan groups.

8. The method of claim 3, wherein said determining whether said given one of said queries should be assigned to said existing one of said scan groups or said new one of said scan groups comprises:

determining whether adding said given one of said queries to said existing one of said scan groups would cause a size of said existing one of said scan groups to exceed a threshold based upon avoidance of stalling; and

if said adding said given one of said queries to said existing one of said scan groups would cause said size of said existing one of said scan groups to exceed said threshold based upon avoidance of stalling, assigning said given one of said queries to said new one of said scan groups.

9. The method of claim 3, wherein said grouping takes into account quality of service requirements.

10. The method of claim 3, wherein said in-memory column-oriented database is horizontally partitioned into a plurality of partitions, and wherein, in said grouping of said queries, a given one of said plurality of queries is added to an ongoing scan of a corresponding one of said plurality of scan groups at commencement of scanning a new one of said partitions.

11. The method of claim 3, further comprising obtaining said real time scan information as at least one of:

identification of active ones of said scan groups;

progress of said active ones of said scan groups; and

working size of said active ones of said scan groups.

12. The method of claim 11, wherein said in-memory column-oriented database is horizontally partitioned into a plurality of partitions, and wherein said real time scan information is obtained at commencement of scanning a new one of said partitions.

13. The method of claim 1, further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied on a computer-readable storage medium, and wherein the distinct software modules comprise a query optimization module, a query grouping module, a scheduling module, and a query engine module;

wherein;

said obtaining of said plurality of queries and said determining, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, are carried out by said query optimization module executing on at least one hardware processor;

said grouping said plurality of queries into said plurality of scan groups is carried out by said query grouping module executing on said at least one hardware processor; and

said evaluating of said column predicates for those of said queries in said given one of said scan groups in accordance with said scheduling scheme is carried out by said query engine module executing on said at least one hardware processor;

wherein said scheduling scheme is developed by said scheduling module executing on said at least one hardware processor.

14. A computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, said computer readable program code comprising:

computer readable program code configured to obtain a plurality of queries of an in-memory column-oriented database, each of said queries having at least one column predicate;

computer readable program code configured to determine, for each of said queries, which of a plurality of columns in said in-memory column-oriented database need to be scanned;

computer readable program code configured to group said plurality of queries into a plurality of scan groups, based at least in part on said determining step; and

computer readable program code configured to evaluate said column predicates for those of said queries in a given one of said scan groups in accordance with a scheduling scheme;

wherein said grouping and said scheduling scheme take into account real time scan information.

15. The computer program product of claim 14, wherein said computer readable program code configured to group comprises computer readable program code configured to determine whether a given one of said queries should be assigned to an existing one of said scan groups or a new one of said scan groups.

16. The computer program product of claim 15, wherein said computer readable program code configured to determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, makes said determination based on an estimated query cost and said real time scan information.

17. The computer program product of claim 16, wherein said computer readable program code configured to determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, comprises:

computer readable program code configured to, for a given one of said queries, rank those of said plurality of columns in said in-memory column-oriented database that need to be scanned, based upon a number of records in said in-memory column-oriented database qualified by those of said plurality of columns in said in-memory column-oriented database that need to be scanned, to obtain at least a first ranked column and a second ranked column; and

computer readable program code configured to determine whether said first ranked column should be scanned first or whether said first and second ranked columns should be scanned simultaneously.

18. The computer program product of claim 17, wherein said computer readable program code configured to determine whether said first ranked column should be scanned first or whether said first and second ranked columns should be scanned simultaneously takes into account whether there exists at least one of:

an existing one of said scan groups which scans said first ranked column; and

an existing one of said scan groups which scans said first and second ranked columns simultaneously.

19. The computer program product of claim 16, wherein said computer readable program code configured to determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, comprises:

computer readable program code configured to, for a given one of said queries, rank those of said plurality of columns in said in-memory column-oriented database that need to be scanned, based upon a number of records in said in-memory column-oriented database qualified by those of said plurality of columns in said in-memory column-oriented database that need to be scanned, to obtain at least a first ranked column and a second ranked column; and

computer readable program code configured to, if said first ranked column has a predicate type that is more costly to operate on first in terms of overall query cost than said second ranked column, not scan said first ranked column first.

20. An apparatus comprising:

a memory; and

at least one processor, coupled to said memory, and operative to;

obtain a plurality of queries of an in-memory column-oriented database, each of said queries having at least one column predicate;

determine, for each of said queries, which of a plurality of columns in said in-memory column-oriented database need to be scanned;

group said plurality of queries into a plurality of scan groups, based at least in part on said determining; and

evaluate said column predicates for those of said queries in a given one of said scan groups in accordance with a scheduling scheme;

wherein said grouping and said scheduling scheme take into account real time scan information.

21. The apparatus of claim 20, wherein said at least one processor is operative to group by determining whether a given one of said queries should be assigned to an existing one of said scan groups or a new one of said scan groups.

22. The apparatus of claim 21, wherein said at least one processor is operative to determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, based on an estimated query cost and said real time scan information.

23. The apparatus of claim 22, wherein said at least one processor is operative to determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned, by:

for a given one of said queries, ranking those of said plurality of columns in said in-memory column-oriented database that need to be scanned, based upon a number of records in said in-memory column-oriented database qualified by those of said plurality of columns in said in-memory column-oriented database that need to be scanned, to obtain at least a first ranked column and a second ranked column; and

determining whether said first ranked column should be scanned first or whether said first and second ranked columns should be scanned simultaneously.

24. The apparatus of claim 20, further comprising a plurality of distinct software modules, each of the distinct software modules being embodied on a computer-readable storage medium, and wherein the distinct software modules comprise a query optimization module, a query grouping module, a scheduling module, and a query engine module;

wherein;

said at least one processor is operative to obtain said plurality of queries and determine, for each of said queries, which of said plurality of columns in said in-memory column-oriented database need to be scanned by executing said query optimization module;

said at least one processor is operative to group said plurality of queries into said plurality of scan groups by executing said query grouping module;

said at least one processor is operative to evaluate said column predicates for those of said queries in said given one of said scan groups in accordance with said scheduling scheme by executing said query engine module; and

said at least one processor is operative to develop said scheduling scheme by executing said scheduling module.

25. An apparatus comprising:

means for obtaining a plurality of queries of an in-memory column-oriented database, each of said queries having at least one column predicate;

means for determining, for each of said queries, which of a plurality of columns in said in-memory column-oriented database need to be scanned;

means for grouping said plurality of queries into a plurality of scan groups, based at least in part on said determining step; and

means for evaluating said column predicates for those of said queries in a given one of said scan groups in accordance with a scheduling scheme;

wherein said means for grouping and said scheduling scheme take into account real time scan information.