Pruning of spatial queries using index root MBRS on partitioned indexes

• US 20060155679A1
• Filed: 01/07/2005
• Published: 07/13/2006
• Est. Priority Date: 01/07/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ravada, Siva, Kothuri, Ravikanth V.
• Granted Patent: US 7,877,405 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A method, system, and computer program product provides improved performance for queries on local partitioned indexes. A method of performing a database query comprises receiving a query of spatial data in a database, the database comprising at least one partitioned spatial index, obtaining metadata relating to all partitions of the spatial index using array-fetching techniques, determining, for each partition, whether the partition is relevant to the query by comparing with “footprint” (root_mbr) information stored in the metadata for the partition, and processing the query on each relevant partition.

Claims

1. A method of performing a database query comprising:

receiving a query of spatial data in a database, the database comprising at least one partitioned spatial index;

obtaining metadata relating to all partitions of the spatial index;

determining, for each partition, whether the partition is relevant to the query, using the metadata for the partition; and

processing the query on each relevant partition.

2. The method of claim 1, wherein the metadata for a partition comprises a minimum bounding rectangle for spatial data in the partition.

3. The method of claim 2, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with a minimum bounding rectangle for the query.

4. The method of claim 3, wherein the query is further processed on each relevant partition by performing an exact comparison of the query and index-information in the index for the partition.

5. The method of claim 3, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with the query.

6. The method of claim 1, wherein the metadata relating to all partitions of the spatial index is obtained by:

obtaining all columns of metadata for a first partition of the spatial index; and

obtaining distinct columns of metadata for all partitions.

7. The method of claim 6, wherein the distinct columns of metadata are columns that have different values for different partitions.

8. The method of claim 6, wherein the distinct columns of metadata for all partitions are obtained using an array fetch technique.

9. A system for performing a database query comprising:

a processor operable to execute computer program instructions;

a memory operable to store computer program instructions executable by the processor; and

computer program instructions stored in the memory and executable to perform the steps of;

receiving a query of spatial data in a database, the database comprising at least one partitioned spatial index;

obtaining metadata relating to all partitions of the spatial index;

determining, for each partition, whether the partition is relevant to the query, using the metadata for the partition; and

processing the query on each relevant partition.

10. The system of claim 9, wherein the metadata for a partition comprises a minimum bounding rectangle for spatial data in the partition.

11. The system of claim 10, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with a minimum bounding rectangle for the query.

12. The system of claim 11, wherein the query is further processed on each relevant partition by performing an exact comparison of the query with the index information fro the partition.

13. The system of claim 12, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with the query.

14. The system of claim 11, wherein the metadata relating to all partitions of the spatial index is obtained by:

obtaining all columns of metadata for a first partition of the spatial index; and

obtaining distinct columns of metadata for all partitions.

15. The system of claim 14, wherein the distinct columns of metadata are columns that have different values for different partitions.

16. The system of claim 14, wherein the distinct columns of metadata for all partitions are obtained using an array fetch technique.

17. A computer program product for performing a database query comprising:

a computer readable medium;

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of

receiving a query of spatial data in a database, the database comprising at least one partitioned spatial index;

obtaining metadata relating to all partitions of the spatial index;

determining, for each partition, whether the partition is relevant to the query, using the metadata for the partition; and

processing the query on each relevant partition.

18. The computer program product of claim 17, wherein the metadata for a partition comprises a minimum bounding rectangle for spatial data in the partition.

19. The computer program product of claim 18, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with a minimum bounding rectangle for the query.

20. The computer program product of claim 19, wherein the query is processed on each relevant partition by performing an exact comparison of each point, boundary, area, or extent of the query with each point, boundary, area, or extent of the data in the partition.

21. The computer program product of claim 18, wherein it is determined whether a partition is relevant to the query by determining whether the minimum bounding rectangle for spatial data in the partition intersects with the query.

22. The computer program product of claim 21, wherein the query is further processed on each relevant partition by performing an exact comparison of the query with the index information for the partition.

23. The computer program product of claim 17, wherein the metadata relating to all partitions of the spatial index is obtained by:

obtaining all columns of metadata for a first partition of the spatial index; and

obtaining distinct columns of metadata for all partitions.

24. The computer program product of claim 23, wherein the distinct columns of metadata are columns that have different values for different partitions.

25. The computer program product of claim 23, wherein the distinct columns of metadata for all partitions are obtained using an array fetch technique.