Sql Server paging rows by offset - without 'ORDER BY'

Question

A production table of mine contains over a million records. An requirement calls for a paging query to retrieve records by OFFSET and LIMIT parameters(similar to MySql's LIMIT clause), without sorting the result set, just as rows' natural order are in a table-scan, since 'ORDER BY' generates unacceptable performance impact, including 'ORDER BY' clause used in traditional technique of ROW_NUMBER() OVER (ORDER BY ...).
Could any expert offer a solution to this problem? Paging records without any ordering of the result set. e.g.

Create table RandomRecords(int id, datetime recordDate)
----
select * from RandomRecords
34, '1/1/2009'
123, '8/1/2008'
11, '2/23/2008'
10, '3/2/2008'
4, '2/5/2009'
78, '1/1/2008'
55, '5/2/2008'
6666, '2/12/2009'
....
one million rows

-----
paging query with @Offset = 3 and @limit=4 generates
11, '2/23/2008'
10, '3/2/2008'
4, '2/5/2009'
78, '1/1/2008'

Answer 1

ORDER BY only generates additional impact if it cannot be addressed by an index. If you see 'unacceptable' impact it means that either you did not properly design your table, or you did not properly design the query.

Some us constant ORDER BY expressions SELECT ..., ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM .... But that may still generate a sorting spool if not properly designed.

So to consider your example:

CREATE TABLE RandomRecords (recordId int not null primary key, id int);
INSERT INTO RandomRecords (id) values (...)
WITH PagedRandomRecords (
   SELECT id, 
      ROW_NUMBER() OVER (ORDER BY recordId) as rn
      FROM RandomRecords)
SELECT id FROM PagedRandomRecords
   WHERE rn BETWEEN 3 and 7;

This will not sort the data because the recordId PK clustered index can deliver the rows in the needed order.

Answer 2

This is just meant as a comment in addition to Remus' answer.

Paging a primary key doesn't cause SQL Server to sort, because the primary key is stored in sort order. You can page on primary key without a WITH statement like:

SELECT *
FROM (
    SELECT 
        ROW_NUMBER() OVER (ORDER BY PrimaryKey) as rn
    ,   *
    FROM BigTable
) sub 
WHERE sub.rn BETWEEN 3 and 7

The subquery is still required, because you can't use ROW_NUMBER() in a WHERE statement.