to ti je zbog ORDER BY, on mora uvek da prvo sortira svih 700K redova...
imas dva resenja, ili da smanjis broj redova kao sto kaze salebab, ili da optimizujes indexe na tabeli tako da se sortiranje radi na indexima direktno. Tu je takodje bitno i da mysql ima dovoljno memorije da mu ceo index stane u memoriju.
dodaj EXPLAIN ispred upita pa vidi sta ce da ti kaze... i procitaj
ovo
EDIT: pretece me dinke
EDIT2: Da ne pravim novu poruku, za FULLTEXT ti je isti problem, jer sam full text search je jako brz, ali verovatno interracial (hmm, cime se ti to bavis?
) vrati previse rezultata...