Efficiently find common ancestor in postgresql directed acyclic graph

Here is another solution with PL/pgSQL.

Only makes sense for deep roots – many nodes to the common ancestor. The point being to avoid executing a single-row SELECT and array concatenation for every single element. Instead, collect an (adjustable) number of nodes and concatenate that once – while the search continues. With a shortcut for the other leg, after one leg ends.

Hard to say where the additional overhead starts to pay off. Test with different data sets and different batch sizes (_batch_size). I set the default at 100. It’s increased dynamically with every iteration in the loop to cover both short and long paths.

Auxiliary function to dig up a given number of steps:

CREATE OR REPLACE FUNCTION f_roots(_a text, _b_roots text[], _batch_size int)
  RETURNS text[]
  LANGUAGE sql STABLE STRICT
BEGIN ATOMIC
WITH RECURSIVE roots AS (
   SELECT g.parent AS node
   FROM   graphtable g
   WHERE  g.id = _a

   UNION ALL
   SELECT (SELECT g.parent FROM graphtable g WHERE g.id = r.node)
   FROM   roots r   
   WHERE  r.node <> ALL(_b_roots)
   )
SELECT ARRAY(TABLE roots LIMIT _batch_size);
END;

See:

• What does BEGIN ATOMIC mean in a PostgreSQL SQL function / procedure?

It takes the node to be advanced, and the array of nodes from the other side. The last element is null if the root node has been reached.
The functions stops at the first match, so (only) the last element can be a match.

Main function:

CREATE OR REPLACE FUNCTION f_common_root(_a text, _b text, _batch_size int = 100)
  RETURNS text
  LANGUAGE plpgsql STABLE AS
$func$
DECLARE
   a_roots  text[] := ARRAY[_a];
   b_roots  text[] := ARRAY[_b];
   a_step   text[];
   b_step   text[];
   last_a   text := _a;
   last_b   text := _b;
BEGIN
   -- corner case
   IF _a = _b THEN
      RETURN _a;
   END IF;

   LOOP
      -- get the next _batch_size nodes for a
      IF last_a IS NOT NULL THEN
         a_step := f_roots(last_a, b_roots, _batch_size);
         last_a := a_step[array_upper(a_step, 1)];

         IF last_a IS NULL THEN
            -- trim last null!
            a_roots := a_roots || a_step[1:array_upper(a_step, 1)-1];
         ELSIF last_a = ANY(b_roots) THEN
            RETURN last_a;
         ELSE
            a_roots := a_roots || a_step;
         END IF;
      END IF;

      -- shortcut to finish other side (no more array concatenation needed)
      IF last_a IS NULL THEN
         LOOP
            SELECT INTO last_b  g.parent
            FROM   graphtable g
            WHERE  g.id = last_b;
            
            IF NOT FOUND THEN
               RETURN null;
            ELSIF last_b = ANY(a_roots) THEN
               RETURN last_b;
            END IF;
         END LOOP;
      END IF;


      -- EXACTLY symmetrical for b
      IF last_b IS NOT NULL THEN
         b_step := f_roots(last_b, a_roots, _batch_size);
         last_b := b_step[array_upper(b_step, 1)];

         IF last_b IS NULL THEN
            b_roots := b_roots || b_step[1:array_upper(b_step, 1)-1];
         ELSIF last_b = ANY(a_roots) THEN
            RETURN last_b;
         ELSE
            b_roots := b_roots || b_step;
         END IF;
      END IF;      
      
      IF last_b IS NULL THEN
         LOOP
            SELECT INTO last_a  g.parent
            FROM   graphtable g
            WHERE  g.id = last_a;
            
            IF NOT FOUND THEN
               RETURN null;
            ELSIF last_a = ANY(b_roots) THEN
               RETURN last_a;
            END IF;
         END LOOP;
      END IF;

      -- grow batch_size dynamically
      _batch_size := (_batch_size * 1.5)::int;
   END LOOP;   
END
$func$;

Call (with optional custom _batch_size):

SELECT f_common_root('branch-a-head-id', 'branch-b-head-id');

SELECT f_common_root('branch-a-head-id', 'branch-b-head-id', 500);

fiddle