[CALCITE-2160] Spatial grid index, to accelerate polygon-to-polygon spatial joins

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.25.0
• Component/s: spatial
• Assignee: Julian Hyde
• Reporter: Julian Hyde
• Created: 30/Jan/18 21:56
• Updated: 22/Aug/20 18:48
• Resolved: 29/Jul/20 01:06

Description

Recognize materialized views that convert a geometry into a grid of rectangles, and use such materialized views for point-to-polygon and polgyon-to-polygon joins.

Implement the ST_MakeGrid and ST_MakeGridPoints functions.

Add a test data set based upon western U.S. states and national parks. Given a materialized view

CREATE MATERIALIZED VIEW StateGrids (name, x, y, PRIMARY KEY (name)) AS
SELECT s.name, ST_XMin(g.the_geom), ST_YMin(g.the_geom)
FROM States AS s
CROSS APPLY TABLE(ST_MakeGrid(s.geom, 1, 1)) AS g

and a similar materialized view ParkGrids on Parks, the query

SELECT p.name AS park, s.name AS state
FROM Parks AS p
JOIN States AS s ON ST_Overlaps(s.geom, p.geom)
ORDER BY 1, 2

should return

Park         State
============ =====
Death Valley CA
Death Valley NV
Yellowstone  ID
Yellowstone  MT
Yellowstone  WY
Yosemite     CA

and should semi-join to the StateGrids and ParkGrids tables to reduce the size of the input before applying St_Overlaps:

SELECT p.name AS park, s.name AS state
FROM Parks AS p
JOIN States AS s ON ST_Overlaps(s.geom, p.geom)
WHERE (p.name, s.name) IN (
  SELECT DISTINCT pg.name, sg.name
  FROM ParkGrids AS pg
  JOIN StateGrids AS sg ON pg.id = sg.id)

Note the semi-join, to remove duplicates in case a park and a state have several cells that overlap.

Issue Links

• depends upon: CALCITE-2569 UDFs that are table functions must implement SqlTableFunction and have CURSOR as their return type
• relates to: CALCITE-531 Window function does not work in LATERAL