Самый быстрый способ найти/добавить недостающие строки (50 000+)

У меня есть таблица Mysql (innodb) с ровно 50 млн строк (да, 50 млн строк, не больше и не меньше) со следующими столбцами:

• 'ai' -> Автоинкремент, беззнаковое большое число;
• 'client_id' -> уникальный ключ, unsigned bigint;
• 'has_dog' -> логическое значение;
• со временем будет больше...

Допустим: Я хочу отправить всем клиентам, у которых есть собака, подарок. С помощью простого запроса я могу найти всех владельцев собак, но... Но что, если некоторые строки отсутствуют? Может удалил? Может вообще не вставил? Когда я ищу COUNT(client_id), я ожидаю ровно 50 000 000 строк, но результат, к сожалению, меньше.

Вопрос: Имея 10 строк, легко увидеть, каких строк не хватает, но как узнать, каких строк не хватает, если 50 млн строк?