Intra-block partitioning for database management

Patent metadata

Field	Value
Publication number	US-9535940-B2
Application number	US-201213599007-A
Country	US
Kind code	B2
Filing date	Aug 30, 2012
Priority date	May 31, 2012
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

A method for storing database information includes storing a table having data values in a column major order. The data values are stored in a list of blocks. The method also includes assigning a tuple sequence number (TSN) to each data value in each column of the table according to a sequence order in the table. The data values that correspond to each other across a plurality of columns of the table have equivalent TSNs. The method also includes assigning each data value to a partition based on a representation of the data value. The method also includes assigning a tuple map value to each data value. The tuple map value identifies the partition in which each data value is located.

First claim

What is claimed is:

1. A method for storing database information, comprising:
storing a table comprising data values in a column major order, wherein the data values comprise encoded and unencoded data values, wherein the data values within each column are stored in a list of blocks, wherein each block comprises an array;
assigning a tuple sequence number (TSN) to each data value in each column of the table according to a sequence order in the table, wherein data values that correspond to each other across a plurality of columns of the table have equivalent TSNs;
identifying a bit length of each encoded data value and an encoding representation of each encoded data value;
assigning each encoded data value in a block to one of a plurality of partitions within the block based on the bit length of each encoded data value and the encoding representation of each encoded data value, and assigning the unencoded data values to a separate partition from the encoded data values, the unencoded data values stored in an unencoded format and each other partition comprising data values stored in a distinct encoding format, representing each partition in the array within the block, wherein the array is an index separate from the plurality of partitions;
indexing the data values in the block in an array contained in the block by assigning a tuple map value to each data value, wherein the tuple map value identifies the partition in which each data value is located; and
storing the tuple map values in the array within the block.

2. The method of claim 1 , further comprising:
receiving a new record comprising related data values for insertion into the plurality of columns in the table;
inserting the new record into a buffer;
ordering records within the buffer based on the representation of the data values in each record to preserve a TSN order of the records among values comprising identical representation;
appending the data values of the records from the buffer to partitions in a trailing block of each corresponding column; and
assigning a new tuple map value to each data value of the records for the corresponding partitions.

3. The method of claim 1 , further comprising:
receiving a query that performs operations on a subset of the table identified by one or more predicates;
evaluating the predicates within each partition independently;
producing one bitmap per partition, wherein each bitmap indicates only data values which pass the corresponding predicates; and
merging all bitmaps using the tuple map values to form a combined bitmap for the corresponding block.

4. The method of claim 3 , further comprising:
loading the data values that pass the predicates from the combined bitmap for a region, wherein the region comprises one partition in the corresponding block;
forming an array of source indexes in each region and destinations indexes in an output vector; and
moving the data values from a first location specified by the source indexes to a second location specified by the destination indexes.

5. The method of claim 1 , further comprising:
sequentially scanning a tuple map comprising the tuple map values;
maintaining a cursor in each partition in the tuple map; and
accessing a given data value from the cursor on an indicated partition in response to encountering the indicated partition while scanning the tuple map; and
incrementing the cursor.

Assignees

• Barber Ronald J
• Kim Min-Soo
• Lightstone Sam S
• Lohman Guy M
• Qiao Lin
• Raman Vijayshankar
• Shekita Eugene J
• Sidle Richard S
• IBM

Inventors

• Barber Ronald J
• Kim Min-Soo
• Lightstone Sam S
• Lohman Guy M
• Qiao Lin
• Raman Vijayshankar
• Shekita Eugene J
• Sidle Richard S

Classifications

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F17/30584

  Physics · mapped topic

• G06F17/30315 Primary

  Physics · mapped topic