--- path: docs/spatial-sql-book/01-prerequisites title: Prerequisites: Joins and Big O desc: Why a join loses rows, why it multiplies them, and why an index decides if it finishes image: /images/spatial-sql-book/01-prerequisites/cover.webp --- # Prerequisites: Joins and Big O *Why a join loses rows, why it multiplies them, and why an index decides if it finishes* ## What this lesson covers - A join multiplies rows, and that is how totals go wrong - The filter that silently turns LEFT JOIN into INNER JOIN - Finding what is missing, not what matches - A spatial join is a join with a predicate in ON - Why the index is the difference between 72 ms and a timeout Run the query below. It returns a hundred named things — cafés, benches, post boxes, shrines — from six square kilometres of central Tokyo, and the map draws them where they stand. There are 2,184 of them in that box, of 75 different kinds. That cost nothing to set up. No Docker, no download, no `ogr2ogr`, no waiting: the OpenStreetMap extract behind it holds 440 million buildings and it is already connected. Every query on this page runs against it, and every one of them is yours to edit. Then come the questions that first result raises — and they are the rest of this lesson: - What if I want the *parcels*, and what is inside each one? - Why did moving one condition from `ON` to `WHERE` delete thirty of my rows? - Why is one parcel’s area coming back sixty-six times too large? - Why does the same query hang for thirty seconds if I drop the bounding box? Two ideas answer all four, and neither is about geography: **a join decides which rows survive** — and quietly multiplies them — and **an index decides whether that join finishes at all**. A spatial join is an ordinary join whose `ON` clause reads `ST_Contains(…)` instead of `a.id = b.id`, so every rule and every trap carries straight over. #### A hundred named things in central Tokyo ```sql SELECT name, osm_type, geom FROM osm.amenity_point WHERE geom && ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AND name IS NOT NULL LIMIT 100; ``` Five lines, one table, no joins and no functions except the one that draws the box. `&&` compares bounding boxes against the index, which is why this returns in milliseconds against a 440-million-row database. It selects `geom`, so the result is geometry — not a table about places, the places themselves. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* > **Not required reading** > > These lessons are for running queries, reading rows and pushing them onto the map as a layer — not for studying theory first. Skip ahead and come back when a query returns a number you do not believe, or sits there for thirty seconds. #### Now the parcels, and what is inside each one ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ) SELECT p.name AS parcel, count(a.osm_id) AS amenities, round(ST_Area(p.geom::geography)) AS area_m2, p.geom FROM parcels AS p LEFT JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) GROUP BY p.osm_id, p.name, p.geom ORDER BY amenities DESC LIMIT 50; ``` The first question from the intro. This is a spatial join: `osm.landuse_polygon` on the left, `osm.amenity_point` on the right, matched by `ST_Contains` instead of by an id. It is a LEFT JOIN, so a parcel holding nothing still appears — with a count of 0 rather than vanishing. It returns `geom` too, so this one is also a layer. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* ## Joins, in one page A spatial join is an ordinary join. The only difference is the matching condition: ```sql ON o.customer_id = c.id -- ordinary ON ST_Contains(parcel.geom, amenity.geom) -- spatial ``` Everything below is true of both. The two mistakes at the end are not join trivia — they are the two ways a spatial query returns a confident, wrong answer. ## Which rows survive | Join | Keeps | Unmatched rows | |---|---|---| | `INNER JOIN` | rows matching on both sides | dropped | | `LEFT JOIN` | every row on the left | right columns become `NULL` | | `FULL OUTER JOIN` | every row from either side | missing side becomes `NULL` | | `CROSS JOIN` | every combination | nothing matches, so nothing drops | `RIGHT JOIN` is `LEFT JOIN` with the tables swapped. Full reference: [PostgreSQL — joined tables](https://www.postgresql.org/docs/current/queries-table-expressions.html). ![The join types as Venn diagrams: inner, left, right, full outer, and their anti-join forms](/images/spatial-sql-book/01-prerequisites/sql-join.webp) The abstract shape, with three customers and three orders — one customer has two orders, and one order belongs to a customer who does not exist: ```sql -- INNER: only Alice, twice. Bob, Cara and the orphan order all disappear. SELECT c.name, o.id FROM customers AS c JOIN orders AS o ON o.customer_id = c.id; -- LEFT: all three customers; Bob and Cara get NULL order columns. SELECT c.name, o.id FROM customers AS c LEFT JOIN orders AS o ON o.customer_id = c.id; ``` Those two tables do not exist in this database — they are the picture. Every query you can run on this page uses the real thing: **`osm.landuse_polygon`** as the parcels and **`osm.amenity_point`** as what is inside them, both filtered to one bounding box in central Tokyo. In that box there are 342 landuse polygons, of which **34 carry a name**. ## Mistake 1 — the filter in the wrong clause `LEFT JOIN` promises to keep every left row. A condition on the **right** table in `WHERE` breaks that promise, because `NULL` fails every comparison: ```sql -- keeps all 34 parcels; those with no café simply have NULL on the right LEFT JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) AND a.osm_type = 'cafe' -- silently an INNER JOIN: only the 4 parcels that do have a café survive LEFT JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) WHERE a.osm_type = 'cafe' ``` Nothing errors. The row count drops from 34 to 4, and "parcels and their cafés" quietly becomes "parcels that have a café". **Filter the right table in `ON`. Filter the left table in `WHERE`.** ## Mistake 2 — rows multiply A parcel containing 66 amenities produces **66 rows**. Anything you sum over those rows is counted 66 times — including the parcel's own area, which has not changed at all: ```sql SELECT p.name, count(*) AS rows_the_join_made, round(p.area_m2) AS area_m2_once, round(sum(p.area_m2)) AS area_m2_if_you_sum_it -- 66× too big FROM parcels AS p JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) GROUP BY p.osm_id, p.name, p.area_m2; ``` `count(*)` counts join rows. `count(a.osm_id)` counts matches and ignores the `NULL` a `LEFT JOIN` inserts — so an empty parcel scores 0 rather than 1. When you only need to know *whether* something is inside, `EXISTS` never multiplies anything. ## Finding what is missing Which parcels contain nothing at all? An inner join cannot answer this — the rows it would need are exactly the ones it drops: ```sql SELECT p.name, p.geom FROM parcels AS p WHERE NOT EXISTS ( SELECT 1 FROM osm.amenity_point AS a WHERE ST_Contains(p.geom, a.geom) ); ``` 19 of the 34. That is the bottom half of the diagram — the shapes with the overlap removed — and because it returns `geom`, it is a layer you can put on the map. --- **In SedonaDB** the join types and both mistakes are identical; it is the same SQL dialect over files instead of tables. What differs is which predicates it can accelerate: [Sedona — spatial join optimizer](https://sedona.apache.org/latest/api/sql/Optimizer/). #### INNER JOIN — and the 30 parcels it deletes ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ) SELECT p.name AS parcel, a.name AS cafe, a.osm_subtype AS kind FROM parcels AS p JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) AND a.osm_type = 'cafe' ORDER BY p.name, a.name LIMIT 50; ``` The same two tables, joined the ordinary way and filtered to cafés. An inner join keeps only pairs that match on both sides, so a parcel with no café is not "a parcel with zero cafés" — it is gone. Four of the thirty-four parcels survive; the other thirty are simply absent from the result, with nothing to indicate they ever existed. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* #### The 19 parcels with nothing inside ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ) SELECT p.name AS parcel, round(ST_Area(p.geom::geography)) AS area_m2, p.geom FROM parcels AS p WHERE NOT EXISTS ( SELECT 1 FROM osm.amenity_point AS a WHERE ST_Contains(p.geom, a.geom) ) ORDER BY area_m2 DESC LIMIT 50; ``` The question an inner join structurally cannot answer, because the rows it needs are the ones it drops. `NOT EXISTS` asks it directly and stops at the first match, so it never builds the join and never multiplies anything. This is the bottom half of the Venn diagram — the shapes with the overlap removed — and it is often the more interesting half. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* #### The trap: the same filter, in ON and in WHERE ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ), filter_in_on AS ( SELECT p.osm_id FROM parcels AS p LEFT JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) AND a.osm_type = 'cafe' GROUP BY p.osm_id ), filter_in_where AS ( SELECT p.osm_id FROM parcels AS p LEFT JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) WHERE a.osm_type = 'cafe' GROUP BY p.osm_id ) SELECT 'osm_type = cafe in ON' AS filter_placement, count(*) AS parcels_returned FROM filter_in_on UNION ALL SELECT 'osm_type = cafe in WHERE', count(*) FROM filter_in_where; ``` Both halves of this query are a LEFT JOIN with `osm_type = 'cafe'`. The only difference is which clause the condition sits in. In `ON` it is part of the match, so unmatched parcels survive with NULL on the right. In `WHERE` it runs after the join, and NULL fails every comparison — so the rows the LEFT JOIN just created are deleted again and you have an inner join wearing a LEFT JOIN's clothes. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* #### A join multiplies rows — and your totals with them ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom, ST_Area(l.geom::geography) AS area_m2 FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ) SELECT p.name AS parcel, count(*) AS rows_the_join_made, round(p.area_m2) AS area_m2_once, round(sum(p.area_m2)) AS area_m2_if_you_sum_it FROM parcels AS p JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) GROUP BY p.osm_id, p.name, p.area_m2 ORDER BY rows_the_join_made DESC LIMIT 10; ``` Chiyoda contains 66 amenities, so the join emits 66 rows for it, each carrying a full copy of the parcel — including its area. Sum that column and you have added the same 1.4 km² sixty-six times. Nothing about the query looks wrong, and the result is off by a factor of 66. This is the single most common way a correct-looking spatial join produces a wrong number. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* > **Now make the ON clause spatial** > > Everything above holds with one substitution: `ON o.customer_id = c.id` becomes `ON ST_Contains(parcel.geom, amenity.geom)`. Same join types, same NULL rules, same row multiplication. > > What changes is the price of one comparison — and that is the second idea. #### Four desktop steps as one statement ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), parcels AS ( SELECT l.osm_id, l.name, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL AND l.name <> '' ) SELECT p.name AS parcel, a.osm_type AS category, count(*) AS amenities FROM parcels AS p JOIN osm.amenity_point AS a ON ST_Contains(p.geom, a.geom) GROUP BY p.osm_id, p.name, a.osm_type ORDER BY amenities DESC LIMIT 30; ``` Select by location, join, group, order — a four-step point-and-click workflow written once. The extra dimension here is `osm_type`, so each row is a parcel-and-category pair rather than a parcel total. This is the argument for spatial SQL over a desktop GIS: a query is versionable, diffable and re-runnable tomorrow, and a click history is none of those. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* ## Why some queries never finish You need none of this to write spatial SQL. You need it the first time a query hangs for thirty seconds and you have to guess why. The curve a query lands on is decided by one thing: **whether an index can answer its `ON` clause.** | Growth | What it means | Where you meet it | |---|---|---| | `O(log n)` | each step halves the candidates | an index probe | | `O(n)` | every row, once | a sequential scan | | `O(n × m)` | every left row against every right row | a join with no usable index | The first two are fine at any size here. The third is the cliff. ![Curves for O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!) against input size](/images/spatial-sql-book/01-prerequisites/big-O.png) ## The number that decides everything ```text osm.building_polygon 440,727,425 rows ``` Join that to anything without an index and you are asking for hundreds of billions of comparisons. The editor cancels the statement at 30 seconds, so what you actually see is a query that "doesn't work". This is why every query in these lessons carries a bounding box: ```sql WHERE geom && ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) ``` Same query, 72 ms instead of never. ## What the index actually does A GIST index stores each geometry's bounding box in a tree, so instead of scanning `m` rows the database descends it. On the small box used in this lesson — 342 polygons, 2,184 points: ```text no index 342 × 2,184 = 746,928 comparisons index 342 × log₂(2,184) ≈ 3,794 comparisons (~197× less) ``` And the gap widens as the data grows, because one side is a logarithm. See [PostgreSQL — index types](https://www.postgresql.org/docs/current/indexes-types.html) and [PostGIS — spatial indexing](https://postgis.net/workshops/postgis-intro/indexing.html). ## Why `&&` comes first PostGIS splits every spatial predicate in two: 1. [`&&`](https://postgis.net/docs/geometry_overlaps.html) compares **bounding boxes** — cheap, and the index can answer it. 2. [`ST_Contains`](https://postgis.net/docs/ST_Contains.html) compares **real geometry** — exact, and a 500-vertex polygon costs 500 vertices of arithmetic. The planner runs the cheap one first and the exact one only on the survivors. Defeat the index — wrap the geometry column in a function, compare across mismatched SRIDs — and you drop back onto the steep curve, with nothing to warn you except the wait. To see which path a query actually took, ask: [PostgreSQL — using EXPLAIN](https://www.postgresql.org/docs/current/using-explain.html). --- **In SedonaDB** there is no GIST index; it partitions and builds an index per query instead, and only for predicates it recognises — [Sedona — spatial join optimizer](https://sedona.apache.org/latest/api/sql/Optimizer/). The lesson is the same: a join it cannot accelerate is a join that compares every pair. #### Why && runs before ST_Contains ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), land AS ( SELECT l.osm_id, l.geom FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g AND l.name IS NOT NULL ), amenity AS ( SELECT a.osm_id, a.geom FROM osm.amenity_point AS a, box WHERE a.geom && box.g ) SELECT (SELECT count(*) FROM land) AS landuse_polygons, (SELECT count(*) FROM amenity) AS amenity_points, (SELECT count(*) FROM land AS l, amenity AS a WHERE l.geom && a.geom) AS bbox_candidate_pairs, (SELECT count(*) FROM land AS l, amenity AS a WHERE ST_Contains(l.geom, a.geom)) AS exact_pairs; ``` PostGIS splits every spatial predicate in two. && compares bounding boxes, which the GIST index can answer without reading a single coordinate; ST_Contains then runs the exact geometry test on the survivors. Counting both tells you how much work the cheap test removed before the expensive one started. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* #### Big O, measured on this bounding box ```sql WITH box AS ( SELECT ST_MakeEnvelope(139.75, 35.67, 139.78, 35.69, 4326) AS g ), counts AS ( SELECT (SELECT count(*) FROM osm.landuse_polygon AS l, box WHERE l.geom && box.g) AS n, (SELECT count(*) FROM osm.amenity_point AS a, box WHERE a.geom && box.g) AS m ) SELECT n AS landuse_polygons, m AS amenity_points, n * m AS comparisons_without_index, round(n * log(2, greatest(m, 2)::numeric)) AS comparisons_with_index, round((n * m)::numeric / greatest(round(n * log(2, greatest(m, 2)::numeric)), 1)) AS speedup FROM counts; ``` The chart above, evaluated against the rows actually in this bbox. With no index a join compares every pair: n × m. With one, each left row probes a tree instead, roughly n × log₂(m). The ratio is the speedup, and it widens with the data — which is why the same query shape is instant on a neighbourhood and impossible on the planet. *[Run this query yourself](https://app.gisowl.com/app/register?source=site)* > **One habit to keep** > > Every query here carries a bounding box. Drop it and `n × m` stops being a number you can write down: the statement hits the editor’s 30-second cap and is cancelled. > > That is the whole practical takeaway. Now go and break something on the map. ## Rules of thumb - Filter the right table in ON, never in WHERE. - Aggregate before you total — a join multiplies rows. - A spatial join is a join with a predicate in ON. - Let && go first; ST_Contains only runs on what survives. --- **Run these queries against a live PostGIS.** [Open the lesson in the app](https://app.gisowl.com/app/register?source=site) — the same SQL, an editor, and your own data. [Where Your SQL Runs](/docs/spatial-sql-book/02-where-your-sql-runs) → · [All lessons](/docs/spatial-sql-book)