Fix skewed SQL Server plan in C/AL

NAV 2009R2

I have a moderately large table with an indexed field that is tremendously skewed toward one value. NAV, of course, tells SQL Server to optimize for unknown, so SQL Server is choosing a hideously bad plan for the particular situation at hand.

NAV Psuedocode:

Table.SetCurrentKey(Status, Type);
Table.SetRange(Status, Table.Status::New);
Table.SetRange(Type, 'TYP1');
If Table.FindFirst Then Begin
<do stuff>

The query NAV is issuing looks something like:

(@P1 int,@P2 varchar(4))
SELECT TOP 1 *
FROM <db>."dbo".<company>$<Table> WITH (UPDLOCK, ROWLOCK)
WHERE (("Status"=@P1)) AND (("Type"=@P2))
ORDER BY "Status","Type","Filename","Line No_"
OPTION (OPTIMIZE FOR UNKNOWN)

Filename and Line No_ are the PK, of course, so NAV adds them to the actual key it generates, and the order by clause.

Most of the data in the table does not fit the filter. In fact, there were 5 rows out of about 10 million when I checked it earlier. However, SQL Server is choosing to to a full clustered index scan to find those 5 rows, which is generating half a million unnecessary reads every time the code runs (which is often).

Edit: I guess I should have noted that the other 10 million rows mostly have a status of "Completed"


If I run the above query in SQL Server changing to (OPTIMIZE for (@P1=0), the query acts more as I would expect.

I did refresh the statistics on the table (no change), force a new plan (no change), and check the results with no optimize clause at all (no change).


So, since I'm pretty sure there isn't a way to control the OPTIMIZE FOR clause in NAV 2009R2, what are my other options? Thoughts I had:
1) Partition the table, so the history rows are in a different partition (which seems kind of overkill, and potentially confusing for NAV when it tries to do table changes)
2) Create a view for a linked table (but I don't think "optimize for" can go on a view, and even if it could, I suspect the optimize for unknown from NAV might override it)
3) "Manually" partition the table by moving history off to another table (which is more programming than I wanted to do, and will generate lots of extra disk activity that I don't want)

Other thoughts?