What is a suitable index for this query?
Using SQL Server 2012 (hopefully there is an equivalent in MySQL):

CREATE TABLE dbo.site_map_template 
(
  row_mod datetime NULL,
  row_create datetime NULL,
  template_name varchar(50) COLLATE Latin1_General_BIN2 NULL,
  alias_to varchar(100) COLLATE Latin1_General_BIN2 NULL,
  package varchar(50) COLLATE Latin1_General_BIN2 NULL,
  fake_uri varchar(255) COLLATE Latin1_General_BIN2 NULL,
  precedence integer NULL,
  parameters1 varchar(255) COLLATE Latin1_General_BIN2 NULL,
  parameters2 varchar(255) COLLATE Latin1_General_BIN2 NULL,
  parameters3 varchar(255) COLLATE Latin1_General_BIN2 NULL
);


A good clustered index for this query is:

CREATE UNIQUE CLUSTERED INDEX PK__site_map_template_precedence_fake_uri
ON dbo.site_map_template (precedence, fake_uri DESC);


Or, a nonclustered index:

CREATE NONCLUSTERED INDEX nc1
ON dbo.site_map_template
    (
    precedence,
    fake_uri DESC
    )
INCLUDE
    (
    alias_to,
    parameters1,
    parameters2,
    parameters3,
    template_name
    );


The query (again, in SQL Server syntax) is:

SELECT
    alias_to, 
    fake_uri,
    [parameters] = CONCAT(parameters1, parameters2, parameters3),
    precedence, 
    template_name 
FROM dbo.site_map_template
ORDER BY
    precedence, 
    fake_uri DESC;


And the execution plan is a simple scan of the index:



Or, using the nonclustered index:



The important thing in both cases is that each index covers all the columns needed by the query, and the index keys are precedence ASC and fake_uri DESC. Without the descending second key, a full sort would be required, and this is likely the cause of your slow performance.