# US 2012/0084278 A1 · Scan sharing for query predicate evaluations in column-based in-memory database systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084278 A1
- Document ID: US20120084278A1
- Status: Published application
- Kind: A1
- Application number: 12/894,370
- Filed: 2010-09-30
- Published: 2012-04-05
- Earliest claimed: 2010-09-30
- Assignees: International Business Machines Corporation
- Inventors: Hubertus Franke; Hong Min
- Web page: https://patentgrep.com/patent/US20120084278A1

## CPC

- G06F 16/28: Databases characterised by their database models, e.g. relational or object models
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 3)

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.

### Claim 7 (depends on 3)

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.

### Claim 8 (depends on 3)

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.

### Claim 9 (depends on 3)

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

### Claim 10 (depends on 3)

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.

### Claim 11 (depends on 3)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 1)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 16)

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.

### Claim 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.

### Claim 21 (depends on 20)

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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 20)

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.

### Claim 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.
