I found a bit better situation.

DECLARE @intPageNumber INT = 1, @intPageSize INT = 20;

WITH SQLPaging

AS

(

SELECT TOP(@intPageNumber * @intPageSize) ROW_NUMBER() OVER (ORDER BY vaa.CreatedDate) AS RowNum,

vaa.AdID, vaa.AdTitle, vaa.CityID, vaa.AdFor, vaa.AdCondition,

vaa.AdExpPrice, vaa.CreatedDate, vaa.ModifiedDate, vaa.AdUID

FROM Catalogue.vwAvailableActiveAds vaa

WHERE vaa.CategoryID = 1 AND vaa.CountryCode = 'GB' AND vaa.CreatedDate > DATEADD(dd, -90, GETUTCDATE())

AND vaa.StateID = 1737 AND vaa.CityID = 86

)

SELECT * FROM SQLPaging

WHERE RowNum > (@intPageSize * (@intPageNumber - 1))

If I use CreatedDate in place of AdID in Row_Number order by clause, then it uses the index seek till Created date. After that it looks for the predicate StateID & CityID.

I can not move the createddate before stateid & cityid becaue stateid & cityid are optional parameters in dynamic query & categoryid, country & created date are fixed conditions.