Mysql - How to Optimize Retrieval Time in a Table
Maybe GROUP BY can help. See this MySQL reference on DISTINCT optimization

SELECT COUNT(*)
FROM (
  SELECT 1
  FROM [tablename]
  WHERE [columnname] &gt;= 3
  GROUP BY id
) q