"ORDER BY" without large table scans and filesort

[Andreas]

OK, this seems to be impossible but I thought I could ask anyway, maybe I overlooked smth. and somebody has the 1.000.000 $ answer

Let's say I got a table with several tenthousand records; the primary index as an auto-increment integer.
Now I want the last record.
I could do
[sql]SELECT * FROM table ORDER BY id DESC LIMIT 1[/sql]

But this causes large table scans ...