PostgreSQL/PostGIS - Fast MST over a set of POINT geometries.

point_set_minimum_spanning_tree.sql

/*
 * Generates the minimum spanning tree (MST) over a set
 * of POINT geometries. In pure SQL, this is about the most
 * performant way for the specific case of point sets,
 * given proper spatial indexing of the <graph> table/MV.
 *
 * Assumes the presence of an <id> and <geom> column in <graph>.
 */

WITH RECURSIVE
  tree AS (
    SELECT
      g.<geom>::GEOMETRY AS vtcs,
      NULL::GEOMETRY AS segment,
      ARRAY[g.<id>] AS ids
    FROM
      <graph> AS g
    WHERE
      g.<id> = 1   
    UNION ALL   
    SELECT
      ST_Union(t.vtcs, v.<geom>),
      ST_ShortestLine(t.vtcs, v.<geom>),
      t.ids || v.<id>
    FROM
      tree AS t
      CROSS JOIN LATERAL (
        SELECT
          g.<id>, g.<geom>
        FROM
          <graph> AS g
        WHERE
          NOT g.<id> = ANY(t.ids)
        ORDER BY
          t.vtcs <-> g.<geom>
        LIMIT
          1
      ) AS v
  )       
SELECT
  segment
FROM
  tree
WHERE
  segment IS NOT NULL
;

This may or may not benefit from a PL/pgSQL impementation...