This will probably require adding a page_sortkey column to the 'page' table (akin to cl_sortkey in 'categorylinks'), and maybe another one if we wanted to sort by both the real title and the DEFAULTSORT, as well as adding/updating indexes.

How viable would doing this be? Is there any less painful reasonably performant way?

Changed the summary to be more general as the issue involves the following special pages:

Special:AllPAges
Special:PrefixIndex
Special:Uncategorized*
Special:Unused*
Special:OrphanPages
Special:DeadEndPages
Special:WithoutInterwiki
Special:ListRedirects

Special:CategoryTree (or should that one honour the sortkey order?)

Also to consider:

Should the special pages just use the collation given by the system or should they also honour overrides by {{DEFAULTSORT:}}?

(In reply to Bartosz Dziewoński from comment #1)

This will probably require adding a page_sortkey column to the 'page' table
(akin to cl_sortkey in 'categorylinks'), and maybe another one if we wanted
to sort by both the real title and the DEFAULTSORT, as well as
adding/updating indexes.

We can't actually do that if we ever want to support using multiple collations on one wiki (bug 44667).

(In reply to Bartosz Dziewoński from comment #4)

(In reply to Bartosz Dziewoński from comment #1)

This will probably require adding a page_sortkey column to the 'page' table
(akin to cl_sortkey in 'categorylinks'), and maybe another one if we wanted
to sort by both the real title and the DEFAULTSORT, as well as
adding/updating indexes.

We can't actually do that if we ever want to support using multiple
collations on one wiki (bug 44667).

probably it's doable now by abusing categorylinks, using categorylinks rows with cl_category set to empty. not sure about performance consideration though.

Some other issues, missing categorylinks rows will result in incomplete page list. I guess people will tolerate it less than incomplete categories.

I talked about this with Reedy yesterday (mostly I was blabbering silly ideas and he was cringing) and we came up with this too, but having to fill the other fields with gibberish would be a bit silly. It might be the simplest thing that'll work, though.

We also came up with maybe just creating a separate table just for storing generated sortkeys and what they apply to (e.g. a page title, a page defaultsort, a category link) and using JOIN queries. Not sure about the performance of this.