Database Management SystemsSpatial Indexes

Spatial Indexes: Indexing Multi-Dimensional Data

LevelAdvanced

Duration75 mins

TopicSpatial Indexes

1 / 5

Spatial Data: Understanding Multi-Dimensional Information

Beyond Rows and Columns: The Spatial Dimension

Open any mapping application on your phone, and within milliseconds, you see restaurants within a 5-mile radius, traffic conditions on nearby roads, and points of interest surrounding your current location. Behind this seamless experience lies a sophisticated indexing challenge that cannot be solved by traditional B+-trees or hash indexes.

The fundamental problem: How do you efficiently answer the question "What objects are near this location?" when dealing with billions of geographic points, complex polygons representing building footprints, intricate road networks, and overlapping spatial regions?

Traditional indexes excel at one-dimensional ordering—sorting numbers, comparing strings, or finding exact matches. But spatial data exists in multiple dimensions simultaneously. A restaurant isn't just at longitude -122.4194; it's at longitude -122.4194 AND latitude 37.7749. These two dimensions are inseparably linked, and queries must consider both at once.

What You Will Learn

By the end of this page, you will understand what spatial data is, the various types of spatial objects databases must handle, coordinate systems and their implications, and why traditional indexing approaches fundamentally fail for spatial queries. This foundation is essential before we explore R-trees and spatial query processing.

What Is Spatial Data?

Spatial data represents information about the physical location and shape of objects in space. Unlike traditional scalar data (a number, a string, a date), spatial data encapsulates position, extent, and often topology—how objects relate to each other in space.

At its core, spatial data answers questions about where things are and how they relate to other things based on location:

Where is the nearest hospital?
Which roads intersect Highway 101?
What buildings fall within this flood zone?
Does this delivery route cross any restricted areas?

The term geospatial specifically refers to data tied to Earth's surface, but spatial indexing techniques apply equally to any multi-dimensional space—from 2D screen coordinates in graphics applications to 3D molecular structures in computational biology, or even abstract high-dimensional feature spaces in machine learning.

Spatial vs. Traditional Data Characteristics
Characteristic	Traditional Data	Spatial Data
Dimensions	Single (1D ordering)	Multiple (2D, 3D, or higher)
Ordering	Total ordering possible	No natural total ordering
Query types	Point lookups, range scans	Proximity, containment, intersection
Size variability	Usually fixed or predictable	Highly variable (point vs. polygon)
Comparison	Simple (<, =, >)	Complex (overlaps, touches, within)
Index key	Single value	Bounding region or approximation

The Multi-Dimensional Challenge

Consider sorting geographic points: Should San Francisco (37.7749°N, 122.4194°W) come before or after Los Angeles (34.0522°N, 118.2437°W)? By latitude, SF is 'greater'. By longitude, LA is 'greater'. There's no single ordering that captures spatial proximity—this is why we need fundamentally different indexing approaches.

Spatial Data Types

Database systems that support spatial data implement a hierarchy of geometric types, standardized primarily by the Open Geospatial Consortium (OGC). Understanding these types is crucial because the complexity and storage requirements vary dramatically, affecting how indexes must handle them.

Core Spatial Data Types

•Point — The simplest spatial type: a single location in space defined by coordinates (x, y) or (longitude, latitude). Examples: GPS waypoints, store locations, sensor positions. Storage: typically 16-32 bytes depending on precision.
•LineString — An ordered sequence of points connected by straight line segments, forming a path. Examples: roads, rivers, flight paths, subway routes. The vertices are explicit; segments between them are implied.
•Polygon — A closed region bounded by one or more rings (LineStrings where start = end). The exterior ring defines the boundary; interior rings represent holes. Examples: building footprints, park boundaries, administrative districts.
•MultiPoint — A collection of Points treated as a single geometry. Examples: multiple entrances to a stadium, distributed sensor network stations.
•MultiLineString — A collection of LineStrings. Examples: a highway system with disconnected segments, a river delta with multiple branches.
•MultiPolygon — A collection of Polygons. Examples: an archipelago nation (multiple islands), a park with non-contiguous sections.
•GeometryCollection — A heterogeneous collection of any geometry types. Rarely used in practice but necessary for complete expressiveness.

spatial_data_examples.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-- Point: A coffee shop location
-- SRID 4326 = WGS84 (standard GPS coordinate system)
SELECT ST_GeomFromText('POINT(-122.4194 37.7749)', 4326);
 
-- LineString: A street segment
SELECT ST_GeomFromText(
    'LINESTRING(-122.4200 37.7700, -122.4180 37.7720, -122.4160 37.7750)', 
    4326
);
 
-- Polygon: A park boundary
SELECT ST_GeomFromText(
    'POLYGON((-122.4230 37.7690, -122.4230 37.7750, 
              -122.4170 37.7750, -122.4170 37.7690, 
              -122.4230 37.7690))', 
    4326
);
 
-- Polygon with hole: Building with interior courtyard
SELECT ST_GeomFromText(
    'POLYGON(
        (-122.4100 37.7800, -122.4100 37.7850, -122.4050 37.7850, -122.4050 37.7800, -122.4100 37.7800),
        (-122.4090 37.7810, -122.4090 37.7840, -122.4060 37.7840, -122.4060 37.7810, -122.4090 37.7810)
    )', 
    4326
);
 
-- MultiPolygon: Country with islands
SELECT ST_GeomFromText(
    'MULTIPOLYGON(
        ((-122.5 37.7, -122.5 37.8, -122.4 37.8, -122.4 37.7, -122.5 37.7)),
        ((-122.3 37.6, -122.3 37.65, -122.25 37.65, -122.25 37.6, -122.3 37.6))
    )', 
    4326
);

Storage Implications:

The variability in spatial object size creates indexing challenges:

Type	Typical Storage	Example
Point	16-32 bytes	Store location
LineString (10 vertices)	160-320 bytes	City block
LineString (1000 vertices)	16-32 KB	Detailed river course
Polygon (100 vertices)	1.6-3.2 KB	Building footprint
Polygon (10000 vertices)	160-320 KB	Detailed country boundary

Unlike B+-trees where all keys are similar size, spatial indexes must handle objects spanning five orders of magnitude in storage. This variability influences index node capacity and splitting strategies.

Coordinate Systems and Projections

Before diving into spatial indexing, we must understand how spatial data is represented numerically. This seemingly mundane topic has profound implications for index correctness and query accuracy.

The Fundamental Problem:

Earth is a three-dimensional oblate spheroid (slightly flattened at the poles). Maps and databases represent this 3D surface in 2D coordinates. This transformation introduces distortions that affect distance calculations, area measurements, and even the simple question of "What is between two points?"

Geographic Coordinates (Geodetic)

•Uses latitude/longitude (degrees)
•References Earth's curved surface
•WGS84 (SRID 4326) is GPS standard
•1 degree ≠ constant distance
•At equator: 1° ≈ 111 km
•At 60°N: 1° longitude ≈ 55 km
•Great circle distance for accuracy
•Ideal for: GPS data, global datasets

Projected Coordinates (Cartesian)

•Uses x/y (meters or feet)
•Represents flat 2D plane
•Many projections exist (UTM, State Plane)
•Units are consistent everywhere
•Euclidean distance works correctly
•Distortion varies by location
•Pythagorean theorem applies
•Ideal for: local analysis, engineering

Critical: Coordinate System Mismatch Errors

The most common spatial database bug: mixing coordinate systems. If your data is in WGS84 but you calculate Euclidean distance, a 1-degree difference could mean 111 km at the equator but only 55 km at 60° latitude. Indexes may work but return incorrect results. Always verify SRID consistency before querying.

Spatial Reference Identifier (SRID):

Every geometry in a spatial database carries an SRID—a numeric code identifying its coordinate system. The European Petroleum Survey Group (EPSG) maintains the definitive registry:

SRID	Name	Use Case
4326	WGS84	GPS coordinates, global web maps
3857	Web Mercator	Google Maps, OpenStreetMap tiles
32610	UTM Zone 10N	California, precision engineering
2163	US National Atlas	US-wide area calculations

Why This Matters for Indexing:

R-trees and spatial indexes typically work in Cartesian space—they measure distances using sqrt((x₂-x₁)² + (y₂-y₁)²). For geographic coordinates near the poles, this calculation is severely distorted. Some databases handle this transparently; others require explicit projection. Understanding your coordinate system prevents subtle but catastrophic query errors.

coordinate_system_operations.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
-- Check geometry's coordinate system
SELECT ST_SRID(geom), ST_AsText(geom) FROM locations LIMIT 1;
 
-- Transform from WGS84 to Web Mercator
SELECT ST_Transform(
    ST_GeomFromText('POINT(-122.4194 37.7749)', 4326),
    3857
);
-- Result: POINT(-13627665.27 4547675.35) in meters
 
-- Calculate distance in WGS84 (returns degrees - WRONG for distance)
SELECT ST_Distance(
    ST_GeomFromText('POINT(-122.4194 37.7749)', 4326),
    ST_GeomFromText('POINT(-118.2437 34.0522)', 4326)
);
-- Returns ~5.5 (degrees, meaningless as a distance)
 
-- Calculate geographic distance (returns meters - CORRECT)
SELECT ST_Distance(
    ST_GeographyFromText('POINT(-122.4194 37.7749)'),
    ST_GeographyFromText('POINT(-118.2437 34.0522)')
);
-- Returns ~559,044 meters (559 km) - actual great-circle distance
 
-- Best practice: transform to appropriate local projection for calculations
SELECT ST_Distance(
    ST_Transform(ST_GeomFromText('POINT(-122.4194 37.7749)', 4326), 32610),
    ST_Transform(ST_GeomFromText('POINT(-118.2437 34.0522)', 4326), 32610)
) / 1000.0 AS distance_km;

Why Traditional Indexes Fail for Spatial Data

Understanding why B+-trees and hash indexes fail for spatial queries illuminates why we need specialized structures like R-trees. This isn't merely academic—it explains real performance cliffs when developers attempt to hack spatial functionality onto non-spatial indexes.

B+-Tree Limitations for Spatial Data

•One-dimensional ordering — B+-trees store keys in sorted order along a single dimension. Geographic points have TWO co-equal dimensions. Sorting by longitude destroys latitude proximity; sorting by latitude destroys longitude proximity.
•No natural total ordering — Unlike numbers (2 < 5 < 10), points cannot be universally ordered. Is (3, 8) less than (5, 2)? By x-coordinate, yes. By y-coordinate, no. There's no single answer that preserves 2D proximity.
•Range queries span arbitrary rectangles — 'Find all points within this bounding box' requires filtering on TWO ranges simultaneously (min_x ≤ x ≤ max_x AND min_y ≤ y ≤ max_y). B+-trees can only efficiently filter ONE range.
•Proximity queries are discontinuous — 'Find nearest neighbors to this point' draws a circular region. Points at the edge of this circle may be far apart in any 1D ordering, requiring full scans.

The Composite Index Trap:

A common but flawed approach: create a composite B+-tree on (longitude, latitude). Let's trace why this fails:

Data points:
A: (-122.0, 37.0)  B: (-122.0, 38.0)  C: (-121.0, 37.5)
D: (-123.0, 37.5)  E: (-122.5, 37.5)  F: (-121.5, 37.5)

B+-tree order by (longitude, latitude):

D(-123.0, 37.5) → E(-122.5, 37.5) → A(-122.0, 37.0) → B(-122.0, 38.0) → F(-121.5, 37.5) → C(-121.0, 37.5)

Query: Find points within rectangle [(-122.5, 37.0) to (-121.5, 38.0)]

The tree can efficiently find longitude range -122.5 to -121.5: {E, A, B, F}

But latitude filtering (37.0 to 38.0) must scan ALL those entries. Point E at latitude 37.5 is between A(37.0) and B(38.0) in the index order, but the tree cannot skip directly to qualifying latitudes.

Result: For 1 million points with 10% matching longitude, we read 100,000 entries and filter down to perhaps 1,000 matching both dimensions—a 100x overhead compared to optimal spatial indexing.

The Curse of Dimensionality

As dimensions increase, the problem worsens exponentially. In 2D, composite indexes give √n overhead. In 3D, n^(2/3) overhead. In high dimensions (10+), even specialized spatial indexes degrade to near-linear scans. This fundamental limit is known as the 'curse of dimensionality' and profoundly impacts machine learning, similarity search, and scientific databases.

Hash Index Limitations for Spatial Data

•Exact match only — Hash indexes find points exactly at (-122.4194, 37.7749). They cannot find points near a location without scanning every bucket.
•No range support — Hash functions deliberately destroy ordering to distribute values uniformly. You cannot ask 'What's the next closest bucket?' because there's no spatial relationship between bucket values.
•No proximity semantics — Even if two points are 1 meter apart, their hash values may be completely unrelated, placing them in distant buckets.
•Geometric impossibility — Nearest-neighbor queries require knowing distance to check, but hash lookup requires knowing the exact target value. Chicken-and-egg problem.

Space-Filling Curves: A Bridge Approach

Before specialized spatial indexes like R-trees were widely available, researchers developed clever techniques to encode multi-dimensional coordinates into one-dimensional values that preserve some spatial locality. These space-filling curves map 2D (or higher) space to 1D in a way that keeps nearby points relatively close in the 1D sequence.

Key Insight: If we can transform (x, y) coordinates into a single value Z such that nearby points usually have similar Z values, we can use regular B+-trees for approximate spatial queries.

Two space-filling curves dominate practice:

Z-Order (Morton Curve)

Interleaves the bits of x and y coordinates:

x = 5 (binary: 101)
y = 3 (binary: 011)

Interleave: 01 10 11 = 011011 = 27

The resulting Z-value clusters nearby 2D points into nearby 1D values. A B+-tree range scan on Z-values approximates a spatial window query.

Advantages:

Simple bit manipulation
Fast encoding/decoding
Reasonable locality preservation

Disadvantages:

'Jump' discontinuities at quadrant boundaries
May require multiple range scans for one spatial query

Hilbert Curve

A more complex recursive pattern that visits every cell in a space while minimizing jumps between visits:

Hilbert value depends on recursive
position within fractal pattern.
More complex calculation than Z-order.

Advantages:

Better locality than Z-order
Fewer discontinuities
More compact query ranges

Disadvantages:

More expensive to compute
Complex encoding/decoding logic
Still imperfect—cannot fully linearize 2D

Used by: S2 Geometry (Google), H3 (Uber), many GIS systems

Space-Filling Curves in Practice

Google's S2 library (used in Google Maps) projects Earth onto a cube and applies Hilbert curves to each face. This enables remarkably efficient spatial queries using standard B+-tree indexes on 64-bit cell IDs. Uber's H3 uses hexagonal cells with similar principles. These approaches demonstrate that the 'linearization' strategy, while not theoretically optimal, works exceptionally well for geographic data at planetary scale.

Limitations of Linearization:

While space-filling curves are practical and widely deployed, they are fundamentally approximations:

Imperfect locality — No 1D curve can perfectly preserve 2D distance. Some nearby 2D points will be far apart on the curve.
Multiple ranges for boxes — A simple rectangular query may require scanning 2-8 disjoint 1D ranges, depending on how the query box aligns with curve structure.
Variable precision — Different levels of curve refinement trade off storage against precision. Too coarse loses locality; too fine wastes space.
Complex objects — Points linearize easily. Polygons spanning many cells require storing multiple cell IDs or bounding-box approximations.

These limitations motivate true multi-dimensional indexes like R-trees, which directly partition space rather than transforming it to 1D.

Spatial Query Types

Understanding the queries that spatial indexes must support is essential before studying index structures. These query types reveal why we need indexes that understand geometric relationships, not just value ordering.

Common Spatial Query Operations
Query Type	Description	Example	Index Requirement
Point-in-Region	Test if a point lies inside a polygon	Is the user inside the delivery zone?	Containment testing, polygon intersection
Range/Window	Find all objects within a bounding box	Show all cafes on the visible map	Rectangle intersection testing
Nearest Neighbor (NN)	Find the k closest objects to a point	Find 5 nearest gas stations	Priority-queue traversal by distance
Radius/Buffer	Find all objects within distance d of a point	Alert users within 10km of emergency	Circular region intersection
Intersection	Find objects that overlap a given geometry	Which parcels does this pipeline cross?	Complex geometry overlap detection
Spatial Join	Match objects from two tables by spatial relationship	Link customers to their congressional district	Bulk intersection testing

spatial_query_examples.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-- Range/Window Query: Find all restaurants in visible map area
SELECT name, ST_AsText(location)
FROM restaurants
WHERE ST_Intersects(
    location, 
    ST_MakeEnvelope(-122.45, 37.75, -122.40, 37.80, 4326)
);
 
-- Nearest Neighbor: Find 5 closest hospitals to current location
SELECT name, ST_Distance(location::geography, 
       ST_GeographyFromText('POINT(-122.4194 37.7749)')) AS distance_m
FROM hospitals
ORDER BY location <-> ST_GeomFromText('POINT(-122.4194 37.7749)', 4326)
LIMIT 5;
 
-- Radius Query: Find all users within 10km of emergency broadcast point
SELECT user_id, name
FROM users
WHERE ST_DWithin(
    location::geography,
    ST_GeographyFromText('POINT(-122.4194 37.7749)'),
    10000  -- 10km in meters
);
 
-- Point-in-Polygon: Check if delivery address is in service zone
SELECT EXISTS(
    SELECT 1 FROM service_zones 
    WHERE ST_Contains(
        zone_boundary, 
        ST_GeomFromText('POINT(-122.420 37.780)', 4326)
    )
) AS is_serviceable;
 
-- Spatial Join: Link buildings to their census tract
SELECT b.address, c.tract_id, c.population
FROM buildings b
JOIN census_tracts c ON ST_Contains(c.boundary, b.centroid);
 
-- Intersection: Find roads crossing the proposed pipeline route
SELECT r.road_name, ST_AsText(ST_Intersection(r.geometry, p.route))
FROM roads r, pipelines p
WHERE ST_Intersects(r.geometry, p.route)
  AND p.name = 'North Valley Pipeline';

The <-> Operator

In PostgreSQL/PostGIS, the <-> operator is the 'distance operator' designed for index-accelerated nearest-neighbor queries. It's not just syntactic sugar—it enables the query planner to use the spatial index's internal distance-priority traversal instead of computing all distances and sorting. Always use ORDER BY geom <-> point LIMIT k for nearest-neighbor queries.

Spatial Relationships: The DE-9IM Model

Spatial queries rely on a rich vocabulary of geometric relationships. The Dimensionally Extended 9-Intersection Model (DE-9IM) provides a complete mathematical framework for describing how two geometries relate in space.

The Core Concept:

Every geometry has three parts:

Interior (I) — The area inside the boundary
Boundary (B) — The edge of the geometry
Exterior (E) — Everything outside the geometry

The relationship between two geometries A and B is characterized by a 3×3 matrix showing whether each combination of these parts intersects:

de9im_matrix.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
            Interior(B)  Boundary(B)  Exterior(B)
           ┌────────────┬────────────┬────────────┐
Interior(A)│   I ∩ I    │   I ∩ B    │   I ∩ E    │
           ├────────────┼────────────┼────────────┤
Boundary(A)│   B ∩ I    │   B ∩ B    │   B ∩ E    │
           ├────────────┼────────────┼────────────┤
Exterior(A)│   E ∩ I    │   E ∩ B    │   E ∩ E    │
           └────────────┴────────────┴────────────┘
 
Each cell contains:
- 'T' = intersection exists (True)
- 'F' = no intersection (False)
- '0', '1', '2' = dimension of intersection (point=0, line=1, area=2)
- '*' = don't care (any value acceptable)

This matrix completely characterizes spatial relationships. Named predicates are shortcuts for common DE-9IM patterns:

Common Spatial Predicates and Their DE-9IM Patterns
Predicate	DE-9IM Pattern	Meaning
Equals	TF**FFF	Geometries are topologically identical
Disjoint	FFFF***	No intersection whatsoever
Intersects	NOT Disjoint	At least one point in common
Touches	FT***** or FT* or FT*	Share boundary but not interior
Crosses	TTT (for lines)	Pass through each other
Within	TFF	A is completely inside B
Contains	T****FF	B is completely inside A (inverse of Within)
Overlaps	TTT (for areas)	Share some but not all interior area

Why This Matters for Indexes

Spatial indexes cannot directly compute these complex relationships—that would require full geometry comparison for every candidate. Instead, indexes use bounding box approximations for filtering, then exact predicates verify the final relationship. The query 'Find all polygons that TOUCH this polygon' first uses the index to find polygons whose bounding boxes intersect, then tests the actual TOUCH predicate on the reduced candidate set.

Summary: The Need for Spatial Indexing

We've established the foundation for understanding spatial indexing. Let's consolidate the key insights:

Key Takeaways

•Spatial data is fundamentally multi-dimensional — Points, lines, and polygons exist in 2D or 3D space where both coordinates matter equally and simultaneously.
•No natural total ordering exists — Unlike numbers, spatial objects cannot be sorted in a single sequence that preserves proximity in all directions.
•Traditional indexes fail for spatial queries — B+-trees can only efficiently filter one dimension; hash indexes provide no proximity semantics at all.
•Coordinate systems matter — SRID mismatches cause subtle but severe query errors. Always verify coordinate system consistency.
•Space-filling curves offer a bridge — Z-order and Hilbert curves provide practical linearization that works surprisingly well for many applications.
•Spatial queries have unique semantics — Range, nearest-neighbor, intersection, and containment queries require specialized index support.
•DE-9IM provides precise relationship vocabulary — The standard model describes all possible spatial relationships, which indexes must efficiently filter.

What's Next:

With this foundation, we're ready to explore the dominant solution to spatial indexing: the R-tree. The next page introduces the R-tree concept—how it partitions space using overlapping bounding rectangles, why this design enables efficient multi-dimensional search, and how it elegantly solves the problems we've identified in this page.

Page Complete

You now understand what spatial data is, why traditional indexes fail for spatial queries, and the unique challenges of multi-dimensional indexing. This foundation prepares you to appreciate why R-trees use the specific design decisions they do. Next, we explore the elegant R-tree structure that powers location-based services worldwide.

1 / 5

Loading learning content...

Database Management SystemsSpatial Indexes

Spatial Indexes: Indexing Multi-Dimensional Data

LevelAdvanced

Duration75 mins

TopicSpatial Indexes

1 / 5

Spatial Data: Understanding Multi-Dimensional Information

Beyond Rows and Columns: The Spatial Dimension

What You Will Learn

What Is Spatial Data?

At its core, spatial data answers questions about where things are and how they relate to other things based on location:

Where is the nearest hospital?
Which roads intersect Highway 101?
What buildings fall within this flood zone?
Does this delivery route cross any restricted areas?

Spatial vs. Traditional Data Characteristics
Characteristic	Traditional Data	Spatial Data
Dimensions	Single (1D ordering)	Multiple (2D, 3D, or higher)
Ordering	Total ordering possible	No natural total ordering
Query types	Point lookups, range scans	Proximity, containment, intersection
Size variability	Usually fixed or predictable	Highly variable (point vs. polygon)
Comparison	Simple (<, =, >)	Complex (overlaps, touches, within)
Index key	Single value	Bounding region or approximation

The Multi-Dimensional Challenge

Spatial Data Types

Core Spatial Data Types

•Point — The simplest spatial type: a single location in space defined by coordinates (x, y) or (longitude, latitude). Examples: GPS waypoints, store locations, sensor positions. Storage: typically 16-32 bytes depending on precision.
•LineString — An ordered sequence of points connected by straight line segments, forming a path. Examples: roads, rivers, flight paths, subway routes. The vertices are explicit; segments between them are implied.
•Polygon — A closed region bounded by one or more rings (LineStrings where start = end). The exterior ring defines the boundary; interior rings represent holes. Examples: building footprints, park boundaries, administrative districts.
•MultiPoint — A collection of Points treated as a single geometry. Examples: multiple entrances to a stadium, distributed sensor network stations.
•MultiLineString — A collection of LineStrings. Examples: a highway system with disconnected segments, a river delta with multiple branches.
•MultiPolygon — A collection of Polygons. Examples: an archipelago nation (multiple islands), a park with non-contiguous sections.
•GeometryCollection — A heterogeneous collection of any geometry types. Rarely used in practice but necessary for complete expressiveness.

spatial_data_examples.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-- Point: A coffee shop location
-- SRID 4326 = WGS84 (standard GPS coordinate system)
SELECT ST_GeomFromText('POINT(-122.4194 37.7749)', 4326);
 
-- LineString: A street segment
SELECT ST_GeomFromText(
    'LINESTRING(-122.4200 37.7700, -122.4180 37.7720, -122.4160 37.7750)', 
    4326
);
 
-- Polygon: A park boundary
SELECT ST_GeomFromText(
    'POLYGON((-122.4230 37.7690, -122.4230 37.7750, 
              -122.4170 37.7750, -122.4170 37.7690, 
              -122.4230 37.7690))', 
    4326
);
 
-- Polygon with hole: Building with interior courtyard
SELECT ST_GeomFromText(
    'POLYGON(
        (-122.4100 37.7800, -122.4100 37.7850, -122.4050 37.7850, -122.4050 37.7800, -122.4100 37.7800),
        (-122.4090 37.7810, -122.4090 37.7840, -122.4060 37.7840, -122.4060 37.7810, -122.4090 37.7810)
    )', 
    4326
);
 
-- MultiPolygon: Country with islands
SELECT ST_GeomFromText(
    'MULTIPOLYGON(
        ((-122.5 37.7, -122.5 37.8, -122.4 37.8, -122.4 37.7, -122.5 37.7)),
        ((-122.3 37.6, -122.3 37.65, -122.25 37.65, -122.25 37.6, -122.3 37.6))
    )', 
    4326
);

Storage Implications:

The variability in spatial object size creates indexing challenges:

Type	Typical Storage	Example
Point	16-32 bytes	Store location
LineString (10 vertices)	160-320 bytes	City block
LineString (1000 vertices)	16-32 KB	Detailed river course
Polygon (100 vertices)	1.6-3.2 KB	Building footprint
Polygon (10000 vertices)	160-320 KB	Detailed country boundary

Coordinate Systems and Projections

The Fundamental Problem:

Geographic Coordinates (Geodetic)

•Uses latitude/longitude (degrees)
•References Earth's curved surface
•WGS84 (SRID 4326) is GPS standard
•1 degree ≠ constant distance
•At equator: 1° ≈ 111 km
•At 60°N: 1° longitude ≈ 55 km
•Great circle distance for accuracy
•Ideal for: GPS data, global datasets

Projected Coordinates (Cartesian)

•Uses x/y (meters or feet)
•Represents flat 2D plane
•Many projections exist (UTM, State Plane)
•Units are consistent everywhere
•Euclidean distance works correctly
•Distortion varies by location
•Pythagorean theorem applies
•Ideal for: local analysis, engineering

Critical: Coordinate System Mismatch Errors

Spatial Reference Identifier (SRID):

Every geometry in a spatial database carries an SRID—a numeric code identifying its coordinate system. The European Petroleum Survey Group (EPSG) maintains the definitive registry:

SRID	Name	Use Case
4326	WGS84	GPS coordinates, global web maps
3857	Web Mercator	Google Maps, OpenStreetMap tiles
32610	UTM Zone 10N	California, precision engineering
2163	US National Atlas	US-wide area calculations

Why This Matters for Indexing:

coordinate_system_operations.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
-- Check geometry's coordinate system
SELECT ST_SRID(geom), ST_AsText(geom) FROM locations LIMIT 1;
 
-- Transform from WGS84 to Web Mercator
SELECT ST_Transform(
    ST_GeomFromText('POINT(-122.4194 37.7749)', 4326),
    3857
);
-- Result: POINT(-13627665.27 4547675.35) in meters
 
-- Calculate distance in WGS84 (returns degrees - WRONG for distance)
SELECT ST_Distance(
    ST_GeomFromText('POINT(-122.4194 37.7749)', 4326),
    ST_GeomFromText('POINT(-118.2437 34.0522)', 4326)
);
-- Returns ~5.5 (degrees, meaningless as a distance)
 
-- Calculate geographic distance (returns meters - CORRECT)
SELECT ST_Distance(
    ST_GeographyFromText('POINT(-122.4194 37.7749)'),
    ST_GeographyFromText('POINT(-118.2437 34.0522)')
);
-- Returns ~559,044 meters (559 km) - actual great-circle distance
 
-- Best practice: transform to appropriate local projection for calculations
SELECT ST_Distance(
    ST_Transform(ST_GeomFromText('POINT(-122.4194 37.7749)', 4326), 32610),
    ST_Transform(ST_GeomFromText('POINT(-118.2437 34.0522)', 4326), 32610)
) / 1000.0 AS distance_km;

Why Traditional Indexes Fail for Spatial Data

B+-Tree Limitations for Spatial Data

•One-dimensional ordering — B+-trees store keys in sorted order along a single dimension. Geographic points have TWO co-equal dimensions. Sorting by longitude destroys latitude proximity; sorting by latitude destroys longitude proximity.
•No natural total ordering — Unlike numbers (2 < 5 < 10), points cannot be universally ordered. Is (3, 8) less than (5, 2)? By x-coordinate, yes. By y-coordinate, no. There's no single answer that preserves 2D proximity.
•Range queries span arbitrary rectangles — 'Find all points within this bounding box' requires filtering on TWO ranges simultaneously (min_x ≤ x ≤ max_x AND min_y ≤ y ≤ max_y). B+-trees can only efficiently filter ONE range.
•Proximity queries are discontinuous — 'Find nearest neighbors to this point' draws a circular region. Points at the edge of this circle may be far apart in any 1D ordering, requiring full scans.

The Composite Index Trap:

A common but flawed approach: create a composite B+-tree on (longitude, latitude). Let's trace why this fails:

Data points:
A: (-122.0, 37.0)  B: (-122.0, 38.0)  C: (-121.0, 37.5)
D: (-123.0, 37.5)  E: (-122.5, 37.5)  F: (-121.5, 37.5)

B+-tree order by (longitude, latitude):

D(-123.0, 37.5) → E(-122.5, 37.5) → A(-122.0, 37.0) → B(-122.0, 38.0) → F(-121.5, 37.5) → C(-121.0, 37.5)

Query: Find points within rectangle [(-122.5, 37.0) to (-121.5, 38.0)]

The tree can efficiently find longitude range -122.5 to -121.5: {E, A, B, F}

The Curse of Dimensionality

Hash Index Limitations for Spatial Data

•Exact match only — Hash indexes find points exactly at (-122.4194, 37.7749). They cannot find points near a location without scanning every bucket.
•No range support — Hash functions deliberately destroy ordering to distribute values uniformly. You cannot ask 'What's the next closest bucket?' because there's no spatial relationship between bucket values.
•No proximity semantics — Even if two points are 1 meter apart, their hash values may be completely unrelated, placing them in distant buckets.
•Geometric impossibility — Nearest-neighbor queries require knowing distance to check, but hash lookup requires knowing the exact target value. Chicken-and-egg problem.

Space-Filling Curves: A Bridge Approach

Key Insight: If we can transform (x, y) coordinates into a single value Z such that nearby points usually have similar Z values, we can use regular B+-trees for approximate spatial queries.

Two space-filling curves dominate practice:

Z-Order (Morton Curve)

Interleaves the bits of x and y coordinates:

x = 5 (binary: 101)
y = 3 (binary: 011)

Interleave: 01 10 11 = 011011 = 27

The resulting Z-value clusters nearby 2D points into nearby 1D values. A B+-tree range scan on Z-values approximates a spatial window query.

Advantages:

Simple bit manipulation
Fast encoding/decoding
Reasonable locality preservation

Disadvantages:

'Jump' discontinuities at quadrant boundaries
May require multiple range scans for one spatial query

Hilbert Curve

A more complex recursive pattern that visits every cell in a space while minimizing jumps between visits:

Hilbert value depends on recursive
position within fractal pattern.
More complex calculation than Z-order.

Advantages:

Better locality than Z-order
Fewer discontinuities
More compact query ranges

Disadvantages:

More expensive to compute
Complex encoding/decoding logic
Still imperfect—cannot fully linearize 2D

Used by: S2 Geometry (Google), H3 (Uber), many GIS systems

Space-Filling Curves in Practice

Limitations of Linearization:

While space-filling curves are practical and widely deployed, they are fundamentally approximations:

Imperfect locality — No 1D curve can perfectly preserve 2D distance. Some nearby 2D points will be far apart on the curve.
Multiple ranges for boxes — A simple rectangular query may require scanning 2-8 disjoint 1D ranges, depending on how the query box aligns with curve structure.
Variable precision — Different levels of curve refinement trade off storage against precision. Too coarse loses locality; too fine wastes space.
Complex objects — Points linearize easily. Polygons spanning many cells require storing multiple cell IDs or bounding-box approximations.

These limitations motivate true multi-dimensional indexes like R-trees, which directly partition space rather than transforming it to 1D.

Spatial Query Types

Common Spatial Query Operations
Query Type	Description	Example	Index Requirement
Point-in-Region	Test if a point lies inside a polygon	Is the user inside the delivery zone?	Containment testing, polygon intersection
Range/Window	Find all objects within a bounding box	Show all cafes on the visible map	Rectangle intersection testing
Nearest Neighbor (NN)	Find the k closest objects to a point	Find 5 nearest gas stations	Priority-queue traversal by distance
Radius/Buffer	Find all objects within distance d of a point	Alert users within 10km of emergency	Circular region intersection
Intersection	Find objects that overlap a given geometry	Which parcels does this pipeline cross?	Complex geometry overlap detection
Spatial Join	Match objects from two tables by spatial relationship	Link customers to their congressional district	Bulk intersection testing

spatial_query_examples.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-- Range/Window Query: Find all restaurants in visible map area
SELECT name, ST_AsText(location)
FROM restaurants
WHERE ST_Intersects(
    location, 
    ST_MakeEnvelope(-122.45, 37.75, -122.40, 37.80, 4326)
);
 
-- Nearest Neighbor: Find 5 closest hospitals to current location
SELECT name, ST_Distance(location::geography, 
       ST_GeographyFromText('POINT(-122.4194 37.7749)')) AS distance_m
FROM hospitals
ORDER BY location <-> ST_GeomFromText('POINT(-122.4194 37.7749)', 4326)
LIMIT 5;
 
-- Radius Query: Find all users within 10km of emergency broadcast point
SELECT user_id, name
FROM users
WHERE ST_DWithin(
    location::geography,
    ST_GeographyFromText('POINT(-122.4194 37.7749)'),
    10000  -- 10km in meters
);
 
-- Point-in-Polygon: Check if delivery address is in service zone
SELECT EXISTS(
    SELECT 1 FROM service_zones 
    WHERE ST_Contains(
        zone_boundary, 
        ST_GeomFromText('POINT(-122.420 37.780)', 4326)
    )
) AS is_serviceable;
 
-- Spatial Join: Link buildings to their census tract
SELECT b.address, c.tract_id, c.population
FROM buildings b
JOIN census_tracts c ON ST_Contains(c.boundary, b.centroid);
 
-- Intersection: Find roads crossing the proposed pipeline route
SELECT r.road_name, ST_AsText(ST_Intersection(r.geometry, p.route))
FROM roads r, pipelines p
WHERE ST_Intersects(r.geometry, p.route)
  AND p.name = 'North Valley Pipeline';

The <-> Operator

Spatial Relationships: The DE-9IM Model

The Core Concept:

Every geometry has three parts:

Interior (I) — The area inside the boundary
Boundary (B) — The edge of the geometry
Exterior (E) — Everything outside the geometry

The relationship between two geometries A and B is characterized by a 3×3 matrix showing whether each combination of these parts intersects:

de9im_matrix.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
            Interior(B)  Boundary(B)  Exterior(B)
           ┌────────────┬────────────┬────────────┐
Interior(A)│   I ∩ I    │   I ∩ B    │   I ∩ E    │
           ├────────────┼────────────┼────────────┤
Boundary(A)│   B ∩ I    │   B ∩ B    │   B ∩ E    │
           ├────────────┼────────────┼────────────┤
Exterior(A)│   E ∩ I    │   E ∩ B    │   E ∩ E    │
           └────────────┴────────────┴────────────┘
 
Each cell contains:
- 'T' = intersection exists (True)
- 'F' = no intersection (False)
- '0', '1', '2' = dimension of intersection (point=0, line=1, area=2)
- '*' = don't care (any value acceptable)

This matrix completely characterizes spatial relationships. Named predicates are shortcuts for common DE-9IM patterns:

Common Spatial Predicates and Their DE-9IM Patterns
Predicate	DE-9IM Pattern	Meaning
Equals	TF**FFF	Geometries are topologically identical
Disjoint	FFFF***	No intersection whatsoever
Intersects	NOT Disjoint	At least one point in common
Touches	FT***** or FT* or FT*	Share boundary but not interior
Crosses	TTT (for lines)	Pass through each other
Within	TFF	A is completely inside B
Contains	T****FF	B is completely inside A (inverse of Within)
Overlaps	TTT (for areas)	Share some but not all interior area

Why This Matters for Indexes

Summary: The Need for Spatial Indexing

We've established the foundation for understanding spatial indexing. Let's consolidate the key insights:

Key Takeaways

•Spatial data is fundamentally multi-dimensional — Points, lines, and polygons exist in 2D or 3D space where both coordinates matter equally and simultaneously.
•No natural total ordering exists — Unlike numbers, spatial objects cannot be sorted in a single sequence that preserves proximity in all directions.
•Traditional indexes fail for spatial queries — B+-trees can only efficiently filter one dimension; hash indexes provide no proximity semantics at all.
•Coordinate systems matter — SRID mismatches cause subtle but severe query errors. Always verify coordinate system consistency.
•Space-filling curves offer a bridge — Z-order and Hilbert curves provide practical linearization that works surprisingly well for many applications.
•Spatial queries have unique semantics — Range, nearest-neighbor, intersection, and containment queries require specialized index support.
•DE-9IM provides precise relationship vocabulary — The standard model describes all possible spatial relationships, which indexes must efficiently filter.

What's Next:

Page Complete

1 / 5