Simple count id in MySql table is taking to long

I have to tables with 65.5 Million rows: 1) CREATE TABLE RawData1 ( cdasite varchar(45) COLLATE utf8_unicode_ci NOT NULL, id int(20) NOT NULL DEFAULT '0', timedate datetime NOT NULL DEFAULT '0000-00-00 00:00:00', type int(11) NOT NULL DEFAULT '0', status int(11) NOT NULL DEFAULT '0', branch_id int(20) DEFAULT NULL, branch_idString varchar(64) COLLATE utf8_unicode_ci DEFAULT NULL, PRIMARY KEY (id,cdasite,timedate), KEY idx_timedate (timedate,cdasite) ) ENGINE=InnoDB; 2) Same table with partition (call it RawData2) PARTITION BY RANGE ( TO_DAYS(timedate)) (PARTITION p20140101 VALUES LESS THAN (735599) ENGINE = InnoDB, PARTITION p20140401 VALUES LESS THAN (735689) ENGINE = InnoDB, . . PARTITION p20201001 VALUES LESS THAN (738064) ENGINE = InnoDB, PARTITION future VALUES LESS THAN MAXVALUE ENGINE = InnoDB); I'm using the same query: SELECT count(id) FROM RawData1 where timedate BETWEEN DATE_FORMAT(date_sub(now(),INTERVAL 2 YEAR),'%Y-%m-01') AND now(); 2 problems: 1. why the partitioned table runs longer then the regular table? 2. the regular table returns 36380217 in 17.094 Sec. is it normal, all R&D leaders think it is not fast enough, it need to return in ~2 Sec. What do I need to check / do / change ? Is it realistic to scan 35732495 rows and retrieve 36380217 in less then 3-4 sec?