Table organization using one or more queries

• US 10,394,790 B2
• Filed: 08/04/2016
• Issued: 08/27/2019
• Est. Priority Date: 02/14/2014
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: International Business Machines Corporation
• Inventors: Muras, Brian R.
• Primary Examiner(s): Gortayo, Dangelino N
• Application Number:
  US15/227,988
• Publication Number:
  US 20160342640A1
• Time in Patent Office: 1,118 Days
• Field of Search: 707745, 707718, 707752, 707803
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A method, system and computer program product are provided for reorganizing a database table according to a set of queries. More specifically, the table is reorganized such that random I/O is reduced by more tightly grouping together rows in the table associated with each of the referencing queries. This enables more associated rows from a given table relevant to a query to be read into memory for a given I/O operation.

Claims

1. A program product, comprising:

a computer readable storage medium; and

program code stored on the computer readable storage medium and configured upon execution to reorganize a database table residing on a computer system according to a set of queries, comprising the steps of;

constructing a bitmap entry for each row entry within the database table, each bitmap entry having n bit positions, each of the n bit positions corresponding to a referencing state of a different one of the set of queries;

computing a single numerical value for each bitmap entry as a function of individual bit values for the n bit positions; and

sorting the row entries within the database table based upon the numerical values of the bitmap entries.

2. The program product of claim 1, wherein constructing a bitmap entry for each row comprises:

initializing a first bitmap entry for a first row to “

0”

;

determining if any of the set of queries point to the first row; and

if yes, setting the bit positions within the first bitmap entry corresponding to the referencing queries associated with the first row to “

1”

.

3. The program product of claim 2, wherein the bit positions within each bitmap entry are organized such that the most significant bit positions within each bitmap entry are assigned to the most popular queries within the set of queries, and the least significant bit positions within each bitmap entry are assigned to the least popular queries.

4. The program product of claim 3, wherein the popularity of each of the queries is determined by monitoring query use of the queries by at least one counter.

5. The program product of claim 1, wherein the set of queries reference the same column within the database table.

6. The program product of claim 1, wherein in the set of queries reference a set of columns within the database table.

7. The program product of claim 1, wherein one or more of the set of queries are ignored in computing the value of the bitmap, based upon a set of predefined criteria.

8. The program product of claim 7, wherein one of the set of predefined criteria is the number of rows selected by the query.

9. The program product of claim 1, wherein the steps further comprise sorting, in response to sorting the row entries within the database table based upon the values of the bitmap entries, at least a portion of the row entries within the database table based upon an index.

10. The program product of claim 1, wherein the steps further comprise setting a plurality of bits in a plurality of bitmaps associated with a plurality of tables to reorganize the plurality of tables.

11. The program product of claim 1, wherein sorting the row entries within the database table based upon the values of the bitmap entries further comprises:

determining a degree of adjacency metric for rows in the database table referenced by each of the set of queries; and

if the value of the degree of adjacency metric exceeds a predefined threshold value, sorting the row entries within the database.

12. A system, comprising:

one or more computer processors; and

a memory containing a program, which when executed by the one or more computer processors is configured to perform an operation comprising;

constructing a bitmap entry for each row entry within the database table, each bitmap entry having n bit positions, each of the n bit positions corresponding to a referencing state of a different one of the set of queries;

computing a single numerical value for each bitmap entry as a function of individual bit values for the n bit positions; and

sorting the row entries within the database table based upon the numerical values of the bitmap entries.

13. The system of claim 12, wherein constructing a bitmap entry for each row comprises:

initializing a first bitmap entry for a first row to “

0”

;

determining if any of the set of queries point to the first row; and

if yes, setting the bit positions within the first bitmap entry corresponding to the referencing queries associated with the first row to “

1”

.

14. The system of claim 13, wherein the bit positions within each bitmap entry are organized such that the most significant bit positions within each bitmap entry are assigned to the most popular queries within the set of queries, and the least significant bit positions within each bitmap entry are assigned to the least popular queries.

15. The system of claim 14, wherein the popularity of each of the queries is determined by monitoring query use of the queries by at least one counter.

16. The system of claim 12, wherein the set of queries reference the same column within the database table.

17. The system of claim 12, wherein in the set of queries reference a set of columns within the database table.

18. The system of claim 12, wherein one or more of the set of queries are ignored in computing the value of the bitmap, based upon a set of predefined criteria.

19. The system of claim 18, wherein one of the set of predefined criteria is the number of rows selected by the query.

20. The system of claim 12, wherein the operation further comprises sorting, in response to sorting the row entries within the database table based upon the values of the bitmap entries, at least a portion of the row entries within the database table based upon an index.