Generating a multi-column index for relational databases by interleaving data bits for selectivity
AssigneeAmazon Technologies, Inc.
InventorANURAG WINDLASS GUPTA
Life of this patent
Estimating the term…
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.
Claims22
A distributed data warehouse system, comprising:
- a plurality of compute nodes, implementing:
- one or more storage devices providing storage for a columnar relational database table, wherein the one or more 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;
- generate a multi-column index for the columnar relational database table based, at least in part, on an interleaving of data bits for selectivity from the identified at least two columns, wherein said multi-column index provides a respective index value for each entry of the columnar relational database table;
- a write module, configured to:
- direct the one or more storage devices to store the entries of the columnar relational database table sorted according to the respective index value for each entry in one or more of the plurality of data blocks;
- and
- direct the one or more storage devices to store metadata indicating multi-column index value ranges corresponding to the index values of the entries stored in each of the one or more data blocks.
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 data bits for selectivity from the identified at least two columns, wherein said multi-column index provides a respective index value for each entry of the relational database table;
- and
- storing the entries of the relational database table according to the respective index value for each entry.
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 data bits for selectivity from the identified at least two columns, wherein said multi-column index provides a respective index value for each entry of the relational database table;
- and
- directing storage of the entries of the relational database table according to the respective index value for each entry.
Dependencies are inferred from the claim text.