Explore geospatial query optimizations via H3 pre-computation

[rdhyee]

Goal

Deliver a fast, pleasant experience for developers and users querying iSamples geospatial data over the web. Current approach (DuckDB-WASM + remote parquet via HTTP range requests) is already good, but geospatial queries have room for optimization.

User experience we're targeting:

• Sub-second map rendering at any zoom level
• Responsive bounding box filters
• Smooth zoom-dependent clustering
• Minimal data transfer for spatial queries

---

The Problem

Geospatial queries on remote parquet are expensive:

Query Type	Current Behavior
Bounding box filter	Scans all rows, evaluates lat/lon conditions
"Near this point"	Distance calculation on every row
Zoom-level clustering	Full aggregation, no pre-computation
Faceted geo query	Combines the above costs

With 6.7M+ samples (20M rows in wide format), this adds up.

---

Optimization Strategies

1. H3 Pre-computation (Recommended Starting Point)

Add H3 hexagonal grid cell IDs at multiple resolutions:

SELECT *, 
       h3_latlng_to_cell(latitude, longitude, 4) as h3_res4,  -- Continental
       h3_latlng_to_cell(latitude, longitude, 6) as h3_res6,  -- Regional  
       h3_latlng_to_cell(latitude, longitude, 8) as h3_res8   -- Local
FROM wide_parquet
WHERE latitude IS NOT NULL

Benefits:

• Filter by cell ID = simple integer match (fast)
• Hierarchical: zoom-appropriate aggregation via GROUP BY h3_res6
• DuckDB has native H3 extension
• Minimal infrastructure change (same single-file approach)

2. Partitioned Parquet by H3

Split into Hive-style partitions:

data/h3_res4=841f9ffffffffff/part-0.parquet
data/h3_res4=841fbffffffffff/part-0.parquet

Benefits: Range requests skip irrelevant partitions entirely
Trade-off: More complex file management, needs manifest

3. Pre-aggregated Tiles

Create summary parquets at each zoom level:

zoom_4_summaries.parquet   # ~1K rows
zoom_8_summaries.parquet   # ~100K rows  
full_data.parquet          # 20M rows

Benefits: Appropriate data volume per zoom
Trade-off: Storage overhead, staleness concerns

4. GeoParquet Bounding Box Metadata

Ensure row group bounding boxes in parquet footer for predicate pushdown.

5. Edge Compute (Future)

Cloudflare Workers + DuckDB for server-side filtering closer to users.

---

Interaction with PQG Schema

Key principle: Core spec stays clean, enhancements are optional

Parquet is additive-friendly. We can add columns without breaking existing queries:

Column Type	Examples	Required?
Core PQG	row_id, otype, s, p, o, n, label, pid, latitude, longitude, p__*	Yes
Enhancement	h3_res4, h3_res6, h3_res8, geometry	No

Conventions to consider:

• Prefix enhancement columns? (_idx_h3_res4, _geo_*)
• Document in PQG spec (see Define formal PQG Parquet Schema specification #16)
• Possibly publish multiple variants:
  • isamples_wide.parquet (core only, smaller)
  • isamples_wide_geo.parquet (with H3, geometry)

---

Exploration Strategy

Phase 1: Local Python Baseline

• Benchmark current query speeds (bbox, point-radius, aggregation)
• Add H3 columns to local parquet
• Measure improvement

Phase 2: File Size Impact

• Measure size increase per H3 resolution
• Find sweet spot (e.g., res4 + res7 only?)
• Test compression ratios

Phase 3: Remote (R2) Performance

• Upload test files to R2
• Measure HTTP range request behavior
• Compare bytes transferred: H3 filter vs lat/lon filter
• Test different row group sizes

Phase 4: Browser (DuckDB-WASM) Validation

• Create test harness in Quarto
• Confirm optimizations work in browser
• Measure memory usage

Phase 5: Document & Decide

• Benchmark report with numbers
• Recommendation on which resolutions
• Update PQG spec with enhancement columns
• Push optimized parquet to R2 if results are good

---

Benchmark Matrix (To Fill In)

Query Type	Local	Remote Python	Remote WASM	Notes
Bbox (baseline)	? ms	? ms / ? MB	? ms / ? MB
Bbox (H3)	? ms	? ms / ? MB	? ms / ? MB
Aggregation (baseline)	? ms	? ms / ? MB	? ms / ? MB
Aggregation (H3 GROUP BY)	? ms	? ms / ? MB	? ms / ? MB
Point radius 50km	? ms	? ms / ? MB	? ms / ? MB

---

Success Criteria

• Bbox queries 5x+ faster with H3
• Aggregation queries support zoom-appropriate clustering
• File size increase < 20% for meaningful improvement
• Works in DuckDB-WASM (browser) without special handling
• Enhancement columns documented in PQG spec

---

Related

• Define formal PQG Parquet Schema specification #16 - PQG Parquet Schema specification (where to document enhancement columns)
• H3 documentation
• DuckDB H3 extension
• GeoParquet spec

cc @smrgeoinfo @datadavev

[rdhyee]

Experiment Results: H3 Geospatial Indexing ✅

Ran the full benchmark using fly.io sprite against the live parquet. TL;DR: ~5x speedup for geo queries with only 3.7% file size increase.

Baseline vs H3-Indexed Queries

Query Type	Baseline	With H3	Speedup
Bounding box (Western US)	170ms	35ms	4.85x
Bbox + source facet	187ms	38ms	4.87x
Map clustering (res6)	N/A	52ms	New capability

File Size Impact

Metric	Value
Original size	282 MB
With H3 columns (res4/6/8)	292 MB
Increase	3.7%
Generation time	42 seconds

H3 Cell Distribution

Resolution	Unique Cells	Use Case
Res 4	38,406	Broad filtering (continent/region)
Res 6	111,681	Map clustering
Res 8	175,653	Fine-grained selection

Coverage

• 5,980,282 samples with coordinates (89.5%)
• 6,680,932 total MaterialSampleRecords

Conclusions

1. H3 indexing is worth it - significant speedup, minimal overhead
2. Res4 for filtering, Res6 for clustering - matches Eric's recommendation from Dec SESSION_SUMMARY
3. Validates the approach for dashboard/frontend use cases
4. Integer column filtering outperforms lat/lon range scans

Recommended Implementation

-- Add H3 columns when generating wide parquet
SELECT *,
    h3_latlng_to_cell(latitude, longitude, 4) as h3_res4,
    h3_latlng_to_cell(latitude, longitude, 6) as h3_res6,
    h3_latlng_to_cell(latitude, longitude, 8) as h3_res8
FROM wide
WHERE latitude IS NOT NULL AND longitude IS NOT NULL

Reference

• Full results: https://github.com/rdhyee/pqg/blob/experiments/optimization-tasks/experiments/h3_optimization/results/benchmark_results.json
• Task spec: experiments/h3_optimization/TASK_SPEC.md

Ready to combine with #18 (facet optimization) for implementation PR.

[rdhyee]

@emetsger This validates your H3 approach from the December work - ~5x speedup for geo queries with minimal file size increase. Combined with the 140x facet speedup from #18, we have a solid optimization story for the dashboard. Would appreciate your review of the benchmark results.