Index na record_num polju postoji?
Dalje, koliko se secam kad radis nesto ovako, MySQL "svlaci" prvih X slogova do setovanog offseta (prvi parametar u limitu) pa tek onda vrati slogove sa tog mesta.
Pogledaj ovaj link, mozda iskopas nesto korisno:
http://www.mysqlperformanceblog.com/...-optimization/