Um detalhe que ajuda a entender o ganho dos 70x: o ON DELETE CASCADE é executado por gatilhos internos de integridade, que disparam uma busca na tabela filha para cada linha removida da tabela pai. Então, ao apagar um tenant com milhares de usuários, a tabela de logs recebe milhares de buscas, e sem índice cada uma vira uma varredura completa. Por isso o índice na coluna da FK pesa mais do que parece num teste com uma única linha. Para a purga em lotes, vale também definir um lock_timeout na sessão, para que um lote que esbarre em linhas travadas falhe rápido e possa ser repetido, em vez de ficar esperando e segurando outros locks.