Eğer ürün sayısı çok fazla ise cron ile parçalar halinde yapmak mantıklı. Aksi taktirde adminden kategoriyi silme işleminde ajax ile mantıklı.
Edit: MySQL fonksiyonları genelde yavaş çalışıyor PHP ile test edip belki hızlandırabilirsiniz.