How can I do cursor pagination with string based columns and integer values?

Pagination in SQL Server can be done by two differents ways in standard ISO SQL:

1) with ORDER BY only :

SELECT *
FROM   Customers
ORDER  BY City DESC, ID DESC OFFSET 0 ROWS FETCH NEXT 11 ROWS ONLY;

To paginate with a 10 rows page and having page 7, you can execute this query :

SELECT *
FROM   Customers
ORDER  BY City DESC, ID DESC OFFSET 1 + 10 * 7  ROWS FETCH NEXT 10 ROWS ONLY;

More generically you can use SQL variables :

DECLARE @PAGE INT = 7, @ROWS INT = 10;
SELECT *
FROM   Customers
ORDER  BY City DESC, ID DESC OFFSET 1 + @ROWS * @PAGE  ROWS FETCH NEXT @ROWS ROWS ONLY;

If OFFSET / FETCH is not available in your SQL Server version...

2) Pagination with ROW_NUMBER() window function:

WITH 
QUERY AS
(
SELECT *, ROW_NUMBER() OVER(ORDER BY City DESC, ID DESC) AS ROWNUM
FROM   Customers
)
SELECT * 
FROM   QUERY
WHERE  ROWNUM <= 11
ORDER  BY 1 City DESC, ID DESC;

To paginate with a 10 rows page and having page 7, you can execute this query :

WITH 
QUERY AS
(
SELECT *, ROW_NUMBER() OVER(ORDER BY City DESC, ID DESC) AS ROWNUM
FROM   Customers
)
SELECT * 
FROM   QUERY
WHERE  ROWNUM BETWEEN 1 + 10 * 7 AND (7 + 1) * 10
ORDER  BY 1 City DESC, ID DESC;

And generically :

DECLARE @PAGE INT = 7, @ROWS INT = 10;
WITH 
QUERY AS
(
SELECT *, ROW_NUMBER() OVER(ORDER BY City DESC, ID DESC) AS ROWNUM
FROM   Customers
)
SELECT * 
FROM   QUERY
WHERE  ROWNUM BETWEEN 1 + @ROWS * @PAGE AND (@PAGE + 1) * @ROWS
ORDER  BY 1 City DESC, ID DESC;

By the way TOP is a non standard operator specific to MS SQL Server and should not be used if some SQL ISO standard can do the same or best...

I have been able to coble together a solution that is a combination of @The Impaler's answer and the information use-the-index-luke.com's website, specifically this tidbit:

SELECT *
  FROM ( SELECT *
           FROM sales
          WHERE sale_date <= ?
            AND NOT (sale_date = ? AND sale_id >= ?)
          ORDER BY sale_date DESC, sale_id DESC
       )
 WHERE rownum <= 10

I took two options, one using offset / limit and one using the cursor based approach I was looking for.

The poor performing SQL was:

select c.* FROM customers c order by city asc, id asc offset 999989 rows FETCH NEXT 11 ROWS ONLY;

When I combine the prior answers and the website suggestions together, I came up with this SQL:

   SELECT top(10) * FROM ( SELECT * FROM customers   WHERE City <= 'City-99'
         AND NOT (City = 'City-99'  AND ID >= 999999 )) t  ORDER BY City DESC, ID DESC

The SQL Server profiler view was even more black and white.

                CPU / Reads / Duration
Offset / Limit 2049  22163    553
Cursor         1626  22163    274

So, while I didn't reduce the reads between the statements, the CPU and duration were sped up significantly.

I was able to sort by any column, use the combination key of the sort column and the ID column, and get pretty good performance without indexing any of the columns.

Speaking of indexing columns, I went back and put an index on the City column to see if it would make a difference:

                CPU / Reads / Duration
Offset / Limit 2156  22163    586
Cursor            0     48    48

Running the same SQL above, the improvements become even more drastic.

And I recognize that proper database hygiene would be to know ahead of time what columns to index, but I'm releasing systems that aren't aware of how the customers will use them initially, which is why I was pushing for something better than Limit / offset. My hope is that we capture the high frequency of user sorting events and then recommend an index if one doesn't exist for the primarily used columns the customer sorts by.