Spatial indexing in microsoft SQL server 2008

ABSTRACT

Microsoft SQL Server 2008 adds built-in support for 2-dimensional spatial data types for both planar and geodetic geometries to address the increasing demands for managing location-aware data. SQL Server 2008 also adds indexing capabilities that, together with the necessary plan selections done by the query optimizer, provide efficient processing of spatial queries. This paper will present an overview of the spatial indexing implementation in SQL Server 2008 and outline how the indexing is implemented and how the cost-based query optimizer chooses among the different plans.

REFERENCES

• 1: Walid G. Aref, Ihab F. Ilyas: SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees. J. Intell. Inf. Syst. 17(2-3): 215--240 (2001)
• 2: Srikanth R Avadhanam, Nigel R. Ellis, Campbell Bryce Fraser, Rodger N. Kline. System and method for using a compressed trie to estimate like predicates. United States Patent # 6,829,602, 2004.
• 3: N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger.The R*-tree: an efficient and robust access method for points and rectangles Proceedings of the 1990 ACM SIGMOD international conference on Management of data. pages 322--331, 1990
• 4: S. Berchtold, C. Bohm, D. A. Keim, and H.-P. Kriegel. A cost model for nearest neighbor search in high-dimensional data space. In PODS, pages 78--86, 1997.
• 5: Thomas Brinkhoff, Holger Horn, Hans-Peter Kriegel, Ralf Schneider, A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.357--376, June 23-25, 1993
• 6: Wm. Randolph Franklin. Adaptive Grids for geometric operations. In Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), pages 230--239, Ottawa, 1983
• 7: Thanaa M. Ghanem, Rahul Shah, Mohamed F. Mokbel, Walid G. Aref, Jeffrey Scott Vitter: Bulk Operations for Space-Partitioning Trees. ICDE 2004: 29--41
• 8: A. Guttman.R-Trees: A Dynamic Index Structure for Spatial Searching. Proc. ACM SIGMOD Int. Conf. on Management of Data. pages 47--57, 1984
• 9: Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562--573
• 10: Gísli R. Hjaltason, Hanan Samet. Ranking in Spatial Databases. Proceedings of the 4th International Symposium on Advances in Spatial Databases. pages 83--95, 1995
• 11: Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205--214
• 12: P. Krishnan, Jeffrey Scott Vitter, Balakrishna R. Iyer. Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD 1996: 282--293.
• 13: Microsoft Corp. Delivering Location Intelligence with Spatial Data. Whitepaper. http://www.microsoft.com/sql/techinfo/whitepapers/spatialdata.mspx, 2007.
• 14: Open Geospatial Consortium (OGC). OpenGIS® Simple Features Specification for SQL. http://www.opengeospatial.org/standards/sfs
• 15: Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343--352.
• 16: Shankar Pal, Istvan Cseri, Gideon Schaller, Oliver Seeliger, Leo Giakoumakis, Vasili Zolotov: Indexing XML Data Stored in a Relational Database. VLDB 2004: 1134--1145.
• 17: D. Papadias, Y. Theodoridis, T. Sellis, and M. Egenhofer. Topological relations in the world of minimum bounding rectangles: a study with R-trees. Proceedings of the ACM SIGMOD Conference, San Jose, California, 1995.
• 18: K. V. Ravi Kanth, D. Agrawal, Ambuj K. Singh. Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166--176
• 19: K. V. Ravi Kanth, Siva Ravada, Daniel Abugov. Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data SIGMOD Conference 2002: 546--557.
• 20: J. T. Robinson. The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. In Proceedings of ACM SIGMOD, pages 10--18, 1981.
• 21: Hanan Samet, Robert E. Webber: Storing a Collection of Polygons Using Quadtrees. ACM Trans. Graph. 4(3): 182--222 (1985).
• 22: Hanan Samet, C. A. Shatter, Randal C. Nelson, Y.-G. Huang, Kikuo Fujimura, A. Rosenteld: Recent developments in linear quadtree-based geographic information systems. Image Vision Comput. 5(3): 187--197 (1987).
• 23: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. Proceedings of 13th International Conference on Very Large Data Bases. page 507--518, 1987.
• 24: Michael Stonebraker, "Inclusion of New Types in Relational Data Base Systems," Proceedings of the Second International Conference on Data Engineering(ICDE), pages 262--269. 1986
• 25: Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161--171.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
spatial databases, spatial indexing, spatial query processing