Tracking granularity levels for accessing a spatial index

Patent metadata

Field	Value
Publication number	US-11269930-B1
Application number	US-201715472093-A
Country	US
Kind code	B1
Filing date	Mar 28, 2017
Priority date	Mar 28, 2017
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

Abstract

A database engine may track granularity levels for accessing a spatial index. Granularity levels of a spatial index may be evaluated to identify those granularity levels that identify data objects in a data set. An indication of the identified granularity levels may be stored as part of metadata for the data set. When a spatial query directed to the data set is received, the spatial index may be accessed at the identified granularity levels indicated in the metadata for the data set as part of processing the spatial query.

First claim

What is claimed is:

1. A system, comprising:
a memory to store program instructions which, when performed by at least one processor, cause the at least one processor to perform a method to at least:
evaluate a plurality of granularity levels of a spatial index for a data set to identify one or more of the granularity levels that identify at least one data object stored in the data set, wherein the plurality of granularity levels of the spatial index comprises the one or more of the granularity levels that identify at least one data object stored in the data set and at least one remaining granularity level;
store an indication of the identified one or more of the granularity levels of the spatial index, identified in the evaluating, as part of metadata for the data set;
receive a spatial query directed to the data set; and
in response to receiving the spatial query:
obtain the indication of the identified one or more of the granularity levels of the spatial index from the metadata for the data set; and
evaluate the spatial index at individual ones of the identified one or more of the granularity levels of the obtained indication to process the spatial query with respect to the data set, wherein the evaluating of the spatial index is not performed at the at least one remaining granularity level of the spatial index;
scan the at least one remaining granularity level to determine the existence of data objects in the data set; and
responsive to determining that at least one data object exists in the at least one remaining granularity level:
retrieve the at least one data object from the data set; and
evaluate the at least one data object to process the spatial query with respect to the data set.

2. The system of claim 1 , wherein the method further comprises detect an event for updating granularity level tracking data, wherein the evaluation of the granularity levels and the storage of the indication of the identified granularity levels is performed in response to the detection of the event for updating the granularity level tracking data.

3. The system of claim 1 , wherein the method further comprises:
further in response to receiving the spatial query, generate a query execution plan that includes operations to evaluate the spatial index at the identified granularity levels, wherein the evaluation of the spatial index at the identified granularity levels to process the query is performed according to the query execution plan.

4. The system of claim 1 , wherein the evaluation of the granularity levels, the storage of the indication of the granularity levels, the receipt of the spatial query, the obtain of the identified granularity levels and the evaluation of the spatial index are performed by a database engine implemented as part of a network-based database service, wherein the spatial query is received via a network interface for the database service, wherein the data set is stored in a network-based data storage service, wherein the database service and the data storage service are implemented as part of the same network-based services platform, and wherein the spatial query is received via a network interface for the database service.

5. A method, comprising:
evaluating a plurality of granularity levels of a spatial index for a data set to identify one or more of the granularity levels that identify at least one data object stored in the data set, wherein the plurality of granularity levels of the spatial index comprises the one or more of the granularity levels that identify at least one data object stored in the data set and at least one remaining granularity level;
receiving a spatial query directed to the data set; and
in response to receiving the spatial query;
accessing the spatial index at individual ones of the identified one or more of the granularity levels to process the spatial query with respect to the data set, wherein the accessing of the spatial index is not performed at the at least one remaining granularity level of the spatial index;
scanning the at least one remaining granularity level to determine the existence of data objects in the data set; and
responsive to determining that at least one data object exists in the at least one remaining granularity level, accessing the at least one data object to process the spatial query with respect to the data set.

6. The method of claim 5 , further comprising detecting an event for updating granularity level tracking data, and wherein the evaluating the granularity levels of the spatial index is performed in response to the detection of the event for updating the granularity level tracking data.

7. The method of claim 6 , wherein detecting the event for updating the granularity level tracking data comprises determining that an amount of updates to the data set exceeds an update threshold for the granularity level tracking data.

8. The method of claim 6 ,
wherein the method further comprises storing respective indications for the identified granularity levels in metadata for the data in response to detecting the event; and
wherein accessing the spatial index at the identified granularity levels comprises obtaining the identified granularity levels from metadata for the data set.

9. The method of claim 5 , further comprising:
further in response to receiving the spatial query, generating a query execution plan that includes operations to evaluate the spatial index at the identified granularity levels, wherein the accessing of the spatial index at the identified granularity levels to process the query is performed according to the query execution plan.

10. The method of claim 9 , wherein generating the query execution plan comprises generating one or more operations to scan remaining ranges of granularity levels in the spatial index not identified in the evaluating of the plurality of granularity levels for the existence of data objects.

11. The method of claim 9 , further comprising:
determining, as part of performing the operations to scan remaining ranges of granularity levels, that a number of data objects identified by a scanned level exceeds a probe threshold; and
modifying the query execution plan to include an operation that evaluates the scanned level of the spatial index as part of processing the spatial query.

12. The method of claim 5 , wherein data objects stored in the data set are represented as floating point values in a Geographic Information Systems (GIS) data format.

13. The method of claim 5 , wherein the evaluating, the receiving,
and the accessing are performed by a database engine implemented as part of a network-based database service and wherein the spatial query is received via a network interface for the database service.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:
evaluating a plurality of granularity levels of a spatial index for a data set to identify one or more of the granularity levels that identify at least one data object stored in the data set, wherein the plurality of granularity levels of the spatial index comprises the one or more of the granularity levels that identify at least one data object stored in the data set and at least one remaining granularity level;
receiving a spatial query directed to the data set; and
in response to receiving the spatial query;
evaluating the spatial index at individual ones of the identified one or more of the granularity levels to process the spatial query with respect to the data set, wherein the evaluating of the spatial index i

Assignees

• Amazon Tech Inc

Inventors

• Davis Jeffrey

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title