Efficient Database Searching

• US 20140317086A1
• Filed: 04/17/2013
• Published: 10/23/2014
• Est. Priority Date: 04/17/2013
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: James, Rick
• Granted Patent: US 9,501,526 B2
• Time in Patent Office: Days
• US Class Current: 707/715
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Systems and methods are disclosed for efficiently searching a database including a table. The table is partitioned along a first dimension, such as latitude. Indexes in each of the partitions are built along a second dimension, such as longitude. The table may also be clustered according to an index to improve performance. When a processor receives a database query term and a starting location, the processor selects, from the table, a data partition within a first offset to the starting location along the first dimension. The processor selects, from the selected data partition, a first number of first data records related to the query term and within a second offset to the starting location along the second dimension.

Claims

1. A database, comprising:

a first table of records comprising;

a first data partition being associated with a first range in a first dimension, the first data partition further being associated with a first index in a second dimension; and

a second data partition being associated with a second range in the first dimension, the second data partition further being associated with a second index in the second dimension.

2. The database of claim 1, further comprising:

a second table of records corresponding to the first table of records.

3. The database of claim 1, wherein at least one record of the first partition of the first table is selected for storage in a disk block based upon the first index in the second dimension.

4. The database of claim 1, wherein the first dimension comprises latitude, longitude, or distance from a reference location.

5. The database of claim 2, wherein the first dimension comprises latitude.

6. The database of claim 1, wherein the records of the first table include a primary key comprising a coordinate in the first dimension, a coordinate in the second dimension, and identification information.

7. The database of claim 6, wherein the primary key begins with the coordinate in the second dimension.

8. The database of claim 1, wherein the records of the second table further comprise a primary key corresponding to the first table of records.

9. A device comprising a processor configured to:

receive a request to access a database, wherein the request comprises query term and a starting location, the database comprises a first table of records comprising;

a first data partition being associated with a first range in a first dimension, the first data partition further being associated with a first index in a second dimension; and

a second data partition being associated with a second range in the first dimension, the second data partition further being associated with a second index in the second dimension;

select, from the first table, a data partition within a first offset to the starting location along the first dimension; and

select, from the selected data partition, a first number of first records related to the query term and within a second offset to the starting location along the second dimension.

10. The device of claim 9, wherein the database further comprises a second table of records corresponding to the first table of records.

11. The device of claim 9, wherein at least one record of the first partition of the first table is selected for storage in a disk block based upon the first index in the second dimension.

12. The device of claim 9, wherein the processor is configured to increase at least one of the first and second offsets and repeat the selections if the first number is less than a preset number.

13. The device of claim 10, wherein the processor is configured to select, from the second table, a second number of second data records based on the first number of first data records in the first table.

14. The device of claim 9, wherein the records of the first table include a first primary key comprising a coordinate in the first dimension, a coordinate in the second dimension, and identification information.

15. The device of claim 14, wherein the first primary key starts with the coordinate in the second dimension.

16. The device of claim 10, wherein the records of the second table further comprise a primary key corresponding to the first table of records.

17. The device of claim 9, wherein the first dimension is latitude, longitude, or distance from a reference location.

18. A computer implemented method, comprising:

receiving, by a processor, a request to access a database, wherein the request comprises query term and a starting location, the database comprises a first table of records comprising;

a first data partition being associated with a first range in a first dimension, the first data partition further being associated with a first index in a second dimension; and

a second data partition being associated with a second range in the first dimension, the second data partition further being associated with a second index in the second dimension;

selecting, by the processor, a data partition from the first table within a first offset to the starting location along the first dimension; and

selecting, from the selected data partition, a first number of first records related to the query term and within a second offset to the starting location along the second dimension.

19. The method of claim 18, wherein the database further comprises a second table of records corresponding to the first table of records.

20. The method of claim 19, further comprising selecting, from the second table, a second number of second records based on the first number of first data records in the first table.

21. The method of claim 18, further comprising increasing at least one of the first and second offsets and repeat the selections if the first number is less than a preset number.

22. The method of claim 18, wherein the records of the first table include a primary key comprising a coordinate in the first dimension, a coordinate in the second dimension, and identification information.

23. The method of claim 18, wherein the records of the second table further comprise a primary key corresponding to the first table of records.

24. The method of claim 18, wherein the first dimension is at least one of latitude, longitude, or distance from a reference location.