Não seria apenas mais ou menos exatamente a porcentagem das linhas removidas? Portanto, conte o número total de linhas, conte o número de linhas que atendem à condição e faça a divisão. É claro que para que esse espaço se torne totalmente utilizável, talvez seja necessário reconstruir a tabela e/ou o índice.

Suponho que se você tiver dados de comprimento var e algumas linhas forem muito maiores que outras, essa abordagem pode ser apenas aproximada, mas na maioria dos casos deve ser boa o suficiente.