Inizia ad utilizzare i tipi appropriati per i campi visto che le date in un campo char sono una schifezza.
Se non ricordo male qualche tempo fa ti avevo suggerito come convertire le date nel giusto formato. Impieghi due minuti a farlo e hai un campo congruo ai dati che deve contenere.

Per la tua domanda circa la velocità di esecuzione sicuramente è più rapida una select count di una query che magari estrae tutti i campi di una tabella e della quale poi conti le righe con la funzione mysql_num_rows.

Poi nel tuo caso specifico bisognerebbe vedere come hai strutturato il tutto, se utilizzi degli indici per sveltire le ricerche,ecc. I problemi certamente non sono dovuti a 65 mila record.

Prova a leggerti questi articoli
http://php.html.it/articoli/leggi/89...sql-con-php/1/
http://php.html.it/articoli/leggi/92...le-pagine-web/
http://database.html.it/guide/lezion...ttimizzazione/

e vedi se trovi qualche suggerimento utile a ridurre i tuoi tempi.

Nel caso dovessi avere ancora problemi prova a postare che tanti più esperti di me sulla progettazione di basi di dati sapranno consigliarti meglio.