You don't need to heapsort the entire dataset before you offset to a page, and there are engines capable of doing this.