Querying data set tables in a non-transactional database

• US 9,633,074 B1
• Filed: 01/03/2014
• Issued: 04/25/2017
• Est. Priority Date: 01/03/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sharma, Raghvendra, Goel, Sachin Kumar, Murti, Gautam Venkatesh, Tushant
• Primary Examiner(s): Leroux, Etienne
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US14/147,282
• Time in Patent Office: 1,208 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/248 Presentation of query results

Abstract

A method and apparatus for facilitating data set query is disclosed. In the method and apparatus one or more tables may be created for the data set, whereby each table of the one or more tables may enable searching the data set using one or more records that are associated with one or more indices of the data set. Upon receiving a request to search the data set, a table of the one or more table is identified based at least in part on the one or more bases for query and is searched to provide a yielded record.

Claims

1. A computer-implemented method for searching a data set, comprising:

under the control of one or more computer systems configured with executable instructions,

storing a data set, the data set including a plurality of records and being structured according to a plurality of indices, each record of the plurality of records being associated with one or more indices of the plurality of indices;

receiving a request to create search indices for querying the data set, the request specifying a query object and one or more bases for query for the data set, the query object being a data field to be provided upon execution of the query and being sought to become searchable based at least in part on the one or more bases for query, an individual basis for query of the one or more bases for query being associated with an index of the plurality of indices of the data set;

constructing a table in a non-transactional database, the table having the one or more bases for query as a primary key and the query object as a secondary index, the primary key of the non-transactional database comprising a hash key and a hash range;

receiving a request to query the data set, the request specifying one or more records associated with the one or more bases for query; and

in response to receiving the request;

identifying the table based at least in part on the one or more bases for query;

searching the table to yield a record of the secondary index; and

providing the record of the secondary index.

2. The computer-implemented method of claim 1, wherein:

the non-transactional database is a NoSQL database; and

a first basis for query of the one or more bases for query being assigned as the hash key and a second basis for query of the one or more bases for query being assigned as a range key.

3. The computer-implemented method of claim 2, wherein:

the request to query the data set is an application programming interface (API) function call; and

the request to query the data set specifies a page size limiting a number of records of the secondary index provided in response to the request.

4. The computer-implemented method of claim 1, wherein the secondary index of the table is capable of being filtered according to one or more filtering parameters.

5. The computer-implemented method of claim 1, further comprising:

receiving a request to add a new record to the table; and

on a condition that the new record is determined to match an existing record in the table, appending the new record with one or more characters to distinguish the new record from the existing record.

6. The computer-implemented method of claim 5, wherein:

determining whether the new record is in conflict with the existing record further includes searching the table to determine a number of matching records in the table; and

the one or more characters are sequentially assigned based at least in part on the number of matching records in the table.

7. A system, comprising at least one computing device configured to implement one or more services, the one or more services are configured to:

receive a plurality of query pairs, a query pair of the plurality of query pairs including a query object for a data set and one or more bases for query for the data set, the data set being organized according to a plurality of indices, the query object being associated with an index of the plurality of indices and the one or more bases for query are associated with one or more indices of the plurality of indices; and

for the query pair of the plurality of query pairs;

create a table for the data set in a NoSQL database, the table being searchable based at least in part on one or more records of the one or more bases for query for the query pair, the table having a primary key comprising a hash key and a hash range; and

cause the table to be searched to yield a yielded record, the yielded record belonging to the query object of the query pair.

8. The system of claim 7, wherein a first basis for query of the one or more bases for query is set as the hash key and a second basis for query of the one or more bases for query is set as the hash range.

9. The system of claim 7, wherein the query object of the created table is a secondary index of the created table.

10. The system of claim 7, wherein the system is further configured to:

receive application programming interface (API) function call requesting the data set to be searched, the API function call specifying the one or more records of the one or more bases for query; and

identify the table to be searched based at least in part on the one or more bases for query.

11. The system of claim 7, wherein the system is further configured to:

filter the yielded record based at least in part on one or more filtering parameters; and

provide the filtered yielded record as a query result.

12. The system of claim 7, wherein the system is further configured to:

receive a request to add a new record to the data set; and

cause the new record to be added to the created table.

13. The system of claim 12, wherein

the system is further configured to determine whether the new record matches an existing record in the table;

and

causing the new record to be added to the table further includes;

appending the new record with one or more characters to distinguish the appended new record from the existing record; and

adding the appended new record to the table.

14. A non-transitory computer-readable storage medium having collectively stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

store a data set, the data set being searchable based at least in part on a plurality of indices associated with the data set;

for at least one pair of indices of the plurality of indices, create a table in a non-transactional database for the data set, the table being populated by records of the data set and the table being searchable based at least in part on the pair of indices, the table having a primary key comprising a hash key and a hash range;

receive a request to query the table, the request specifying, for an index of the pair of indices, a record associated with the index; and

in response to the request;

identify the table based at least in part on the pair of indices; and

search the table to yield a resulting record, the resulting record belonging to an index of the plurality of indices that is different than the pair of indices.

15. The non-transitory computer-readable storage medium of claim 14, wherein:

the non-transactional database is a NoSQL database; and

a first index of the at least one pair of indices is assigned as the hash key and a second index of the at least one pair of indices is assigned as the hash range.

16. The non-transitory computer-readable storage medium of claim 14, wherein the instructions that cause the computer system to receive the request to query the table further include instructions that cause the computer system to:

receive an application programming interface (API) function call to query the table; and

the API function call specifies a limit on a number of the resulting records provided in response to the request.

17. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

filter the resulting record based at least in part on one or more filtering parameters; and

provide the filtered resulting record as a query result.

18. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

receive a request to add a new record to the data set; and

cause the new record to be added to one or more tables associated with the data set.

19. The non-transitory computer-readable storage medium of claim 18, wherein the instructions that cause the computer system to cause the new record to be added to the one or more tables further include instructions that cause the computer system to:

search a table of the one or more tables to determine whether the new record is in conflict with an existing record; and

on a condition that the new record is in conflict with the existing record, append one or more characters to the new record to distinguish the new record from the existing record.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions that cause the computer system to append the one or more characters to the new record further include instructions that cause the computer system to:

determine a number of matching records in the table;

sequentially assign a number to the new record based at least in part on the number of matching records in the table; and

append the new record with the sequentially assigned number.