I have a collection with 35m objects with avg size 430 bytes. There are several indices including

and when I run a count on {"f": 0, wc: {$gt: 4}}) I get about 530k matches - this took a minute or so.

Next I tried a delete using the same query, which is live but not very loaded right now. After over 8 hours it is still running. I see a lot of wait time in top - so I guess it's i/o bound.

The machine has 70G of ram and the filesystem is ext4 with RAID5.