Abstract:
Techniques of querying an index of first objects comprised of a plurality of index entries and a pool of second objects are provided. The techniques include evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query, adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates, filtering the interim group of possible candidates by comparing approximations of the candidates of the interim group with the query to produce filtered candidate objects, and determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a divisional application of and claims the benefit of “Reducing Index Size for Multi-Level Grid Indexes”, having application Ser. No. 10/141,919, filed May 10, 2002, the entire contents of which are incorporated herein by reference. 
     The present application is related to U.S. application Ser. No. 10/144,058, filed May 10, 2002, entitled “Systems, Methods, and Computer Program Products to Improve Indexing of Multidimensional Databases,” the entire contents of which are incorporated herein by reference. 
     The present application is also related to U.S. application Ser. No. 10/144,389, filed May 10, 2002, entitled “Systems, Methods, And Computer Program Products To Reduce Computer Processing In Grid Cell Size Determination For Indexing Of Multidimensional Databases,” the entire contents of which are incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention is directed to the field of computer-based database management systems. It is more particularly directed to reducing index size when grid-indexing techniques are applied to multidimensional data stored in a database management system. 
     2. Description of the Background Art 
     Indexing techniques are used to quickly access data that has been sorted and assigned an index. Spatial data is typically information associated with geometric shapes such as lines, points, poly-lines, polygons, and surfaces. Spatial data is often very large and may have two, three, or more dimensions. Spatial data may be indexed. Indexing such data by traditional techniques, such as with a B-tree, may not be feasible due to the large amount of computer resources required to index spatial data. Further, B-tree indexing is typically associated with single-dimensional data, not multidimensional data. Therefore, sorting capabilities associated with B-tree indexing are typically not sufficient to be efficiently applied to multidimensional data. To reduce data processing time, various spatial indexing techniques have been studied and developed. Grid indexing is one of these indexing techniques associated with searching spatial multidimensional data, and is used by the product marketed under the trademark IBM DB2® Spatial Extender. 
     An index enables fast access to a certain subset of data contained in a larger set of data. The index can include a data structure and indicators of the techniques used to build, maintain, and search the data structure for the purpose of accessing a subset of data. For example, an index may define a data structure that is used to access a specific geometric shape included in a set of spatial data. The particular index of the present example may define a data structure that contains references to the minimum-bounding rectangles associated with various geometric shapes in a spatial data set. By accessing locator references associated with the minimum-bounding rectangles the process of accessing particular geometric shapes in a spatial data set is simplified. 
     A grid index is a space-partitioning. It divides space into rectangles (or squares) called grid cells, using a mathematical formula to determine the boundaries of the grid cells. One approach for such a formula is to define a grid cell size and to lay each boundary as a multiple of the grid cell size. When indexing spatial objects (geometries), the geometries are overlaid with the so defined grid. Depending on the size of the geometry and the grid cell size, a geometry might overlap with more than one grid cell, i.e. it crosses a boundary between grid cells. 
     When a geometry is indexed in an index maintenance operation, an index key is stored in the index for each grid cell that overlaps with the geometry. Usually, the index entry uniquely identifies the grid cell for which the overlap was noted. For example, the identifier used for the index can be any point in the grid cell, such as its lower-left corner, or its center. Alternatively, other techniques for identifying the overlapping grid cell can be used for the identifier, such as dividing the coordinates by the grid size. For example, using a grid size of 10 with the coordinate value ( 46 ,  32 ) and performing integer arithmetic would identify the grid cell ( 4 ,  3 ) where “ 4 ” represents the fourth grid cell in one dimension and “ 3 ” represents the third grid cell in another dimension. 
     Several approaches exist to improve performance of the index maintenance. As previously mentioned, the geometry itself is abstracted by its minimum-bounding rectangle (MBR). That allows for a very simple and fast way to identify the grid cells that overlap with the MBR. 
     As can be appreciated, a geometry, or its MBR, potentially can overlap many grid cells. Although the computation of the identifiers for all the overlapping grid cells is straightforward if the geometry is abstracted, the task to compute all those identifiers grows linearly with the number of overlaps encountered. Also, storage is needed for all the index entries, which effectively increases costs for storage, and also increases the cost of evaluation of the index because more index entries have to be processed at query time. 
     A conventional approach to reduce costs is to introduce multiple levels of grids, each level with a different grid size. A geometry is indexed at exactly one grid level. Accordingly, with a larger grid size, fewer index entries are produced. However, the downside of using larger grid sizes is that they do not provide as fine a resolution as smaller grid sizes. 
     Some implementations of grid indexes (e.g., a grid index implemented in the DB2® Spatial Extender) use a fixed number that sets the maximum number of levels. Although using multiple levels reduces the problem of having many index entries for large geometries, the problem does not entirely vanish. Even at the coarsest grid level, an extremely large geometry can produce thousands of index entries. Also, the grid sizes for the multiple levels are usually tuned to work best for the common set of data and are not tuned for handling such exceptions. 
     To provide an example, assume two grid levels and the data set to be indexed is the street network of the United States of America. One will probably choose a very small grid size to accommodate the short streets in neighborhoods. The second grid size might be used to accommodate longer streets in cities or between cities. Consider now a road like the I-40 highway, that crosses the entire continent from west to east. Indexing this road on either of the two levels produces a vast number of index entries, whose computation is expensive and which greatly increases the number of indices. This complicates the maintenance of the indices and impacts the data processing capabilities of a database management system underlying the storage of the spatial data. 
     A conventional approach to handling such large geometries is not to allow such geometries to be indexed at all. If a geometry would produce more index entries than what is defined by a threshold, an error is returned in that conventional approach. In a database context such as the context in which the DB2® Spatial Extender runs, this implies that an insert or update operation would abort due to error. 
     The conventional approach leaves the user with a number of potentially unattractive options, e.g. to not use an index at all, to not insert the geometry, to break the geometry up into smaller pieces, or to change the index definition to use coarser grid sizes and thus reduce the number of entries produced. A problem with this last option is that changing the index impacts existing data, possibly making performance of the overall index worse. 
     SUMMARY OF THE INVENTION 
     Described here are techniques of querying an index of first objects comprised of a plurality of index entries and a pool of second objects. The techniques include evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query, adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates, filtering the interim group of possible candidates by comparing approximations of the candidates of the interim group with the query to produce filtered candidate objects, and determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query. 
     Also described here are methods of querying both a grid index of first geometric shapes that includes a plurality of indexes and a pool of larger, second geometric shapes. The method includes evaluating the grid index of first shapes to produce a group of one or more candidates based on cells designated in a query that overlap respective first shapes in the index. The geometric shapes from the pool are added to the group of candidates to produce an interim group of candidates. The interim group of candidates is filtered by comparing a query area specified in the query with approximations of the candidates of the interim group to produce filtered candidate objects. Those filtered candidates that satisfy the query are determined by comparing the first and second geometric shapes corresponding to the filtered candidates with the query area. The shapes that overlap with the query area are determined to satisfy the query. 
     Usage of a storage pool for large geometric shapes reduces the number of entries in the index and improves maintenance and use of the index. 
     Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the following detailed description and in the several figures of the drawings, like elements are identified with like reference numerals. 
         FIG. 1A  is a block diagram that illustrates a client-server computer configuration. 
         FIG. 1B  is a block diagram that illustrates an index-pool module; 
         FIG. 2A  is a diagramatic illustration of a multidimensional data cube. 
         FIG. 2B  depicts a grid and geometric shapes. 
         FIG. 2C  depicts a larger grid portion than  FIG. 2B . 
         FIG. 2D  is a block diagram that illustrates a table relating geometric shapes with an identifier, and index data structures. 
         FIG. 2E  is a block diagram that illustrates a pool data structure and a table relating geometric shapes with an identifier. 
         FIG. 3A  is a flow diagram that illustrates an embodiment of determining whether to store an index in a pool storage area; 
         FIG. 3B  is a flow diagram that illustrates a further embodiment of determining whether to store an index in a pool storage area; 
         FIG. 3C  is a flow diagram that illustrates an embodiment using indices stored in the pool storage area. 
         FIG. 4  is a block diagram of a computer system suitably configured for employment of the present invention. 
     
    
    
     DESCRIPTION OF THE INVENTION 
     As shown in  FIG. 1A , a method of indexing large geometries and using those indices can operate in a client-server computer system  100  configuration. Therefore, a client computer system  104  can communicate with a server computer system  102  during such operation. An index-pool module  120  operates in either the client  104  or the server  102  to store and use such indices. For example, information can be communicated to either the server  102  or the client  104  via a user interface  117  and subsequently can be used by an index-pool module  120  to perform a query operation regarding geometric shapes. The user interface  117  can include either a user input unit  118  and/or a batch input unit  119 . 
     Further, a multidimensional data cube  106  can be configured in the memory of either the client  104  or the server  102 . Alternatively, a multidimensional data cube  106  can be configured in computer storage such as that of a disk  122 . Spatial data  124  is a specific type of multidimensional data  110  that can be stored on disk  122 . The terms “multidimensional data cube” and “data cube” will be used interchangeably herein. 
       FIG. 1B  is a block diagram that illustrates the index-pool module  120  used to operate on the spatial data  124 . Spatial data  124  and other elements of the index pool module  120  are described below with reference to  FIG. 1A  and elements  202 ,  204 , and  206  of a multidimensional data cube  106  are described with reference to  FIG. 2A . A technique for partitioning space into grids  202  can include ascribing different levels  138  to the partitioned space. The levels  138  can represent partitions of the space at various resolutions of the cells  206  of the grid  202 . Such levels  138  can be used in connection with designating indices for large geometries. The variable “N,” represents the number of grid levels  142 . If the number of grid cells  146  exceeds a user-defined limit  151  the next level  138  of information is determined. Grid index  132  stores geometric shape information and is used to search spatial data  124 . 
     A geometric shape identifier (ID)  134  is used during the operation to identify a geometric shape so that the information associated with the geometric shape  204 , as shown in  FIG. 2B , can be indexed. The geometric shape ID  134  and the associated level  138  information are combined into the geometric shape ID  134  that is a single, unique value. That single, unique value is identified with the associated grid cell  206 . Information about higher level abstractions of a geometric shape, such as its minimum boundary rectangle, can be stored with the exact geometric shape or can be stored separately from it, such as in the index for the geometric shape. An SQL query that calls a “key generator” function  139  can be used to create index entries associated with each geometric shape  204 . 
     Storage pool  158  is a storage area that can be a separate data structure or can be embedded within the same data structure as the index. If the latter approach is chosen, the separate pool can be modeled as a special grid level, that has its own identifier but no associated grid size. Those geometries that exceed a certain threshold(s)  159  are stored in the storage pool  158 . A special query function  160  that includes data in both the grid index  132  and the storage pool  158  is included in the index pool module  120 . A query box area “Q b ”  140  is the average size of an area that is analyzed. The area covered by Q b    140  may be smaller than the size of the extent of data that is analyzed  149 . A preferred grid cell size “G”  148  can be determined, as disclosed in U.S. patent application Ser. No. 10/144,058, entitled “Systems, Methods, and Computer Program Products to Improve Indexing of Multidimensional Databases,” filed May 10, 2002, the entire contents of which are incorporated herein by reference. 
     As shown in  FIG. 2A  the multidimensional data cube  106  can be suitably configured for operation with the geometries to be processed. The grid  202  represents the decomposition of data into units that may be uniform or of varying size. Grid cell  206  is a specific instance of a unit contained within a grid  202 . Specific examples of grids  202  include the “X” dimension grid that is shown in element  208 , the “Y” dimension grid that is shown in element  210 , and the “Z” dimension grid that is shown in element  212 . 
       FIG. 2B  illustrates a two-dimensional grid  202 . A preferred embodiment operates on spatial data  124 , shown in  FIG. 1A , that is information that represents geometric shape  204 . The two-dimensional grid  202  includes examples of an X dimension grid  208  and a Y dimension grid  210 . Further, the X dimension grid  208  includes six units and the Y dimension grid  210  includes five units. The two-dimensional grid  202  includes grid cells  206  that can be referenced by the units of the X dimension grid  208  and the Y dimension grid  210 . The geometric shape “A” as shown in element  220 , the geometric shape “B” as shown in element  222 , and the geometric shape “C” as shown in element  226  are each bounded by minimum bounding rectangles (MBRs)  224   a,    224   b  and  224   c,  respectively. The variable Q b    140  represents a query box size and in this example Q b    140  overlaps two grid cells  206 . 
     Also present in  FIG. 2B  are geometric shapes  228  and  230 , which are larger than the other geometric shapes. For example, in a geographical context shapes  228  and  230  could represent long roads such as transcontinental highways. A better idea of the potential size of shapes  228  and  230  may be had by referring to  FIG. 2C  which shows a larger portion of the grid overlaid on these shapes. In actuality, shapes  228  and  230  could overlap thousands of grid cells. Here, large shapes such as  228  and  230  are excluded from the grid index and instead are stored in a storage pool. 
       FIG. 2D  is a block diagram that illustrates a table  240  relating geometric shapes  204  with geometric shape identifiers  134 .  FIG. 2D  also shows the index data structure  251 . An SQL statement can be used to generate the index data structure  251  that includes geometric shape ID&#39;s  134  and grid cell ID&#39;s  245 . For example, the geometric shape A  220  as shown in  FIG. 2B , is associated with the Row-A geometric shape ID, as shown in element  248 . Also, the geometric shape B  222  as shown in  FIG. 2B , is associated with the Row-B geometric shape ID, as shown in element  250 . Further, the geometric shape C  226  as shown in  FIG. 2B , is associated with the Row-C geometric shape ID, as shown in element  252 . 
     The geometric shape ID  134  and the grid cell ID  245  can be used jointly as an index to locate a specific geometric shape  204 . Indexes provide quick access to data and can enforce uniqueness on the rows in the table and include index entries, such as index entry  273  which is an entire row in the index data structure  251 , and includes a grid cell ID  245  and a geometric shape ID  134 . 
     The index data structure  251  is used to associate each grid cell  206  that overlaps with the MBR of a geometric shape thereby enabling searches of the information associated with a geometric shape. For example, the MBR of geometric shape A, as shown in element  224   a  of  FIG. 2B , overlaps will the following grid cells  206 ; grid cell ( 1 , 3 ) as shown in element  253  of  FIG. 2D , grid cell ( 2 , 3 ) as shown in element  254 , grid cell ( 3 , 3 ) as shown in element  256 , grid cell ( 1 , 4 ) as shown in element  258 , grid cell ( 2 , 4 ) as shown in element  260 , and grid cell ( 3 , 4 ) as shown in element  262 . Elements  253 ,  254 ,  256 ,  258 ,  260 , and  262  are therefore associated with Row-A geometric shape ID, as shown in element  248 . 
     Similarly, the MBR of geometric shape B, as shown in element  224   b  of  FIG. 2B , overlaps with the following grid cells  206 ; grid cell ( 4 , 2 ) as shown in element  264  of  FIG. 2D , grid cell ( 5 , 2 ) as shown in element  266 , grid cell ( 4 , 3 ) as shown in element  268 , grid cell ( 5 , 3 ) as shown in element  270 , grid cell ( 4 , 4 ) as shown in element  272 , and grid cell ( 5 , 4 ) as shown in element  274 . Elements  264 ,  266 ,  268 ,  270 ,  272 , and  274  overlap with the MBR of geometric shape B and are therefore associated with Row-B geometric shape ID, as shown in element  250 . 
     Also, the MBR of geometric shape C as shown in element  224   c  of  FIG. 2B  overlaps with the following grid cells  206 ; grid cell ( 1 , 5 ) as shown in element  275  of  FIG. 2D , grid cell ( 2 , 5 ) as shown in element  276 , grid cell ( 3 , 5 ) as shown in element  277 , grid cell ( 4 , 5 ) as shown in element  278 , grid cell ( 1 , 4 ) as shown in element  279 , grid cell ( 2 , 4 ) as shown in element  280 , grid cell ( 3 , 4 ) as shown in element  281 , and grid cell ( 4 , 4 ) as shown in element  282 . Elements  275 ,  276 ,  277 ,  278 ,  279 ,  280 ,  281 , and  282  are therefore associated with Row-C geometric shape ID, as shown in element  252 . 
     Conceptually, and optionally in practice, the storage pool is a separate and distinct storage area from the grid index. Because a filtering operation will be applied to all of the geometric shapes in the storage pool to determine if they are candidates for satisfying a query, there is no need to index those shapes in the storage pool. Accordingly, the storage pool can include a pool data structure that contains only identifiers of the geometric shapes stored in the pool. When the filtering operation occurs, all the identifiers in the storage pool are output so that those geometric shapes in the pool can be filtered. Here, the filtering is performed on the MBRs of the geometric shapes identified in the storage pool, and the MBRs of the geometric shapes in the pool can be stored in the storage pool data structure. 
     Alternatively, identifiers of the large geometric shapes that exceed a certain threshold, and hence are stored in the pool, can be stored in the grid index data structure along with the grid indexes.  FIG. 2E  illustrates a pool data structure  282  that is part of the grid index data structure. As shown in  FIG. 2E  the pool data structure  282  includes a pool ID field  283  and a geometric shape ID field  284 . The geometric shape ID is an identifier for a geometric shape that is so large as to exceed the threshold. Because geometric shape IDs in the pool are recorded with the grid cell indexes, an identifier is needed to designate those large geometric shapes as belonging to the pool and not to the grid index. The pool ID serves that purpose and can be any identifier that is different from the grid cell IDs  245 , shown in  FIG. 2D . An example of such a pool ID is shown in  FIG. 2E  in which an unused grid level, in this instance grid level “ 0 ”, operates as an indicator that the associated geometric shape is part of the pool and not part of the grid index. In  FIG. 2E , the geometric shape “D” has a geometric shape ID  284   a  of “Row_D” and an associated pool ID  283   a  of “Level  0 .” Similarly, another entry in the pool, geometric shape “E”, has a geometric shape ID  284   b  of “Row_E” and an associated pool ID  283   b  of “Level  0 .” Although the pool IDs of shapes “D” and “E” are identical, namely “Level  0 ”, they serve to designate those shapes as part of the pool and not part of the grid index. 
     Similar to table  240  in  FIG. 2D , a table  285  in  FIG. 2E  relates a geometric shape ID  286  with a geometric shape  288 . Here, the geometric shape ID  286   a  for shape “D” points to the area where geometric shape “D”  288   a  is stored. Similarly the geometric shape ID  286   b  for shape “E” points to the area where geometric shape “E”  288   b  is stored. 
     The flow diagram of  FIG. 3A  illustrates formation of the grid index and storage in a storage pool. A grid is first laid over the MBRs of a geometric shape, as depicted by operation  301 . A determination is then made as to whether the shape overlaps more than a threshold number of grid cells, as depicted by element  302 . If the threshold of grid cells is not exceeded than the geometric shape is stored in the grid index  251  as depicted by element  303 . However, if the geometric shape overlaps more than the threshold number of grid cells, an index for the geometric shape is stored in the storage pool, as depicted by element  304 . 
     In one embodiment, the threshold number of grid cells is thirty cells, it being understood that a smaller or larger number may be preferred in accordance with the specific application. Accordingly, geometries overlaying more than thirty cells will have a single index for the geometry stored in the pool  280  and will not have a plurality of indices stored in the index data structure  251 . 
     Instead of using a grid having a single level, it may be preferable to use a multi-level grid, which for example could have three levels of progressively increasing grid cell size. Referring to  FIG. 3B , which, is a flow diagram for such a system, a grid at level  1  (the finest level) first would be laid over a geometric shape as depicted by element  312 . A determination would then be made as to whether the grid at level  1  overlaps more than a defined limit number of grid cells, which for example could be four grid cells, as depicted by element  314 . If the shape does not overlap more than four cells, then level  1  is used for indexing of the geometric shape, as depicted by element  316 . On the other hand, if the shape does overlap more than four grid cells, the next coarsest grid level is used, and the same determination is made, as depicted by elements  318  and  320 . If the grid cell overlaps more than four grid cells then progressively coarser grids are used, and the finest grid level at which not more than four grid cells are overlapped is used for grid indexing, as depicted by element  322 . 
     If even at the coarsest grid level more than four grid cells are overlapped, then a determination is made if more than the threshold number of grid cells is overlapped, as depicted by element  324 . If fewer than the threshold number are overlapped, than the coarsest grid level is used for grid indexing, as shown by element  326 . However, if the threshold number is exceeded, then indices for the geometric shape are not placed in the index data structure, but rather one index for the entire geometric shape is placed in the storage pool, as depicted by element  328 . 
     As previously described, use of the pool is advantageous because it reduces the number of entries in the grid index. Computation of such index entries is expensive, and maintenance of the index is simplified by the reduction in size. Use of the present invention is effective to enhance index performance for the rest of the data in the index. 
     When the grid index is queried to retrieve selected geometric shapes, the storage pool must be queried as well so as to consider all shapes. A flow diagram that illustrates an embodiment of the query operation is shown in  FIG. 3C . This flow diagram is to be considered in connection with the grid, associated geometric shapes and query box  140  shown in  FIG. 2B . 
     Referring to  FIG. 2B , the query box  140  defines the area of interest in which it is desired to search for certain geometric shapes. For example, the query box may be drawn on a monitor screen by an operator performing the query operation, and may represent a geographical area having geographical features with different geometric shapes. 
     Referring to  FIG. 3C , first of the grid indices is evaluated, depicted by element  340 . Referring again to  FIG. 2B , the grid index evaluation step determines from the index information held in the index data structure  251  ( FIG. 2D ) whether the MBR of any geometric shape is present in the grid cells overlapped by the query box, that is, whether the MBR of any shape overlaps grid cells ( 4 , 5 ) or ( 5 , 5 ). Referring to the grid index shown in  FIG. 2D , a shape is determined to be present in cell ( 4 , 5 ) but not in cell ( 5 , 5 ). Therefore, cell ( 4 , 5 ) is retained as containing a candidate shape, while cell ( 5 , 5 ) is no longer considered in the evaluation. Because very large shapes are not indexed in the index data structure  251 , grid indexes for those shapes are not evaluated in operation  340 , thereby saving computational time and resources. 
     Next, in operation  344  possible shapes in both the index and pool are filtered based on the location of the MBR of the candidate shapes and the query box. It is at this step that all geometries from the pool are added to possible candidates from the index. 
     Referring again to  FIG. 2B , it is seen that the right, vertically oriented side of the MBR of shape “C” falls within the query box  140 . Hence, the MBR of shape “C” overlays the query box and accordingly shape “C” survives the filtering  344  and remains a candidate. The grid itself is not used in the filtering  344 , but rather there is a positional determination of whether there is an overlap between the MBR (which can be stored in the grid index) and the query box. The positional determination can be a computation of whether the maximum X coordinate of either of the rectangles falls between the minimum and maximum X coordinates of the other rectangle, and if so, whether the maximum Y coordinate of either rectangle falls between the minimum and maximum Y coordinates of the other rectangle. 
     The geometries in the pool are also filtered at element  344  based on whether there is an overlap between their MBR&#39;s and the query box. As can be seen by referring to  FIG. 2B , there would be an overlap of the MBR (not shown) for shape “D”  228  and the query box, so both shape “C” from the index and shape “D” from the pool survive the filtering, while shape “E”  230  from the pool does not. 
     Next, for the remaining candidate shapes that survive MBR filtering, operation  346  determines whether the exact geometric shape for each remaining candidate falls within the query box  140 . Pointers to the exact shape information are stored within the grid index or within the storage pool for large geometries. As can be seen by referring to  FIG. 2B , the rightmost point of shape “C” falls within the query box, so the determination for shape “C” is that the exact shape is within the query box. Similarly, the exact shape “D” falls within the query box, so the same determination is made for that shape. Suitable algorithms for making the exact shape computation are well known to those skilled in the art. In this manner geometric shapes that intersect a query area are returned. 
     According to the above procedure, all geometries from the pool are added to the set of possible candidates from the grid index evaluation. This ensures that no geometry will be missed during the query process. 
     Of course, a drawback is that a geometry from the separate pool might have been eliminated in the grid index evaluation if it were indexed in the grid index, but now it is added to the set of possible candidates due to the processing of the separate pool. However, only very few geometries should be in the separate pool. If there are many geometries, those would not be special cases but rather common cases and the grid index should be tuned for them. But if the grid index is tuned for them, these geometries would be in the grid index itself and not in the separate pool. Also, the last two operations in the query are: (a) filtering based on the MBR  344 , and (b) using the exact geometry to determine the result  346 . If a geometry would have been filtered out by the grid index evaluation but is now added by the separate pool, operation (a) will filter it out before operation (b) performs the more expensive calculation, so the impact is rather marginal. 
       FIG. 4  is a block diagram of a computer system  400 , suitable for employment of the methods described here. System  400  can be implemented on a general-purpose microcomputer, such as one of the members of the IBM Personal Computer family, or other conventional workstation or graphics computer devices, or mainframe computers. In its preferred embodiment, system  400  includes a user interface  417 , a user input device  407 , a display  415 , a printer  420 , a processor  455 , a read only memory (ROM)  450 , a data storage device  122 , such as a hard drive, a random access memory (RAM)  440 , and a storage media interface  435 , all of which are coupled to a bus  425  or other communication means for communicating information. Although system  400  is represented herein as a standalone system, it is not limited to such, but instead can be part of a networked system. For example, the computer system  400  may be connected locally or remotely to fixed or removable data storage devices  122  and data transmission devices  445 . Further the computer system  400 , such as the server computer system  102  or the client computer system  104  shown in  FIG. 1A , also could be connected to other computer systems via the data transmission devices  445 . 
     The RAM  440 , the data storage device  122  and the ROM  450 , are components of a memory unit  458  that stores data and instructions for controlling the operation of processor  455 , which may be configured as a single processor or as a plurality of processors. The processor  455  executes a program  442  recorded in one of the computer-readable storage media described above, to perform the methods of the present invention, as described herein. 
     While the program  442  is indicated as loaded into the RAM  440 , it may be configured on a storage media  430  for subsequent loading into the data storage device  122 , the ROM  450 , or the RAM  440  via an appropriate storage media interface  435 . Storage media  430  can be any conventional storage media such as a magnetic tape, an optical storage media, a compact disk, or a floppy disk. Alternatively, storage media  430  can be a random access memory  440 , or other type of electronic storage, located on a remote storage system. 
     Generally, the computer programs and operating systems are all tangibly embodied in a computer-readable device or media, such as the memory  458 , the data storage device  122 , or the data transmission devices  445 , thereby making an article of manufacture, such as a computer program product. As such, the terms “computer program product” as used herein are intended to encompass a computer program  442  accessible from any computer readable device or media. 
     Moreover, the computer programs  442  and operating systems are comprised of instructions which, when read and executed by the computer system  400 , cause the computer system  400  to perform the steps necessary to implement and use the methods and systems described here. Under control of the operating system, the computer programs  442  may be loaded from the memory  458 , the data storage device  122 , or the data transmission devices  445  into the memories  458  of the computer system  400  for use during actual operations. Those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope of the present invention. 
     The user interface  417  is an input device, such as a keyboard or speech recognition subsystem, for enabling a user to communicate information and command selections to the processor  455 . The user can observe information generated by the system  400  via the display  415  or the printer  420 . The user input device  407  is a device such as a mouse, track-ball, or joy-stick, which allows the user to manipulate a cursor on the display  415  for communicating additional information and command selections to the processor  455 . 
     While operating in accordance with the present invention, the system  400  determines which geometric shapes in the database are to be loaded into the grid index and which into the storage pool. It also operates to query both the grid index and storage pool in such manner that all geometric shapes are considered during the query operation. 
     The methods and systems described here are typically implemented using one or more computer programs  442 , each of which is executed under the control of an operating system and causes the system  400  to perform the desired functions as described herein. Thus, using the present specification, the invention may be implemented as a machine, process, method, system, or article of manufacture by using standard programming and engineering techniques to produce software, firmware, hardware or any combination thereof. 
     It should be understood that various alternatives and modifications can be devised by those skilled in the art. However, these should not be viewed as limitations upon the practice of these teachings, as those skilled in the art, when guided by the foregoing teachings, may derive other suitable characteristics of a similar or different nature. The present invention is intended to embrace all such alternatives, modifications and variances that fall within the scope of the appended claims. For example, although the embodiments are described here with reference to storage and evaluation of geometric shapes, the invention can apply to other types of data objects for which a varying number of indexes can be generated. For such other types of data objects, if a number of index entries generated for such a data object exceeds a certain threshold, the data object, or an identifier of that data object is recorded in a storage pool. If the number of index entries does not exceed the threshold than the data object, or its identifier, is recorded in an index data structure. 
     TRADEMARKS 
     IBM is a trademark or registered trademark of International Business Machines, Corporation in the United States and other countries. 
     DB2 is a trademark or registered trademark of International Business Machines, Corporation in the United States and other countries.