Для запросов «появляется х раз» лучше всего использовать предложение HAVING. В вашем случае запрос может выглядеть так:
SELECT Date FROM table GROUP BY Date HAVING COUNT(*)<k
или, вам нужно выбрать другие столбцы, кроме даты:
SELECT * FROM Table WHERE Date IN (
SELECT Date FROM table GROUP BY Date HAVING COUNT(*)<k)
Вы также можете переписать IN в INNER JOIN, однако это не даст увеличения производительности, так как на самом деле оптимизатор запросов сделает это за вас в большинстве RDBMS. Индекс по дате, безусловно, улучшит производительность для этого запроса.