@code_type sql .sql
@comment_type -- %s
@compiler lit -t sql/README.lit && bash -c 'for f in **/*.sql; do echo "-- GENERATED - DO NOT MODIFY. See README.lit" >> $f; done'

@title Geocoding Queries

The geocoder uses an in-memory DuckDB database that is loaded on startup from WhosOnFirst data in parquet format. This file explains the thinking behind the queries. The query files are built using the literate programming application `lit`. Do not change the generated query files, change things in this file and rebuild.

@s Loading the database

On startup, the database is loaded in memory using only a subset of the available columns in the parquet file. It uses an aggregation query to clean up duplicate data.

In the raw database, there are often multiple entries for large localities with slightly different (lon, lat) locations.  When using this in an autocomplete setup, it's confusing to have many entries with the same name that don't appear different aside from being in different nearby locations.

The aggregation query groups entries that have the same name + placetype + country and are in the same H3 cell (close geographically within ~20km), returning just one representative row as determined by the entry with the largest population and most recent modification date.

An index is added in the Go code on the prefix field, ensuring fast lookups for forward geocoding.

--- sql/load.sql
-- GENERATED - DO NOT MODIFY. See README.lit
INSTALL spatial;
LOAD spatial;
SET geometry_always_xy = true;
INSTALL h3 FROM community;
LOAD h3;

CREATE TABLE data AS
WITH clean AS (
    SELECT
        id,
        parent_id,
        name,
        placetype,
        country,
        lon,
        lat,
        h3_latlng_to_cell(lat, lon, 4) as cell_id,
        modified,
        len(population) as pop_mag,
        ST_Point(lon, lat) AS point,
        substring(lower(name), 1, 3) as prefix,
        ROW_NUMBER() OVER (PARTITION BY name, placetype, country, cell_id ORDER BY pop_mag DESC, modified DESC) as rn
    FROM '%s'
    WHERE placetype NOT IN ['country', 'continent']
)
SELECT *
FROM clean
WHERE rn = 1;
---

@s Forward geocoding

Forward geocoding is done in two steps for performance reasons. The first step is to use the prefix index to match on candidate locations, returning up to 10.  Distance and bearing are calculated from the bias point, if it exists. A separate query is used when no bias point exists. Distance and bearing are 0 in that case.

--- sql/fwd_bias.sql
-- GENERATED - DO NOT MODIFY. See README.lit
SELECT
    id as gid,
    name,
    placetype,
    lon,
    lat,
    ST_Distance_Sphere(point, ST_Point($1, $2)) AS distance,
    ST_Azimuth(ST_Point($1, $2), point) * 180.0 / 3.14159 AS bearing,
    country
FROM data
WHERE
    substring(lower($3), 1, 3) = prefix
AND
    name ILIKE concat($3, '%')
ORDER BY pop_mag DESC, distance ASC
LIMIT 10;
---

For no bias point:

--- sql/fwd_no_bias.sql
-- GENERATED - DO NOT MODIFY. See README.lit
SELECT
    id as gid,
    name,
    placetype,
    lon,
    lat,
    country
FROM data
WHERE
    substring(lower($1), 1, 3) = prefix
AND
    name ILIKE concat($1, '%')
LIMIT 10;
---

The WOF database is organized in a tree-like structure with rows referring to their parents as they work up the hierarchy from neighbourhood -> locality -> county -> country -> continent.  Some of these may not be present for all rows.  To gather this information, a recursive CTE walks up from the initial root until the parent_id no longer exists or is -1.  These results are returned as an Array[name] excluding the root row name.

--- sql/regions.sql
-- GENERATED - DO NOT MODIFY. See README.lit
WITH RECURSIVE parent_chain AS (
    SELECT
        id,
        parent_id,
        name,
        CAST([] AS VARCHAR[]) AS path_names
    FROM data
    WHERE id = $1

    UNION ALL

    SELECT
        t.id,
        t.parent_id,
        t.name,
        array_append(pc.path_names, t.name)
    FROM data t
    JOIN parent_chain pc ON t.id = pc.parent_id
    WHERE pc.parent_id != -1
)
SELECT path_names
FROM parent_chain
ORDER BY array_length(path_names) DESC
LIMIT 1;
---

@s Reverse geocoding

Reverse geocoding does a sequential table scan to find the point closest to given (lon, lat).  This can be slow, but testing shows that it's fast enough even on modest hardware.  An RTree index in memory for the entire database costs a lot of memory and isn't currently worth it.

--- sql/rev.sql
-- GENERATED - DO NOT MODIFY. See README.lit
SELECT
    id as gid,
    name,
    placetype,
    lon,
    lat,
    ST_Distance_Sphere(point, ST_Point($1, $2)) as distance,
    ST_Azimuth(ST_Point($1, $2), point) * 180.0 / 3.14159 AS bearing,
    country
FROM data
ORDER BY distance
LIMIT 1
---

@s Open location codes

The forward geocoder also processes the Google Maps open location code (plus code) for geolocating points that wouldn't appear in the administrative data of the WOF dataset.  Plus codes come in many formats, some exactly specifying the point with only the OLC, and others in a shortened form that includes a reference point, like "35X5+PP Shimla, Himachal Pradesh"

@s Open location codes

The forward geocoder also processes the Google Maps open location code (plus code) for geolocating points that wouldn't appear in the administrative data of the WOF dataset.  Plus codes come in many formats, some exactly specifying the point with only the OLC, and others in a shortened form that includes a reference point, like "35X5+PP Shimla, Himachal Pradesh"

To decode short points, the reference location must first be forward geocoded. Some plus codes include the country while others use a regional point of reference. To accomodate both possibilities, two queries are used.

The first filters results to only the country of interest when known:

--- sql/plus_country.sql
-- GENERATED - DO NOT MODIFY. See README.lit
SELECT
    id as gid,
    name,
    placetype,
    lon,
    lat,
    country
FROM data
WHERE
    substring(lower($1), 1, 3) = prefix
AND
    name ILIKE concat($1, '%')
AND
    country = $2
AND
    placetype IN ['locality', 'county']
ORDER BY pop_mag DESC, placetype ASC;
---

When the country is not known, the query gets all results and in code looks for the region name in its hierarchy:

--- sql/plus_no_country.sql
-- GENERATED - DO NOT MODIFY. See README.lit
SELECT
    id as gid,
    name,
    placetype,
    lon,
    lat,
    country
FROM data
WHERE
    substring(lower($1), 1, 3) = prefix
AND
    name ILIKE concat($1, '%')
AND
    placetype IN ['locality', 'county']
ORDER BY pop_mag DESC, placetype ASC;
---