Organization of data within a database

Patent metadata

Field	Value
Publication number	US-9710507-B2
Application number	US-201514856678-A
Country	US
Kind code	B2
Filing date	Sep 17, 2015
Priority date	Feb 22, 2010
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

A computer implemented method is provided for processing data representing a data entity having sub entities. The method includes analyzing queries to the data entity for deriving information about sets of the sub entities frequently queried together, and grouping the sub entities to a number of banks, each bank having a maximum width, based on the information about sets of sub entities frequently queried together, in order to reduce an average number of banks to be accessed for data retrieval.

First claim

What is claimed:

1. A computer implemented method for processing data of a data table comprising columns, said method comprising:
analyzing queries to said data table and deriving access frequency information about sets of columns of said data table, each set comprising two or more different ones of the columns accessed together by a same corresponding query, wherein said access frequency information includes frequency of occurrences of said sets of columns within said queries;
grouping said columns of said data table for storage in a memory including a plurality of banks, wherein each bank has storage for a fixed quantity of bits and said grouping includes placing columns of said data table accessed together by a same corresponding query in a same bank based on said access frequency information; and
processing a query specifying a plurality of columns of said data table based on said grouping of said columns by scanning at least one bank containing a plurality of the specified columns to reduce number of banks to be scanned for the query and increase table scan speed.

2. The method of claim 1 , wherein said fixed quantity of bits matches a size of a CPU register or a word size.

3. The method of claim 1 , further comprising:
assigning to said sets of columns weight values according to a weight function;
sorting said sets of columns based on said weight values; and
removing from sets of columns having a smaller weight value columns that are present in a set of columns having a higher weight value.

4. The method of claim 3 , wherein said weight function increases with at least one of: total width of said set of columns, access frequency of said set of columns, number of columns in said set of columns, and processing time of said queries to said data table comprising said columns.

5. The method of claim 3 , wherein said weight function determines an order of said sets of columns according to said assigned weight values and the method further comprises a packing method including:
picking up said sets of columns according to said order; and
determining in which bank a current set of columns is placed.

6. The method of claim 3 , further comprising:
determining subsets of columns present in at least two sets of columns; and
handling said subsets of columns as additional sets of columns by assigning a weight value to each subset of columns.

7. The method of claim 6 , wherein an access frequency of each subset of columns is determined as a sum of said access frequencies of corresponding sets of columns containing said subset.

8. The method of claim 3 , further comprising:
handling columns of said data table not present in any set of columns as individual columns having a low weight value.

9. The method of claim 1 , further comprising:
splitting sets of columns having a width larger than a predetermined threshold value and handling said split sets of columns as additional sets of columns by assigning a weight value to each split set of columns.

10. The method of claim 9 , wherein said predetermined threshold value corresponds to said fixed quantity of bits.

11. The method of claim 9 , wherein said weight value determines an order of said split sets of columns according to said assigned weight values, and the method further comprises a packing method including:
picking up said split sets of columns according to said order; and
determining in which bank a current split set of columns is placed.

12. The method of claim 11 , wherein said packing method uses at least one of a first-fit-algorithm, a best-fit-algorithm, and a next-fit-algorithm.

13. The method of claim 1 , wherein grouped data columns in a bank are processed together in a same number of instructions.

14. A computer system comprising at least one computer and at least one storage media to store a database, wherein said at least one computer comprises at least one processing unit configured to process data of a data table comprising columns by:
analyzing queries to said data table and deriving access frequency information about sets of columns of said data table, each set comprising two or more different ones of the columns accessed together by a same corresponding query, wherein said access frequency information includes frequency of occurrences of said sets of columns within said queries;
grouping said columns of said data table for storage in a memory including a plurality of banks, wherein each bank has storage for a fixed quantity of bits and said grouping includes placing columns of said data table accessed together by a same corresponding query in a same bank based on said access frequency information; and
processing a query specifying a plurality of columns of said data table based on said grouping of said columns by scanning at least one bank containing a plurality of the specified columns to reduce a number of banks to be scanned for the query and increase table scan speed.

15. The computer system of claim 14 , wherein the at least one processing unit is further configured to:
assign to said sets of columns weight values according to a weight function;
sort said sets of columns based on said weight values; and
remove from sets of columns having a smaller weight value columns that are present in a set of columns having a higher weight value.

16. The computer system of claim 14 , wherein the at least one processing unit is further configured to:
split sets of columns having a width larger than a predetermined threshold value and handle said split sets of columns as additional sets of columns by assigning a weight value to each split set of columns, wherein said weight value determines an order of said split sets of columns according to said assigned weight values;
pick up said split sets of columns according to said order; and
determine in which bank a current split set of columns is placed.

17. A computer program product for processing data of a data table comprising columns, the computer program product comprising a computer readable storage medium, the computer readable storage medium having computer readable program code embodied therewith, the computer readable program code configured to:
analyze queries to said data table and derive access frequency information about sets of columns of said data table, each set comprising two or more different ones of the columns accessed together by a same corresponding query, wherein said access frequency information includes frequency of occurrences of said sets of columns within said queries;
group said columns of said data table for storage in a memory including a plurality of banks, wherein each bank has storage for a fixed quantity of bits and said grouping includes placing columns of said data table accessed together by a same corresponding query in a same bank based on said access frequency information; and
process a query specifying a plurality of columns of said data table based on said grouping of said columns by scanning at least one bank containing a plurality of the specified columns to reduce a number of banks to be scanned for the query and increase table scan speed.

18. The computer program product of claim 17 , wherein the computer readable program code is further configured to:
assign to said sets of columns weight values according to a weight function;
sort said sets of columns based on said weight values; and
remove from sets of columns having a smaller weight value columns that are present in a set of columns having a higher weight value.

19. The computer program product of claim

Assignees

• IBM

Inventors

• Bendel Peter
• Draese Oliver
• Hrle Namik
• Li Tianchao

Classifications

• G06F17/30345

  Physics · mapped topic

• G06F17/30598

  Physics · mapped topic

• G06F17/30289

  Physics · mapped topic

• G06F17/30342

  Physics · mapped topic

• G06F17/30286

  Physics · mapped topic