Methods and systems for latency-free database queries

• US 8,914,405 B2
• Filed: 05/10/2011
• Issued: 12/16/2014
• Est. Priority Date: 10/08/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Jagota, Arun Kumar, Ming, Lei, Wong, Fang, Nachnani, Pawan
• Primary Examiner(s): SOMERS, MARC S
• Application Number:
  US13/104,193
• Publication Number:
  US 20120089647A1
• Time in Patent Office: 1,316 Days
• Field of Search: 707/705, 707/758, 707/769, 707/791, 707/797, 707/741
• US Class Current: 707/769
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24558 Binary matching operations

Abstract

Systems and methods for performing latency-free database searches using two-level indexed data structures having decreasing integer sets as identifiers to represent actual data. The indexed data structures are stored in distributed memory. Data operations such as intersection and union are performed using the indexed data structures. A binary interval reduction technique is used to quickly move through the data sets looking for common elements for the intersection set, or unique elements to add to the union set.

Claims

1. A method for operating a database apparatus, comprising:

storing each of a plurality of data identifiers in a distributed memory apparatus as a two-level indexed data structure, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each integer in the first unique set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

performing a query operation using the data identifiers and storing the result of the query operation in the distributed memory apparatus as a resultant two-level data structure, the query operation finding a union set between a first data structure and a second data structure by performing a first series of comparison operations between the first level integer sets of the first and second data structures to identify matched and unmatched integers in the first level integers sets;

if a first integer in the first level of the first data structure is not found in the first level of the second data structure, retrieving the unique set of second level integers that is linked to the first integer and storing the unique set of second level integers in the second level of an indexed data structure, and adding the first integer to the union set;

if a matched integer is identified in the first level integers sets, performing a second series of comparison operations between the second level integer sets of the first and second data structures to identify matched and unmatched integers in the second level integer set of the first and second data structures, and storing the matched unmatched integers in the second level of the second data structure with a link to the matched integer in the first level of the second data structure; and

repeating the steps of performing the first and second series of comparison operations until done.

2. The method of claim 1, wherein the first portion of the data identifier is a most significant bits portion and the second portion of the data identifier is a least significant bits portion.

3. The method of claim 1, further comprising:

shifting the first level of the resultant two-level data structure to the left by a specified number of bits and then adding the second level of the resultant two-level data structure thereby obtaining a resultant data identifier;

locating and retrieving the actual data corresponding to the resultant data identifier; and

returning the actual data to a user.

4. The method of claim 1, wherein the distributed memory apparatus comprises memcached storage.

5. The method of claim 1, wherein the first series of comparison steps comprises:

a first comparison step for comparing a plurality of the first level integers of the first data structure to a single integer of the first level integers of the second data structure; and

a second comparison step for comparing a plurality of the first level integers of the second data structure to a single integer of the first level integers of the first data structure.

6. The method of claim 5, wherein the first comparison step comprises:

initializing a first pointer and a second pointer to point to the highest integer value in the first level integer sets of the first and second data structures, respectively;

comparing in a first step the value at the first pointer to the value at the second pointer;

if the value at the first pointer is greater than the value at the second pointer, then retrieving the unique set of integers that is linked to the value at the first pointer, storing the unique set of integers in the second level of an indexed data structure, and adding the value at the first pointer to the union set;

moving the first pointer in accord with the binary interval reduction process and returning to the first step;

if the value at the first pointer is less than the value at the second pointer, then moving the second pointer in accord with the binary interval reduction process and returning to the first step, unless the last move of the second pointer was to the left, and if so, then performing the second comparison step; and

if the value at the first pointer is equal to the value at the second pointer, then performing the second series of comparison operations.

7. The method of claim 5, wherein the second comparison step comprises:

moving the second pointer in accord with the binary interval reduction process,

comparing in a second step the value at the first pointer to the value at the second pointer;

if the value at the first pointer is greater than the value at the second pointer, then moving the first pointer in accord with the binary interval reduction process and returning to the second step, unless the last move of the first pointer was to the left, and if so, then ending the process;

if the value at the first pointer is less than the value at the second pointer, then moving the second pointer in accord with the binary interval reduction process and returning to the second step, unless the last move of the second pointer was to the left, and if so, then ending the process; and

if the value at the first pointer is equal to the value at the second pointer, then performing the second series of comparison operations.

8. The method of claim 1, wherein a plurality of query operations are performed in parallel using the distributed memory.

9. The method of claim 1, further comprising performing the first series of comparison operations and the second series of comparison using a binary interval reduction process.

10. The method of claim 9, wherein the second series of comparison steps comprises:

a third comparison step for comparing a plurality of the second level integers of the first data structure to a single integer of the second level integers of the second data structure; and

a fourth comparison step for comparing a plurality of the second level integers of the second data structure to a single integer of the second level integers of the first data structure.

11. The method of claim 10, wherein the third comparison step comprises:

initializing a third pointer and a fourth pointer to point to the highest integer value in the second levels of the first data structure and the second data structure, respectively;

comparing in a third comparison step the value at the third pointer to the value at the fourth pointer;

if the value at the third pointer is greater than the value at the fourth pointer, then moving the third pointer in accord with the binary interval reduction process and returning to the third comparison step;

if the value at the third pointer is less than the value at the fourth pointer, then moving the fourth pointer in accord with the binary interval reduction process and returning to the first comparison step, unless the last move of the fourth pointer was to the left, and if so, then ending the process; and

if the value at the third pointer is equal to the value at the fourth pointer, then saving and storing the matched integer value at the first and second pointers together with the matched integer value at the third and fourth pointers in a two level representation in the distributed memory, and

incrementing a first index value and a second index value, then moving the first pointer to the integer value indicated by the first index value and moving the second pointer to the integer value indicated by the second index value; and

returning to the first series of comparison operations.

12. The method of claim 10, wherein the fourth comparison step comprises:

moving the fourth pointer in accord with the binary interval reduction process,

comparing in a fourth step the value at the third pointer to the value at the fourth pointer;

if the value at the third pointer is greater than the value at the fourth pointer, then moving the third pointer in accord with the binary interval reduction process and returning to the second step;

if the value at the third pointer is less than the value at the fourth pointer, then moving the fourth pointer in accord with the binary interval reduction process and returning to the second step, unless the last move of the fourth pointer was to the left, and if so, then end the process; and

if the value at the third pointer is equal to the value at the fourth pointer, then saving and storing the matched integer value at the first and second pointers together with the matched integer value at the third and fourth pointers in a two level representation in the distributed memory, and

incrementing a first index value and a second index value, then moving the first pointer to the integer value indicated by the first index value and moving the second pointer to the integer value indicated by the second index value; and

returning to the first series of comparison operations.

13. The method of claim 9, wherein the binary interval reduction process comprises:

in a first move within a search interval, moving the relevant pointer to the right from the highest integer value to the lower integer value; and

in subsequent moves, reducing the search interval, then moving the relevant pointer to the halfway point of the reduced search interval.

14. A method for operating a database apparatus, comprising:

storing each of a plurality of data identifiers in a distributed memory apparatus as a two-level indexed data structure, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each integer in the first unique set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

performing a query operation using the data identifiers and storing the result of the query operation in the distributed memory apparatus as a resultant two-level data structure, the query operation finding an intersection set between a first data structure and a second data structure by performing a first series of comparison operations between the first level integer sets of the first and second data structures to identify a first matching integer in the first level integer sets, the first series of comparison steps including a first comparison step for comparing a plurality of the first level integers of the first data structure to a single integer of the first level integers of the second data structure and a second comparison step for comparing a plurality of the first level integers of the second data structure to a single integer of the first level integers of the first data structure;

if a first matching integer is identified in the first level integer sets, performing a second series of comparison operations between the second level integer sets of the first and second data structures that are linked to the first matching integer in the first level integer sets process to identify at least one second matching integer in the second level integer sets of the first and second data structures;

if at least one second matching integer is identified in the second level integer sets, storing the first and second matching integers as an intersection set having the indexed data structure in distributed memory; and

repeating the steps of performing the first and second series of comparison operations until done.

15. The method of claim 14, further comprising performing the first series of comparison operations and the second series of comparison using a binary interval reduction process.

16. The method of claim 15, wherein the first comparison step comprises:

initializing a first pointer and a second pointer to point to the highest integer value in the first level integer sets of the first and second data structures, respectively;

comparing in a first step the value at the first pointer to the value at the second pointer;

if the value at the first pointer is greater than the value at the second pointer, then moving the first pointer in accord with the binary interval reduction process and returning to the first step;

if the value at the first pointer is less than the value at the second pointer, then moving the second pointer in accord with the binary interval reduction process and returning to the first step, unless the last move of the first pointer was to the left, and if so, then performing the second comparison step; and

if the value at the first pointer is equal to the value at the second pointer, then performing the second series of comparison operations.

17. The method of claim 15, wherein the second comparison step comprises:

moving the second pointer in accord with the binary interval reduction process,

comparing in a second step the value at the first pointer to the value at the second pointer;

if the value at the first pointer is greater than the value at the second pointer, then moving the second pointer in accord with the binary interval reduction process and returning to the second step;

if the value at the first pointer is less than the value at the second pointer, then moving the second pointer in accord with the binary interval reduction process and returning to the second step, unless the last move of the second pointer was to the left, and if so, then ending the process; and

if the value at the first pointer is equal to the value at the second pointer, then performing the second series of comparison operations.

18. The method of claim 15, wherein the second series of comparison steps comprises:

a third comparison step for comparing a plurality of the second level integers of the first data structure to a single integer of the second level integers of the second data structure; and

a fourth comparison step for comparing a plurality of the second level integers of the second data structure to a single integer of the second level integers of the first data structure.

19. The method of claim 18, wherein the third comparison step comprises:

initializing a third pointer and a fourth pointer to point to the highest integer value in the second level integer sets of the first data structure and the second data structure, respectively;

comparing in a third step the value at the third pointer to the value at the fourth pointer;

if the value at the third pointer is greater than the value at the fourth pointer, then moving the third pointer in accord with the binary interval reduction process and returning to the third step;

if the value at the third pointer is less than the value at the fourth pointer, then moving the fourth pointer in accord with the binary interval reduction process and returning to the first step, unless the last move of the fourth pointer was to the left, and if so, then ending the process;

if the value at the third pointer is equal to the value at the fourth pointer, then saving and storing the matched integer value at the first and second pointers together with the matched integer value at the third and fourth pointers in a two level representation in the distributed memory,

incrementing a first index value and a second index value, then moving the first pointer to the integer value indicated by the first index value and moving the second pointer to the integer value indicated by the second index value; and

returning to the first series of comparison operations.

20. The method of claim 18, wherein the fourth comparison step comprises:

moving the fourth pointer in accord with the binary interval reduction process,

comparing in a fourth step the value at the third pointer to the value at the fourth pointer;

if the value at the third pointer is greater than the value at the fourth pointer, then moving the third pointer in accord with the binary interval reduction process and return to the second step;

if the value at the third pointer is less than the value at the fourth pointer, then moving the fourth pointer in accord with the binary interval reduction process and returning to the second step, unless the last move of the fourth pointer was to the left, and if so, then end the process; and

if the value at the third pointer is equal to the value at the fourth pointer, then saving and storing the matched integer value at the first and second pointers together with the matched integer value at the third and fourth pointers in a two level representation in the distributed memory,

incrementing a first index value and a second index value, then moving the first pointer to the integer value indicated by the first index value and moving the second pointer to the integer value indicated by the second index value; and

returning to the first series of comparison operations.

21. The method of claim 15, wherein the binary interval reduction process comprises:

in a first move, moving the relevant pointer to the right from the highest integer value to a lower integer value; and

in subsequent moves, reducing the search interval, then moving the relevant pointer to halfway point of the reduced interval.

22. The method of claim 14, wherein a plurality of query operations are performed in parallel using the distributed memory.

23. The method of claim 14, wherein the first portion of the data identifier is a most significant bits portion and the second portion of the data identifier is a least significant bits portion.

24. The method of claim 14, further comprising:

shifting the first level of the resultant two-level data structure to the left by a specified number of bits and then adding the second level of the resultant two-level data structure thereby obtaining a resultant data identifier;

locating and retrieving the actual data corresponding to the resultant data identifier; and

returning the actual data to a user.

25. A machine-readable medium having one or more sequences of instructions for performing a database search, which instructions, when executed by one or more processors, cause the one or more processors to:

store each of a plurality of data identifiers in a distributed memory apparatus as a two-level indexed data structure, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each unique integer in the first set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

perform a query operation for desired data attributes using the data identifiers and store the result in the distributed memory as a resultant two-level data structure, the query operation finding a union set between a first data structure representing a first data attribute and a second data structure representing a second data attribute by performing a first series of comparison operations between the first level of the first data structure and the first level of the second data structure to identify matched and unmatched integers in the first level of the first and second data structures;

if a first integer in the first level of the first data structure is not found in the first level of the second data structure, then retrieve the unique set of integers that is linked to the first integer and store the unique set of integers in the second level of an indexed data structure, and add the first integer to the union set, and

if a matched integer is identified in the first level of the first and second data structures, then perform a second series of comparison operations between the second level of the first data structure and the second level of the second data structure to identify matched and unmatched integers in the second level of the first data structures, and store the matched and unmatched integers in the second level of the second data structure with a link to the matched integer in the first level of the second data structure; and

repeat the steps of performing the first and second series of comparison operations until done.

26. A machine-readable medium having one or more sequences of instructions for performing a database search, which instructions, when executed by one or more processors, cause the one or more processors to:

store each of a plurality of data identifiers in a distributed memory apparatus as a two-level indexed data structure, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each unique integer in the first set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

perform a query operation for desired data attributes using the data identifiers and store the result in the distributed memory as a resultant two-level data structure, the query operation finding an intersection set between a first data structure and a second data structure by performing a first series of comparison operations between the first level of the first data structure and the first level of the second data structure to identify a first matching integer in the first level of the first and second data structures, the first series of comparison steps including a first comparison step for comparing a plurality of the first level integers of the first data structure to a single integer of the first level integers of the second data structure and a second comparison step for comparing a plurality of the first level integers of the second data structure to a single integer of the first level integers of the first data structure;

when a first matching integer is identified in the first level of the first and second data structures, performing a second series of comparison operations between the second level of the first data structure that is linked to the first matching integer and the second level of the second data structure that is linked to the first matching integer to identify a second matching integer in the second level of the first and second data structures;

when a second matching integer is identified in the second level of the first and second data structures, storing the first and second integer as an intersection set; and

repeating the steps of performing the first and second series of comparison operations until done.

27. A data management apparatus, comprising:

a database having a plurality of data records stored therein;

a database manager program having executable instructions for managing storage, indexing and retrieval of the data records, including first and second instructions;

a distributed memory system accessible to the database and operable in accord with the first instructions of the database manager program, said first instructions for;

storing data identifiers for the data records in the distributed memory apparatus as two-level indexed data structures, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each integer in the first unique set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

a search interface in communication with the database manager program and operable in accord with second instructions, said second instructions for performing query operations on the data records using the indexed data structures to find an intersection set between a first data structure and a second data structure by performing a first series of comparison operations between a first level of the first data structure and a first level of the second data structure to identify a first matching integer in the first level of the first and second data structures, the first series of comparison steps including a first comparison step for comparing a plurality of the first level integers of the first data structure to a single integer of the first level integers of the second data structure and a second comparison step for comparing a plurality of the first level integers of the second data structure to a single integer of the first level integers of the first data structure;

when a first matching integer is identified in the first level of the first and second data structures, performing a second series of comparison operations between the second level of the first data structure that is linked to the first matching integer and the second level of the second data structure that is linked to the first matching integer to identify a second matching integer in the second level of the first and second data structures;

when a second matching integer is identified in the second level of the first and second data structures, storing the first and second integer as an intersection set; and

repeating the steps of performing the first and second series of comparison operations until done.

28. A data management apparatus, comprising:

a database having a plurality of data records stored therein;

a database manager program having executable instructions for managing storage, indexing and retrieval of the data records, including first and second instructions;

a distributed memory system accessible to the database and operable in accord with the first instructions of the database manager program, said first instructions for;

storing data identifiers for the data records in the distributed memory apparatus as two-level indexed data structures, wherein a first level of each data structure includes a first unique set of decreasing integers, wherein a second level of the data structure includes a plurality of unique sets of decreasing integers, wherein each of the plurality of unique sets is linked to one of the integers in the first unique set, wherein each integer in the first unique set represents a first portion of the data identifier and each unique integer in the plurality of sets represent a second portion of the data identifier;

a search interface in communication with the database manager program and operable in accord with second instructions, said second instructions for performing query operations on the data records using the indexed data structures to find a union set between the first data structure and the second data structure by performing a first series of comparison operations between the first level integer sets of the first and second data structures to identify matched and unmatched integers in the first level of the first and second data structures;

if a first integer of the first level of the first data structure is not found in the first level of the second data structure, retrieving the unique set of second level integers that is linked to the first integer and storing the unique set of second level integers in the second level of an indexed data structure, and adding the first integer to the union set;

if a matched integer is identified in the first level integer sets, performing a second series of comparison operations between the second level integer sets of the first and second data structures to identify matched and unmatched integers in the second level integer sets of the first and second data structures, and storing the matched and unmatched integers in the second level of the second data structure with a link to the matched integer in the first level of the second data structure; and

repeating the steps of performing the first and second series of comparison operations until done.