PostgreSQL 內建 point 資料型別，把 point 值當作經緯度座標，就能記錄地表上的興趣點位置。開源專案 OpenStreetMap（OSM）發布可以自由使用的地理資料，例如英國的酒吧。

酒吧名稱資料庫#

透過 Overpass API，用如下 URL 就能下載一個包含英國地理定位酒吧的 XML 檔：

http://www.overpass-api.de/api/xapi?*[amenity=pub][bbox=-10.5,49.78,1.78,59]

OSM 的資料是以 EAV 模型組織的 XML：

<node id="262706" lat="51.0350300" lon="-0.7251785">
  <tag k="amenity" v="pub"/>
  <tag k="created_by" v="Potlatch 0.10f"/>
  <tag k="name" v="Kings Arms"/>
</node>

本章只需要非常簡單的資料庫 schema：

create table if not exists pubnames
 (
   id   bigint,
   pos  point,
   name text
 );

為了用 COPY 協定以串流方式載入，我們用 SAX API 讀 XML。做法是註冊標籤處理函式：

  • parse-osm-start-element 與 parse-osm-end-element 從 node 與 tag XML 元素抽出所需資訊，填進內部的 OSM 資料結構。
  • 一個 node 解析完成後，就透過 cl-postgres:open-db-writer 與 osm-to-pgsql 把這筆記錄序列化送進 PostgreSQL。

這裡使用的 Common Lisp 驅動 Postmodern 以 open-db-writer、db-write-row、close-db-writer 三個函式實作 COPY 協定（前面章節看過）——一邊解析一邊串流資料。同樣的做法可以用任何程式語言實作。

延伸範例：pubnames 專案的 SAX 解析與 COPY 載入（Common Lisp 節錄）
(defun parse-osm-end-element (source stream)
  "When we're done with a <node>, send the data over to the stream"
  (when (and (eq 'node (current-qname-as-symbol source))
         *current-osm*)
    ;; don't send data if we don't have a pub name
    (when (osm-name *current-osm*)
      (cl-postgres:db-write-row stream (osm-to-pgsql *current-osm*)))

    ;; reset *current-osm* for parsing the next <node>
    (setf *current-osm* nil)))

(defmethod osm-to-pgsql ((o osm))
  "Convert an OSM struct to a list that we can send over to PostgreSQL"
  (list (osm-id o)
    (format nil "(~a,~a)" (osm-lon o) (osm-lat o))
    (osm-name o)))

(defun import-osm-file (&key
             table-name sql pathname
             (truncate t)
             (drop nil))
  "Parse the given PATHNAME file, formated as OSM XML."

  (maybe-create-postgresql-table :table-name table-name
                 :sql sql
                 :drop drop
                 :truncate truncate)

  (klacks:with-open-source (s (cxml:make-source pathname))
    (loop
       with stream =
          (cl-postgres:open-db-writer (remove :port *pgconn*) table-name nil)
       for key = (klacks:peek s)
       while key
       do
          (case key
            (:start-element (parse-osm-start-element s))
            (:end-element    (parse-osm-end-element s stream)))
          (klacks:consume s)

          finally (return (cl-postgres:close-db-writer stream)))))

完整程式碼見 GitHub 上的 pubnames 專案。

資料正規化#

想找出英國最常見的酒吧名，需要做點輕量的資料正規化。資料載入後直接用 SQL 做既簡單又高效——這是所謂 ELT（extract、load，然後才 transform）而非常見的 ETL：

  select array_to_string(array_agg(distinct(name) order by name), ', '),
         count(*)
    from pubnames
group by replace(replace(name, 'The ', ''), 'And', '&')
order by count desc
   limit 5;
       array_to_string        │ count
══════════════════════════════╪═══════
 Red Lion, The Red Lion       │   350
 Royal Oak, The Royal Oak     │   287
 Crown, The Crown             │   204
 The White Hart, White Hart   │   180
 The White Horse, White Horse │   163
(5 rows)
  • array_agg(distinct(name) order by name) 做了所有苦工：把同名變體聚在一起、去重並排序。
  • array_to_string 則讓輸出以逗號分隔、方便閱讀。
  • 哪些名字算「同名」？拼寫變體相同者——我們不把 The 視為差異（取代成空字串），也把 And 與 & 視為同一回事。

地理定位最近的酒吧（k-NN 搜尋）#

在 PostgreSQL 實作 k-NN（k 最近鄰）搜尋，只要用距離運算子 <-> 排序結果集。搜尋已知位置附近酒吧的完整 SQL：

  select id, name, pos
    from pubnames
order by pos <-> point(-0.12,51.516)
   limit 3;
    id     │          name          │           pos
═══════════╪════════════════════════╪═════════════════════════
  21593238 │ All Bar One            │ (-0.1192746,51.5163499)
  26848690 │ The Shakespeare's Head │ (-0.1194731,51.5167871)
 371049718 │ The Newton Arms        │ (-0.1209811,51.5163032)
(3 rows)

point 型別實作的是抽象的二維座標系，不綁定任何地球投影。因此 <-> 算的是歐幾里得距離，point 本身不提供以公尺或英里計的地表距離——下一個範例會用 earthdistance 擴充處理這件事。

替 k-NN 搜尋建索引#

上面的查詢約花 20ms。資料集才 27,878 列，20ms 並不出色——因為資料表上還沒有任何索引，規劃器只能整表掃描、邊掃邊過濾。若能改用索引搜尋來滿足查詢限制（這裡是 ORDER BY 與 LIMIT），效能會好得多。這正是 GiST 與 SP-GiST 索引的設計目標，特別是 kNN GiST 支援：

create index on pubnames using gist(pos);

再跑同一個查詢並 explain：

  explain (analyze, verbose, buffers, costs off)
  select id, name, pos
    from pubnames
order by pos <-> point(51.516,-0.12)
   limit 3;
                               QUERY PLAN
════════════════════════════════════════════════════════════════════════
 Limit (actual time=0.071..0.077 rows=3 loops=1)
   Output: id, name, pos, ((pos <-> '(51.516,-0.12)'::point))
   Buffers: shared hit=6
   -> Index Scan using pubnames_pos_idx on public.pubnames (actual tim…
…e=0.070..0.076 rows=3 loops=1)
         Order By: (pubnames.pos <-> '(51.516,-0.12)'::point)
         Buffers: shared hit=6
 Planning time: 0.095 ms
 Execution time: 0.125 ms

在 27,878 列的資料集中，不到一毫秒就找出最近的三間酒吧——這種效能可以直接用在網頁應用中。即使資料集大得多，作者預期效能仍會在同一個量級；找個更大的資料集來驗證 kNN GiST 索引，就留作讀者的練習。

Backward 用 intarray 反正規化標籤 最近的酒吧有多遠 Forward