Document-partitioned secondary indexes in a sorted, distributed key/value data store

• US 20170193041A1
• Filed: 01/05/2016
• Published: 07/06/2017
• Est. Priority Date: 01/05/2016
• Status: Abandoned Application

• Current Assignee: A9.com (Amazon.com, Inc.)
• Original Assignee: Sqrrl Data, Incorporated
• Inventors: Fuchs, Adam P.
• Application Number:
  US14/988,489
• Publication Number:
  US 20170193041A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A method and apparatus are operative in association with a table in a sorted, distributed key-value primary store. The table has associated therewith one or more tablets, wherein each tablet being a partition of the table and that contains key-value pairs in a given sub-range of keys. According to the method, a secondary index that is adapted to optimize particular search and query operations against the primary store is created. The secondary index is stored in a manner such secondary index entries are co-partitioned with entries of the primary store to which the secondary index entries refer. This co-partitioning of the secondary index is then maintained throughout various tablet lifecycle operations (e.g., ingest, minor compaction, major compaction, scan, split and merge) associated with at least one tablet. An information retrieval system may leverage the secondary indexing scheme together with query processing to find and retrieve documents matching a user'"'"'s query.

Claims

1. A method operative in association with a table in a sorted, distributed key-value primary store, the table having associated therewith one or more tablets, each tablet being a partition of the table and that contains key-value pairs in a given sub-range of keys, the method comprising:

generating a secondary index adapted to optimize particular search and query operations against the primary store;

storing the secondary index such that secondary index entries are co-partitioned with entries of the primary store to which the secondary index entries refer; and

maintaining co-partitioning of the secondary index throughout a lifecycle of at least one tablet.

2. The method as described in claim 1 wherein the lifecycle of the tablet includes a set of activities that include one of:

creation, ingest, minor compaction, major compaction, scan, split, merge and deletion.

3. The method as described in claim 2 wherein, during ingest, the step of storing the secondary index such that secondary index entries are co-partitioned includes extracting one or more values of a table object and processing the extracted values according to an index type to form the entries for the secondary index.

4. The method as described in claim 3 wherein the index type is one of:

a full-text inverted index, a geospatial index, a geo-hash, a quad tree, an R-tree, a k-d tree, a BSP tree, a grid index, and a graph index.

5. The method as described in claim 2 wherein the minor compaction of the tablet is carried out when the primary store itself undergoes a minor compaction.

6. The method as described in claim 2 wherein the major compaction of the tablet is carried out independently of any major compaction associated with the primary store.

7. The method as described in claim 2 wherein, during a split, all file references for the primary store and the secondary index are copied from the at least one tablet to two new tablets.

8. The method as described in claim 2 wherein, during a merge, one or more files associated with a secondary index from at least two other tablets whose key ranges about one another are joined into the at least one table.

12. The apparatus as described in claim 8 wherein the sorted, distributed key-value primary store is Accumulo.

13. The method as described in claim 1 wherein the secondary index entries remain co-partitioned with the primary entries to which they refer throughout the lifecycle of a tablet by one or more:

(i) pre-splitting of secondary indexes in anticipation of a table split, (ii) prioritizing of major compaction of secondary index files after a split operation, (iii) enforcing use on the secondary index entries of same security labels as the entries in the primary store from which the secondary index entries were generated, (iv) synchronizing minor compactions of primary store and secondary index store to guarantee atomicity and isolation of writes and reads across all stores in the tablet, (v) reconstructing secondary index entries from the primary entries in the write-ahead log at recovery time, (vi) exposing queries to the secondary index as an iterator within an iterator tree, (vii) combining multiple secondary indexes and the primary index to produce a query result in response to a Boolean logic query;

(viii) enabling the secondary indexes and the primary store to share an LRU-based read cache;

(ix) supporting columnar partitioning on the secondary index;

(x) storing in the secondary index cell-level security labels, wherein the secondary index readers filter index entries using the same cell-level security filter used in the primary store;

(xi) preserving the same cell-level security labeling from the original mutations;

(xii) supporting compaction-time and scan-time iterators similar to the primary store;

(xiii) supporting bulk loading of information into secondary indexes;

(xiv) populating a secondary index with a bulk transformation of existing primary store entries; and

(xv) automatically maintaining referential integrity of secondary index entries by propagating changes in the primary store so as to remove secondary index entries, and by re-generating a secondary index from the primary store as a bulk transformation, preferably scheduled periodically or as a one-time operation.

9. Apparatus, operative in association with a table in a sorted, distributed key-value primary store, the table having associated therewith one or more tablets, each tablet being a partition of the table and that contains key-value pairs in a given sub-range of keys, comprising:

one or more hardware processors;

computer memory storing computer program instructions executed by the hardware processors to;

generate a secondary index adapted to optimize particular search and query operations against the primary store;

store the secondary index such that secondary index entries are co-partitioned with entries of the primary store to which the secondary index entries refer; and

maintain co-partitioning of the secondary index throughout a lifecycle of at least one tablet.

10. The apparatus as described in claim 9 wherein the lifecycle of the tablet includes a set of activities that include one of:

creation, ingest, minor compaction, major compaction, scan, split, merge and deletion.

11. The apparatus as described in claim 9 wherein the computer program instructions further include computer program instructions operative at query time and in response to receipt of a query to:

use the secondary index to search against the primary store; and

to return a response to the query.