Profundidade descendente recursiva do PostgreSQL

A consulta que você tem está basicamente correta. O único erro está na segunda parte (recursiva) do CTE onde tem:

INNER JOIN descendants d ON d.parent_id = o.object_id

Deveria ser o contrário:

INNER JOIN descendants d ON d.object_id = o.parent_id 

Você deseja juntar os objetos com seus pais (que já foram encontrados).

Assim, a consulta que calcula a profundidade pode ser escrita (nada mais alterado, apenas a formatação):

-- calculate generation / depth, no updates
WITH RECURSIVE descendants
  (id, customer_id, object_id, parent_id, ancestor_id, depth) AS
 AS ( SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
      FROM objects
      WHERE object_id = parent_id

      UNION ALL

      SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  d.customer_id = o.customer_id
                               AND d.object_id = o.parent_id  
      WHERE d.id <> o.id
    ) 
SELECT * 
FROM descendants d
ORDER BY id ;

Para a atualização, basta substituir o último SELECT, pelo UPDATE, juntando o resultado do cte, de volta à tabela:

-- update nodes
WITH RECURSIVE descendants
    -- nothing changes here except
    -- ancestor_id and parent_id 
    -- which can be omitted form the select lists
    ) 
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.id = d.id 
  AND o.generation = -1 ;          -- skip unnecessary updates

Testado no SQLfiddle

Comentários adicionais:

• the ancestor_ide the parent_idnão precisam estar na lista de seleção (antepassado é óbvio, pai um pouco complicado para descobrir o porquê), então você pode mantê-los na SELECTconsulta se quiser, mas pode removê-los com segurança do arquivo UPDATE.
• o (customer_id, object_id)parece ser um candidato a uma UNIQUErestrição. Se seus dados estiverem em conformidade com isso, adicione essa restrição. As uniões realizadas no CTE recursivo não fariam sentido se não fossem únicas (caso contrário, um nó poderia ter 2 pais).
• se você adicionar essa restrição, (customer_id, parent_id)seria um candidato a uma FOREIGN KEYrestrição que REFERENCESo (exclusivo) (customer_id, object_id). Você provavelmente não deseja adicionar essa restrição FK, pois, pela sua descrição, você está adicionando novas linhas e algumas linhas podem fazer referência a outras que ainda não foram adicionadas.
• Certamente há problemas com a eficiência da consulta, se ela for realizada em uma tabela grande. Não na primeira execução, pois quase toda a tabela será atualizada de qualquer maneira. Mas, na segunda vez, você deseja que apenas novas linhas (e aquelas que não foram tocadas pela 1ª execução) sejam consideradas para atualização. O CTE como está terá que construir um grande resultado.
  O AND o.generation = -1na atualização final garantirá que as linhas que foram atualizadas na 1ª execução não sejam atualizadas novamente, mas o CTE ainda é uma parte cara.

A seguir, uma tentativa de resolver esses problemas: melhorar o CTE para considerar o menor número possível de linhas e usar (customer_id, obejct_id)em vez de (id)para identificar linhas (portanto, idé completamente removido da consulta. Pode ser usado como a 1ª atualização ou uma subsequente:

WITH RECURSIVE descendants 
  (customer_id, object_id, depth) 
 AS ( SELECT customer_id, object_id, 0
      FROM objects
      WHERE object_id = parent_id
        AND generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, p.generation + 1
      FROM objects o
        JOIN objects p ON  p.customer_id = o.customer_id
                       AND p.object_id = o.parent_id
                       AND p.generation > -1
      WHERE o.generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  o.customer_id = d.customer_id
                               AND o.parent_id = d.object_id
      WHERE o.parent_id <> o.object_id
        AND o.generation = -1
    )
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.customer_id = d.customer_id
  AND o.object_id = d.object_id
  AND o.generation = -1        -- this is not really needed

Observe como o CTE tem 3 partes. As duas primeiras são as partes estáveis. A primeira parte encontra os nós raiz que não foram atualizados antes e ainda generation=-1devem ser nós adicionados recentemente. A 2ª parte encontra filhos (com generation=-1) de nós pais que foram atualizados anteriormente.
A terceira parte, recursiva, encontra todos os descendentes das duas primeiras partes, como antes.

Testado no SQLfiddle-2

@ypercube já fornece ampla explicação, então vou direto ao ponto o que tenho a acrescentar.

Se parent_idnão existir, deve deixar a coluna de geração definida como -1.

Presumo que isso deva ser aplicado recursivamente, ou seja, o restante da árvore sempre ocorre generation = -1após qualquer nó ausente.

Se algum nó na árvore pode estar faltando (ainda), precisamos encontrar linhas com generation = -1isso ...
... são nós raiz
... ou têm um pai com generation > -1.
E atravesse a árvore a partir daí. Os nós filhos desta seleção também devem ter generation = -1.

Pegue o generationdo pai incrementado em um ou volte para 0 para os nós raiz:

WITH RECURSIVE tree AS (
   SELECT c.customer_id, c.object_id, COALESCE(p.generation + 1, 0) AS depth
   FROM   objects      c
   LEFT   JOIN objects p ON c.customer_id = p.customer_id
                        AND c.parent_id   = p.object_id
                        AND p.generation > -1
   WHERE  c.generation = -1
   AND   (c.parent_id = c.object_id OR p.generation > -1)
       -- root node ... or parent with generation > -1

   UNION ALL
   SELECT customer_id, c.object_id, p.depth + 1
   FROM   objects c
   JOIN   tree    p USING (customer_id)
   WHERE  c.parent_id  = p.object_id
   AND    c.parent_id <> c.object_id  -- exclude root nodes
   AND    c.generation = -1           -- logically redundant, but see below!
   )
UPDATE objects o 
SET    generation = t.depth
FROM   tree t
WHERE  o.customer_id = t.customer_id
AND    o.object_id   = t.object_id;

A parte não recursiva é única SELECTdessa maneira, mas logicamente equivalente ao two union'ed de @ypercube SELECT. Não tenho certeza qual é mais rápido, você terá que testar.
O ponto muito mais importante para o desempenho é:

Índice!

Se você adicionar repetidamente linhas a uma tabela grande dessa maneira, adicione um índice parcial :

CREATE INDEX objects_your_name_idx ON objects (customer_id, parent_id, object_id)
WHERE  generation = -1;

Isso alcançará mais desempenho do que todas as outras melhorias discutidas até agora - para pequenas adições repetidas a uma grande tabela.

Adicionei a condição de índice à parte recursiva do CTE (embora logicamente redundante) para ajudar o planejador de consulta a entender que o índice parcial é aplicável.

Além disso, você provavelmente também deve ter a UNIQUErestrição (object_id, customer_id)naquele @ypercube já mencionado. Ou, se você não puder impor exclusividade por algum motivo (por quê?) Adicione um índice simples. A ordem das colunas do índice é importante, btw:

• Um índice composto também é bom para consultas no primeiro campo?