Back to results
US 10,095,722 B1Granted
Hybrid spatial and column-oriented multidimensional storage structure
AssigneeAmazon Technologies, Inc.
InventorsAjay Gopalakrishnan, Mukul Vijay Karnik, Jared Scott Lundell, Yoav Srebrnik, Santosh Kalki
Life of this patent
Estimating the term…
Abstract
Data may be stored using hybrid multidimensional and column-centric storage techniques. A hierarchy of regions of a multidimensional space may be maintained on one or more storage devices. Range information for the hierarchy may be maintained in a column-centric storage. Leaf nodes of the hierarchy may comprise tuple data stored in a column-centric storage. Tuples may be located by identifying candidate regions encompassing the tuple and scanning column-centric stores at the leaf level. Region splitting may be deferred to favor column-centric search characteristics.
Claims20
A system, comprising:
- one or more memories having stored thereon computer-readable instructions that, upon execution by a computing device, cause the system at least to:
- store a plurality of records representative of a hierarchy of regions of a multidimensional space with one or more dimensions corresponding to one or more columns of the table, the plurality of records comprising at least a first interior record and a first leaf record, the first interior record comprising information indicative of a first region of the multidimensional space and information for accessing the first leaf record, the first leaf record comprising a subset of columnar data for a first dimension of the multidimensional space, wherein the subset of columnar data is encompassed by the first region;
- form a first set representation of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a first value of a first column of a row to be added to the table, wherein the first value is of the first dimension;
- form a second set representation of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a second value of a second column of the row, wherein the second value is of a second dimension of the table;
- determine, based at least in part on an intersection of the first set representation and the second set representation, that none of the records, of the plurality of records, contains information indicative of a region that encompasses a point comprising the first value in the first dimension and the second value in the second dimension;
- modify the information indicative of the first region in the first interior record so that the first region encompasses the point;
- and
- add the first value of the first dimension to the columnar data stored in the first leaf record.
5 more elements
A method, comprising:
- storing a plurality of records representative of a hierarchy of regions of a multidimensional space, the plurality of records comprising at least a first interior record and a first leaf record, the first interior record comprising information indicative of a first region of the multidimensional space and information for accessing the first leaf record, the first leaf record comprising a subset of columnar data for a first dimension, wherein the subset of columnar data is encompassed by the first region;
- forming a first set representation of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a first value of a tuple of data to be stored on the one or more storage devices, the first value of the first dimension;
- forming a second set representation of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a second value of the tuple, the second value of a second dimension;
- determining, based at least in part on an intersection of the first set representation and the second set representation, that none of the records, of the plurality of records, corresponds to a region that encompasses a point comprising the first value in the first dimension and the second value in the second dimension;
- modifying the information indicative of the first region in the first interior record so that the first region encompasses the point;
- and
- adding the first value of the first dimension to the columnar data stored in the first leaf record.
4 more elements
A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:
- store a plurality of records on one or more storage devices, the plurality of records representative of a hierarchy of regions of a multidimensional space, the plurality of records comprising at least a first interior record and a first leaf record, the first interior record comprising information indicative of a first region of the multidimensional space and information for accessing the first leaf record, the first leaf record comprising a subset of columnar data for a first dimension, wherein the subset of columnar data is encompassed by the first region;
- form a first representation of a first subset of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a first value of a tuple of data to be stored on the one or more storage devices, the first value of the first dimension;
- form a second representation of a second subset of records, of the plurality of records, that correspond to regions of the multidimensional space that encompass a second value of the tuple, the second value of a second dimension;
- determine, based at least in part on an intersection of the first representation and the second representation, that none of the records, of the plurality of records, contains information indicative of a region that encompasses a point comprising the first value in the first dimension and the second value in the second dimension;
- modify the information indicative of the first region in the first interior record so that the first region encompasses the point;
- and
- add the first value of the first dimension to the columnar data stored in the first leaf record.
4 more elements
Dependencies are inferred from the claim text.