> I saw the fact that the indices help.

This is impossible. I guess you have

scan(table) + sort(records)

slower than

scan(table) + sort(keys) + build_index + walk(part_of_index) +
lookup_table_by_dbkey

just because of second query worked with data cached by
first query

> (After further investigations I saw that the gain is bigger if the table
> is wider).

This is known weak of our sorting algoritm. In-memory we do move
of pointers but on disk we move whole records. You can learn sort.cpp
to be sure

> So, perhaps, if you'll sort
> only the keys (not the entire records) the things will be faster.

And this is a way to improve our sorting algoritm

Regards,
Vlad