select count(*)
       from child
tablesample bernoulli(5) -- If you're only after an estimate, TABLESAMPLE is your friend.
  left join parent on (child.parent_id = parent.id)
      where parent.id is null