Quando executar novamente o CLUSTER?

Você pode usar correlationas estatísticas da coluna coletadas por ANALYZE(ou em segundo plano por autovacuum) como indicador:

SELECT schemaname, tablename, attname, correlation
FROM   pg_stats
WHERE  tablename = 'sometable';

O manual:

correlation float4

Correlação estatística entre a ordenação física das linhas e a ordenação lógica dos valores das colunas. Isso varia de -1 a +1. Quando o valor estiver próximo de -1 ou +1, uma varredura de índice na coluna será estimada como mais barata do que quando estiver próxima de zero, devido à redução do acesso aleatório ao disco. (Esta coluna será nula se o tipo de dados da coluna não tiver um operador <.)

O valor de correlação da coluna usada como campo de índice inicial pode ser seu guia. Quanto mais próximo de 0 estiver, mais você precisará executar novamente CLUSTER. Depende muito do seu caso de uso o quão perto você precisa chegar da ordem de classificação perfeita.

Aumente a meta estatística da coluna e/ou execute ANALYZEprimeiro para aumentar a precisão. Ver:

• Estatísticas inconsistentes na coluna jsonb com índice btree

Para índices com múltiplas colunas, a primeira coluna deve ser boa o suficiente como indicador. Ou você pode usar estatísticas multivariadas para melhorar a validade em casos especiais.

Você pode considerar uma das ferramentas da comunidade (superiores) para substituir o CLUSTER. Ver:

• Configurando o PostgreSQL para desempenho de leitura