Nebylo by to víceméně přesně procento odstraněných řádků? Spočítejte tedy celkový počet řádků, poté spočítejte počet řádků, které splňují podmínku, a proveďte dělení. Samozřejmě, aby se tento prostor stal plně využitelným, možná budete muset znovu sestavit tabulku a/nebo index.
Předpokládám, že pokud máte data var-length a některé řádky jsou mnohem větší než jiné, pak tento přístup může být pouze přibližný, ale ve většině případů by měl být dost dobrý.