US 2019/0377743 A1Published application

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…

Loading patent…

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.

Claims21

Dependent claims

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.

6 more elements

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.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 16/549,669Filed 23 Aug 2019
Priority: 29 Jul 2013
Published: 12 Dec 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/221
Indexing; Data structures therefor; Storage structures: column-oriented storage; Management thereof
G06F 16/22
Of structured data, e.g. relational data: indexing; Data structures therefor; Storage structures
G06F 16/2228
Indexing; Data structures therefor; Storage structures: indexing structures
G06F 16/27
Of structured data, e.g. relational data: replication, distribution or synchronisation of data between databases or within a distributed database…

Family

Application13/953,432Continuation · filed 29 Jul 2013
Application16/549,669Continuation
US 10,394,848 B2Related patent
US 11,132,384 B2Related patent
US 2015/0032684 A1Published application
US 2019/0377743 A1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key