Optimizing Geopoly Queries for Point-in-Polygon Speed

Understanding Geopoly Index Selection and Function Argument Order

Issue Overview

The core challenge revolves around efficiently determining which polygon in a geopoly table contains a given geographic point. Two functions are central to this task: geopoly_contains_point() and geopoly_within(). While geopoly_within() is documented to leverage R*Tree indexes for optimization, initial testing reveals it performs slower than geopoly_contains_point() despite the latter lacking explicit index support.

The problem manifests in two key observations:

1. Query Plan Mismatch: Both functions trigger a 4:fullscan index, forcing a full table scan instead of using the faster 3:rtree index.
2. Argument Order Sensitivity: Reversing arguments in geopoly_within() (e.g., geopoly_within(_shape, generated_polygon)) enables the 3:rtree index but inverts the spatial relationship, rendering results invalid.

The contradiction arises because geopoly_within() requires specific argument ordering to activate index optimizations. The function is designed to check if the first polygon is entirely within the second. However, when the second argument is a table column (e.g., _shape), the virtual table recognizes it as a candidate for index-driven filtering. This recognition fails if the column is the first argument or if additional operations (e.g., != 0) obscure the function call.

Diagnosing Index Utilization and Function Constraints

Why geopoly_within() Fails to Use the Index Initially

The geopoly extension optimizes queries only when specific conditions are met:

• The geopoly_within(P1, P2) function must have the table column (e.g., _shape) as the second argument (P2).
• The function must appear in the WHERE clause without being wrapped in expressions (e.g., != 0, NOT).

In the original query, geopoly_within(geopoly_regular(...), _shape) places the generated polygon (P1) first and the table column (P2) second. This order instructs the virtual table to check if the generated polygon is within _shape, which is the inverse of the desired logic. The optimizer cannot repurpose the index to answer "is the point within _shape" because the index is built to answer "which polygons contain P1" when P1 is a query parameter.

Why geopoly_contains_point() Is Faster Without Indexes

The geopoly_contains_point() function bypasses polygon generation and directly checks point-in-polygon relationships using computational geometry. While it requires a full scan, its runtime efficiency stems from:

• No Polygon Serialization Overhead: It avoids creating a temporary polygon via geopoly_regular(), which involves memory allocation and coordinate calculations.
• Simpler Computational Logic: The ray-casting algorithm for point-in-polygon checks is computationally lighter than polygon-in-polygon intersection tests.

However, the lack of index support means performance degrades linearly with table size, making it impractical for large datasets.

Resolving Index Misuse and Reclaiming Spatial Query Efficiency

Step 1: Correct geopoly_within() Argument Order for Index Activation

To leverage the R*Tree index, restructure the query to position the table column as the second argument while preserving logical correctness:

SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE geopoly_within(  
  geopoly_bbox_point(-64.75, -3.4, 0.0001), -- Custom helper function  
  _shape  
);  

Key Adjustments:

• geopoly_bbox_point(): Replace geopoly_regular() with a helper function that generates a minimal bounding rectangle (MBR) around the point. This ensures the generated polygon fully contains the point while being compatible with index-driven containment checks.
• Implicit Index Activation: By placing _shape as the second argument, the virtual table recognizes the query as a candidate for 3:rtree index scanning.

Helper Function Definition:

CREATE FUNCTION geopoly_bbox_point(lon REAL, lat REAL, radius REAL)  
RETURNS TEXT DETERMINISTIC  
BEGIN  
  RETURN geopoly_json(geopoly_regular(lon, lat, radius, 4));  
END;  

This creates a square (4-sided polygon) around the point, minimizing computational overhead while ensuring the MBR encompasses the point.

Step 2: Validate Query Plan and Index Usage

After restructuring the query, confirm the use of the 3:rtree index via EXPLAIN QUERY PLAN:

EXPLAIN QUERY PLAN  
SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE geopoly_within(geopoly_bbox_point(-64.75, -3.4, 0.0001), _shape);  

The output should indicate INDEX 3:rtree, confirming the index is active. If not, check for:

• Hidden Expression Wrapping: Ensure geopoly_within() is not nested within CASE, COALESCE, or arithmetic operations.
• Deterministic Function Guarantees: Custom helper functions (e.g., geopoly_bbox_point()) must be marked DETERMINISTIC to avoid optimizer skepticism.

Step 3: Optimize Polygon Generation for Index Efficiency

The radius parameter in geopoly_bbox_point() controls the MBR size. A smaller radius reduces false positives but risks excluding the point due to floating-point inaccuracies. Conduct empirical testing to balance precision:

-- Test varying radii to find the smallest value that avoids false negatives  
SELECT COUNT(*)  
FROM ecoregionsGeopoly  
WHERE geopoly_within(geopoly_bbox_point(-64.75, -3.4, 1e-5), _shape);  

A radius of 0.0001 degrees (≈11 meters) is generally sufficient for geographic coordinates.

Step 4: Benchmark and Compare Performance

After index activation, benchmark the revised query against geopoly_contains_point():

-- Revised geopoly_within() query  
.timer ON  
SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE geopoly_within(geopoly_bbox_point(-64.75, -3.4, 0.0001), _shape);  

-- Original geopoly_contains_point() query  
SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE geopoly_contains_point(_shape, -64.75, -3.4);  

Expect the geopoly_within() query to execute in milliseconds (using 3:rtree), while geopoly_contains_point() remains slower due to full scans.

Step 5: Address Edge Cases and Precision Tradeoffs

The MBR approach introduces a tradeoff:

• False Positives: The bounding rectangle may intersect multiple polygons, requiring a secondary precision check.
• Coordinate System Limitations: The geopoly extension assumes planar coordinates, which may misrepresent geodesic distances near poles or the antimeridian.

Mitigate these by adding a secondary filter:

SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE  
  geopoly_within(geopoly_bbox_point(-64.75, -3.4, 0.0001), _shape)  
  AND geopoly_contains_point(_shape, -64.75, -3.4);  

This combines the speed of index-driven geopoly_within() with the accuracy of geopoly_contains_point(), though at the cost of slightly increased runtime.

Step 6: Schema Optimization for Hybrid Queries

For frequently queried points, precompute their MBRs and store them in a dedicated column:

ALTER TABLE ecoregionsGeopoly ADD COLUMN mbr TEXT;  
UPDATE ecoregionsGeopoly SET mbr = geopoly_bbox(_shape); -- geopoly_bbox() returns the minimal bounding rectangle  

Create a covering index to accelerate combined queries:

CREATE INDEX idx_ecoregions_mbr ON ecoregionsGeopoly (mbr);  

Then rewrite queries to leverage both the MBR and exact checks:

SELECT ecoregions_id, biomes_id, realms_id  
FROM ecoregionsGeopoly  
WHERE  
  geopoly_overlap(mbr, geopoly_bbox_point(-64.75, -3.4, 0.0001))  
  AND geopoly_contains_point(_shape, -64.75, -3.4);  

This approach minimizes index scan overhead while ensuring accuracy.

Final Recommendations

1. Prefer geopoly_within() with Correct Argument Order: Always position the table column as the second argument to activate R*Tree indexes.
2. Use Minimal Bounding Rectangles: Replace point-to-polygon conversions with MBRs to reduce computational overhead.
3. Combine Index Scans with Precision Checks: Use geopoly_within() for fast filtering and geopoly_contains_point() for exact results.
4. Monitor Query Plans: Regularly validate EXPLAIN QUERY PLAN outputs to ensure index utilization.

By aligning function argument order with index requirements and optimizing polygon generation, point-in-polygon queries can achieve millisecond response times even on large datasets.