High Performance Index Creation

Patent metadata

Field	Value
Publication number	US-2015032758-A1
Application number	US-201313953341-A
Country	US
Kind code	A1
Filing date	Jul 29, 2013
Priority date	Jul 29, 2013
Publication date	Jan 29, 2015
Grant date	—

Abstract

High performance index creation using parallel query plans with repartitioning scan and vector-based repartitioning scan is described. An example method includes extracting index key columns from data rows of the database table to build a set of index rows, wherein the index on the database table is defined by a plurality of index key columns including a first index key column and a second index key column. Partition boundary values are generated to divide up the index rows into range-partitioned sets, and the index rows are sorted based on values of the index key columns. A repartitioning scan, including a SARG-based or a vector-based partitioning scan is performed on the index rows, using a plurality of worker threads executing in parallel to build sub-indexes. Subsequently, each range-partitioned set of index rows are assigned to a worker thread in the plurality of worker threads. Accordingly, the sub-indexes generated from the plurality of work threads are merged to build the index for the database table.

First claim

What is claimed is:

1 . A computer-implemented method for creating an index on a database table, comprising:
extracting index key columns from data rows of the database table to build a set of index rows, wherein the index on the database table is defined by a plurality of index key columns including a first index key column and a second index key column; generating partition boundary values to divide up the index rows into range-partitioned sets, wherein the index rows are sorted based on values of the index key columns; performing a repartitioning scan on the index rows of the database table, using a plurality of worker threads executing in parallel to build sub-indexes, wherein each range-partitioned set of index rows are assigned to a worker thread in the plurality of worker threads; and merging the sub-indexes from the plurality of work threads to generate the index for the database table.

2 . The method of claim 1 , wherein the repartitioning scan is a vector-based repartitioning scan performed upon determination that there are duplicated values in the partition boundary values of the first index key column.

3 . The method of claim 2 , wherein the vector-based repartitioning scan is associated with a repartition of the index rows based on a columns vector built upon partition boundary values of at least the first index key column and the second index key column.

4 . The method of claim 1 , wherein the repartition scan is a SARG-based repartitioning scan performed upon determination that there are no duplicated values in the partition boundary values of the first index key column.

5 . The method of claim 4 , wherein the SARG-based repartitioning scan is associated with a repartition of the index rows based on partition boundary values of the first index key column only.

6 . The method of claim 1 , further comprising sampling data rows in the database table to determine if the database table is qualified for parallel processing.

7 . The method of claim 1 , wherein the repartitioning scan is a vector-based repartitioning scan performed upon determination that duplicated values in the partition boundary values of the first index key column exceed a predefined threshold.

8 . The method of claim 1 , further comprising sampling data rows in the database table to generate a distribution map including partition boundary rows, which are defined by the partition boundary values of each index key column.

9 . The method of claim 8 , wherein the vector-based repartitioning scan includes a vector comparison of an index row to be processed with the partition boundary rows.

10 . A system for creating an index on a database table, comprising:
a column extractor, implemented by one or more computing devices, configured to extract index key columns from data rows of the database table to build a set of index rows, wherein the index on the database table is defined by a plurality of index key columns including a first index key column and a second index key column; a value generator, implemented by one or more computing devices, configured to generate partition boundary values to divide up the index rows into range-partitioned sets, wherein the index rows are sorted based on values of the index key columns; a repartitioning scanner, implemented by one or more computing devices, configured to perform a repartitioning scan on the index rows of the database table, using a plurality of worker threads executing in parallel to build sub-indexes, wherein each range-partitioned set of index rows are assigned to a worker thread in the plurality of worker threads; and an index merger, implemented by one or more computing devices, configured to merge the sub-indexes from the plurality of work threads to generate the index for the database table.

11 . The system of claim 10 , wherein the repartitioning scanner is further configured to perform a vector-based repartitioning scan upon determination that there are duplicated values in the partition boundary values of the first index key column.

12 . The system of claim 11 , wherein the vector-based repartitioning scan is associated with a repartition of the index rows based on a columns vector built upon partition boundary values of at least the first index key column and the second index key column.

13 . The system of claim 10 , wherein the repartitioning scanner is further configured to perform a SARG-based repartitioning scan upon determination that there are no duplicated values in the partition boundary values of the first index key column.

14 . The system of claim 13 , wherein the SARG-based repartitioning scan is associated with a repartition of the index rows based on partition boundary values of the first index key column only.

15 . The system of claim 10 , further comprising: a data sampler, implemented by one or more computing devices, configured to sample data rows in the database table to determine if the database table is qualified for parallel processing.

16 . The method of claim 10 , wherein the repartitioning scanner is further configured to perform a vector-based repartitioning scan upon determination that duplicated values in the partition boundary values of the first index key column exceed a predefined threshold.

17 . The method of claim 10 , further comprising sampling data rows in the database table to generate a distribution map including partition boundary rows, which are defined by the partition boundary values of each index key column.

18 . The method of claim 17 , wherein the vector-based repartitioning scan includes a vector comparison of an index row to be processed with the partition boundary rows.

19 . A computer program product comprising a computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to perform operations comprising:
extracting index key columns from data rows of the database table to build a set of index rows, wherein the index on the database table is defined by a plurality of index key columns including a first index key column and a second index key column; generating partition boundary values to divide up the index rows into range-partitioned sets, wherein the index rows are sorted based on values of the index key columns; performing a repartitioning scan on the index rows of the database table, using a plurality of worker threads executing in parallel to build sub-indexes, wherein each range-partitioned set of index rows are assigned to a worker thread in the plurality of worker threads; and merging the sub-indexes from the plurality of work threads to generate the index for the database table.

Assignees

• Schneider Peter
• Rui Ming-Li
• Pendap Santosh
• Xiong Leon
• Sybase Inc

Inventors

• Schneider Peter
• Rui Ming-Li
• Pendap Santosh
• Xiong Leon

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F17/30321 Primary

  Physics · mapped topic