Generating a multi-column index for relational databases by interleaving data bits for selectivity

• US 10,394,848 B2
• Filed: 07/29/2013
• Issued: 08/27/2019
• Est. Priority Date: 07/29/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass
• Primary Examiner(s): Wilson, Kimberly L
• Application Number:
  US13/953,432
• Publication Number:
  US 20150032684A1
• Time in Patent Office: 2,220 Days
• Field of Search: 707600
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A multi-column index is generated based on an interleaving of data bits for selectivity for efficient processing of data in a relational database system. Two or more columns may be identified for inclusion in the multi-column index for a relational database table. Based, at least in part, on the interleaving of data bits for selectivity from the identified columns, a multi-column index is generated for the relational database table that provides a respective index value for each entry in the relational database table. The entries of the relational database table may then be stored according to the index values of the multi-column index.

Claims

1. A distributed data warehouse system, comprising:

a plurality of compute nodes, each comprising one or more hardware processors, implementing;

one or more persistent storage devices providing storage for a columnar relational database table, wherein the one or more persistent storage devices comprise a plurality of data blocks;

a multi-column key generator, configured to;

identify at least two columns of a plurality of columns of the columnar relational database table; and

generate a multi-column index for the columnar relational database table based, at least in part, on an interleaving of respective data bits for selectivity from respective portions of respective data values from the identified at least two columns, wherein said multi-column index provides a respective index value for each entry of a plurality of entries of the columnar relational database table;

a write module, configured to;

direct the one or more persistent storage devices to store the plurality of entries of the columnar relational database table, wherein the plurality of entries of the columnar relational database table are directed to be stored in one or more of the plurality of data blocks of the one or more persistent storage devices in sorted order according to the respective index value for each of the plurality of entries; and

direct the one or more persistent storage devices to store metadata indicating multi-column index value ranges corresponding to the index values of the respective entries stored in each of the one or more data blocks.

2. The system of claim 1, wherein to generate the multi-column index for the columnar relational database table based, at least in part, on an interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified at least two columns, the multi-column key generator is configured to compress data from one or more of the at least two columns according to an order preserving compression technique.

3. The system of claim 2, wherein to compress data from the one or more of the at least two columns according to an order preserving compression technique, the multi-column key generator is further configured to:

determine a column data hierarchy for a particular one of the one or more columns from one or more other columns of the columnar relational database table, wherein the column data hierarchy determines an ordering of data values for the particular one of the one or more columns; and

apply the column data hierarchy to the particular one of the one or more columns to order data in the particular one of the one or more columns according to the column data hierarchy.

4. The system of claim 3, further comprising:

a read module; and

a query engine, configured to;

receive an indication of a query directed to one or more of the at least two columns or to one or more of the one or more other columns of the columnar relational database table for select data;

evaluate the indication of the query to determine one or more predicate data values based, at least in part, on an interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified at least two columns, wherein the one or more predicate data values identify the select data;

in response to receiving and evaluating the indication of the query;

analyze the metadata indicating the multi-column index value ranges for the one or more predicate data values for each of the one or more data blocks to determine particular ones of the one or more data blocks to be read in order to service the query for the select data; and

direct the read module to read the particular ones of the one or more data blocks storing data for the columnar relational database table.

5. A method, comprising:

performing, by one or more computing devices;

identifying at least two columns of a plurality of columns of a relational database table;

generating a multi-column index for the relational database table based, at least in part, on an interleaving of respective data bits for selectivity from respective portions of respective data values from the identified at least two columns, wherein said multi-column index provides a respective index value for each of a plurality of entries of the relational database table;

storing the plurality of entries of the relational database table to persistent storage in sorted order according to the respective index value for each entry; and

storing metadata indicating multi-column index value ranges corresponding to the index values of the respective entries stored in the persistent storage.

6. The method of claim 5, wherein said generating the multi-column index for the relational database table, comprises applying an order-preserving compression technique in order to compress data for one or more of the at least two columns.

7. The method of claim 6, wherein said applying an order-preserving compression technique in order to compress data for the one or more of the at least two columns comprises applying a column data hierarchy to a particular one of the one or more columns to order data in the particular one of the one or more columns according to the column data hierarchy.

8. The method of claim 5, wherein the respective index value for each of the plurality of entries of the relational database table is a distribution key value, wherein said storing the plurality of entries of the relational database table to persistent storage according to the respective index value for each of the plurality of entries comprises distributing the plurality of entries of the relational database table to be persisted among a plurality of different persistent storage devices based, at least in part, on the distribution key values for the plurality of entries of the relational database table.

9. The method of claim 5, wherein the respective index value for of the plurality of entries of the relational database table is a sort key value, wherein said storing the plurality of entries of the of the relational database table to persistent storage according to the respective index value for each of the plurality of entries comprises storing the plurality of entries of the relational database table sorted according to the sort key value for the plurality of entries of the of the relational database table.

10. The method of claim 9, further comprising:

receiving one or more additional entries to be stored for the relational database table; and

generating one or more sort key values, based, at least in part, on the interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified at least two columns for the additional entries.

11. The method of claim 9, wherein the plurality of entries of the relational database table are persistently stored among a plurality of data blocks, and wherein the method further comprises maintaining metadata indicating multi-column sort key value ranges corresponding to the sort key values of the respective entries stored in each of the one or more data blocks.

12. The method of claim 11, further comprising:

receiving an indication of a query directed to one or more of the at least two columns of the relational database table for select data;

evaluating the indication of the query to determine one or more predicate data values based, at least in part, on the interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified two columns, wherein the one or more predicate data values identify the select data; and

in response to receiving and evaluating the indication of the query;

analyzing the multi-column sort key value ranges for the one or more predicate data values for each of the one or more data blocks to identify particular ones of the plurality of data blocks to be read in order to service the query for the select data.

13. The method of claim 5, wherein the one or more computing devices are part of a larger collection of computing devices implementing a data warehouse cluster storing data for one or more clients in a distributed database system, wherein the one or more computing devices together implement a compute node of the data warehouse cluster, and wherein said identifying the at least two columns of the plurality of columns of the relational database table, comprises receiving an indication of client-selected columns as the at least two identified columns.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement a relational database system that implements:

identifying at least two columns of a plurality of columns of a relational database table;

generating a multi-column index for the relational database table based, at least in part, on an interleaving of respective data bits for selectivity from respective portions of respective data values from the identified at least two columns, wherein said multi-column index provides a respective index value for each of a plurality of entries of the relational database table; and

directing storage of;

the plurality of entries of relational database table to persistent storage in sorted order according to the respective index value for each entry; and

metadata indicating multi-column index value ranges corresponding to the index values of the respective entries stored in the persistent storage.

15. The non-transitory, computer-readable storage medium of claim 14, wherein, in said generating the multi-column index for the relational database table, the program instructions cause the database system to implement applying an order-preserving compression scheme in order to compress data for one or more of the at least two columns.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions further cause the database system to implement:

receiving one or more additional entries to be stored for the relational database table; and

generating one or more index values, based, at least in part, on the interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified at least two columns for the additional one or more entries.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the program instructions devices further cause the database system to implement:

detecting a re-compression event for a particular one of the one or more columns based, at least in part, on selectivity of the particular one of the one or more columns;

modifying the order-preserving compression scheme based, at least in part, on the selectivity of the particular one of the one or more columns;

applying the modified order-preserving compression scheme to compress the data for the one or more columns including the additional one or more entries in order to generate re-compressed data; and

performing said generating the multi-column index for the relational database table based, at least in part, on the re-compressed data for the particular one of the one or more columns in order to update the respective index values for each of the plurality of entries of the relational database table including the additional one or more entries.

18. The non-transitory, computer-readable storage medium of claim 17, wherein the program instructions further cause the database system to implement:

maintaining the multi-column index for servicing read requests during the performance of generating the multi-column index for the relational database table based, at least in part, on the re-compressed data;

upon completion of generating the multi-column index for the relational database table based, at least in part, on the re-compressed data, servicing read requests based, at least in part, on the updated index values for the multi-column index based, at least in part, on the re-compressed data.

19. The non-transitory, computer-readable storage medium of claim 16, wherein in said applying the order-preserving compression scheme in order to compress data for one or more of the at least two columns, the program instructions devices further cause the database system to implement adding additional data bits in order to represent values for each of the one or more additional entries.

20. The non-transitory, computer-readable storage medium of claim 15, wherein, in applying the order-preserving compression scheme in order to compress the data for one or more of the at least two columns, the program instructions cause the database system to implement applying a column data hierarchy to a particular one of the one or more columns to order data in the particular one of the one or more columns according to the column data hierarchy, wherein the column data hierarchy is determined from one or more other columns of the relational database table.

21. The non-transitory, computer-readable storage medium of claim 20, wherein the respective index value for each of the plurality of entries of the relational database table is a sort key value, wherein the plurality of entries of the relational database table are sorted according to the respective sort key values for the plurality of entries of the relational database table, wherein the plurality of entries of the relational database table are persistently stored among a plurality of data blocks, and wherein the program instructions cause the database system to further implement:

maintaining metadata indicating multi-column sort key value ranges corresponding to the sort key values of the respective entries stored in each of the one or more data blocks;

receiving an indication of a query directed to one or more of the at least two columns or to one or more of the one or more other columns of the relational database table for select data;

evaluating the indication of the query to determine one or more predicate data values based, at least in part, on the interleaving of the respective data bits for selectivity from the respective portions of the respective data values from the identified two columns, wherein the one or more predicate data values identify the select data; and

in response to receiving and evaluating the indication of the query;

analyzing the multi-column sort key value ranges for the one or more predicate data values for each of the one or more data blocks to identify particular ones of the plurality of data blocks to be read in order to service the query for the select data.

22. The non-transitory, computer-readable storage medium of claim 14, wherein the respective index value for each of the plurality of entries of the relational database table is a distribution key value, and wherein, in said directing the storage of the plurality of entries of relational database table according to the respective index value for each plurality of entries, the program instructions cause the database system to implement distributing the plurality of entries of the relational database table to be persisted among a plurality of different persistent storage devices based, at least in part, on the distribution key values for the plurality of entries of the relational database table.