INDEXING TECHNIQUE TO DEAL WITH DATA SKEW

• US 20090248616A1
• Filed: 03/26/2008
• Published: 10/01/2009
• Est. Priority Date: 03/26/2008
• Status: Active Grant

• Current Assignee: Teradata Corporation
• Original Assignee: Teradata Corporation
• Inventors: Molini, Stephen
• Granted Patent: US 9,208,186 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A method for facilitating join operations between a first database table and a second database table within a database system. The first database table and the second database table share at least one common index column. The method includes creating a new index column in the second database table that is populated with a limited number of distinct calculated values for the purpose of increasing the overall number of distinct values collectively assumed by the columns common between the two tables. An intermediate table is created, the intermediate table including the common columns of the first database table, the second database table, and the new index column. An index is defined of the intermediate table to be the column(s) common between the first and second tables. An index is defined of the second table to be the column(s) common between the first database table, the second database table and the new index column.

Claims

1. A method for facilitating join operations between a first database table and a second database table within a database system, the first database table and the second database table sharing at least one common index column, the method comprising:

creating a new index column in the second database table that is populated with a limited number of distinct calculated values for the purpose of increasing the overall number of distinct values collectively assumed by the columns common between the two tables;

creating an intermediate table, the intermediate table including the common columns of the first database table, the second database table, and the new index column;

defining an index of the intermediate table to be the column(s) common between the first and second tables; and

defining an index of the second table to be the column(s) common between the first database table, the second database table and the new index column.

2. The method of claim 1 further comprising defining one or more additional intermediate tables between the first database table and the second database table with multiple calculated index columns, the additional intermediate tables progressively augmenting the number of distinct index key values when advancing joins from one intermediate table to the next until finally reaching the second database table.

3. The method of claim 1 further comprising a developer-controlled or administrator-controlled extension to the function used to calculate values for the new index column specifically as where those extensions alter the range of distinct values that can be generated.

4. A method of indexing a database table within a distributed database system, the system comprising a plurality of processing nodes and data storage facilities, the method comprising:

creating an index structure mapping specific key values to a list of logical row id pointers to individual rows;

dynamically determining during insert, update, and delete operations to the index structure when a threshold for the number of multiple row id pointers corresponding to a single index key value has or has not been exceeded;

computing a logical pointer that identifies both the processing node and storage facility containing the row being indexed but only an approximate range of storage blocks that potentially may contain the row; and

consolidating the index structure by only storing a single vague row id pointer for the corresponding rows where the associated skew threshold has been exceeded and a specific row id pointer otherwise.

5. Computer readable media on which is stored computer executable instructions that when executed on a computing device cause the computing device to perform a method for facilitating join operations between a first database table and a second database table within a database system, the first database table and the second database table sharing at least one common index column, the method comprising:

creating a new index column in the second database table that is populated with a limited number of distinct calculated values for the purpose of increasing the overall number of distinct values collectively assumed by the columns common between the two tables;

creating an intermediate table, the intermediate table including the common columns of the first database table, the second database table, and the new index column;

defining an index of the intermediate table to be the column(s) common between the first and second tables; and

defining an index of the second table to be the column(s) common between the first database table, the second database table and the new index column.

6. The computer readable media of claim 5 wherein the method further comprises defining one or more additional intermediate tables between the first database table and the second database table with multiple calculated index columns, the additional intermediate tables progressively augmenting the number of distinct index key values when advancing joins from one intermediate table to the next until finally reaching the second database table.

7. The computer readable media of claim 5 wherein the method further comprises a developer-controlled or administrator-controlled extension to the function used to calculate values for the new index column specifically as where those extensions alter the range of distinct values that can be generated.

8. Computer readable media on which is stored computer executable instructions that when executed on a computing device cause the computing device to perform a method of indexing a database table within a distributed database system, the system comprising a plurality of processing nodes and data storage facilities, the method comprising:

creating an index structure mapping specific key values to a list of logical row id pointers to individual rows;

dynamically determining during insert, update, and delete operations to the index structure when a threshold for the number of multiple row id pointers corresponding to a single index key value has or has not been exceeded;

computing a logical pointer that identifies both the processing node and storage facility containing the row being indexed but only an approximate range of storage blocks that potentially may contain the row; and

consolidating the index structure by only storing a single vague row id pointer for the corresponding rows where the associated skew threshold has been exceeded and a specific row id pointer otherwise.