SQL Server query slow when paginated

I am seeing some strange behaviour with the following T-SQL query in SQL Server 2012:

SELECT Id 
FROM dbo.Person 
WHERE CONTAINS(Name, '"John" AND "Smith"')
ORDER BY Name

Executing this query alone gives me about 1,300 results in less than two seconds (there's a fulltext index on Name)

However, when I change the query to this:

SELECT Id 
FROM dbo.Person 
WHERE CONTAINS(Name, '"John" AND "Smith"')
ORDER BY Name
OFFSET 0 rows
FETCH NEXT 10 ROWS ONLY

It takes more than 20 seconds to give me 10 results.

The following query is even worse:

SELECT Id 
FROM ( 
    SELECT ROW_NUMBER() OVER (ORDER BY Name) AS RowNum, Id 
    FROM dbo.Person
    WHERE CONTAINS(Name, '"John" AND "Smith"') ) AS RowConstrainedResult 
WHERE RowNum >= 0 AND RowNum < 11 
ORDER BY RowNum

It takes more than 1.5 minutes to complete!

Any ideas?
Slow plan

Fast plan

As you just want the TOP 10 ordered by name it thinks it will be quicker to work down the index on name in order and look to see if each row matches the CONTAINS(Name, '"John" AND "Smith"') ) predicate.

Presumably it takes many more rows to find the 10 matches required then it expects and this cardinality issue is compounded by the number of key lookups.

A quick hack to stop it using this plan would be to change the ORDER BY to ORDER BY Name + '' although using CONTAINSTABLE in conjunction with FORCE ORDER should also work.

StackExchange Database Administrators Q#20643, answer score: 7