MySQL order and group by varchar performance

Question

I need to find a way to increase performance on order and group by varchar fields.

Now i can use a secondary table for artist and format to group, but that is nothing compared to the problem caused by the title field and ordering by artist and title alphabetically.

I was tinkering with taking the first two characters from each and adding them to a table and using those id's to order numerically but in time new artists and new titles with different combinations of characters will come as some artist names can start with anything, so can the song title and in that case everything goes out the window. I don't want to have to write a monster of a trigger that each time it inserts and new two chars combination has to start changing the ids of everything to reset the order, this would be a huge effort and might caus eeven more issues.

Can anyone suggest a better approach at this issue?

Update

So I made an artists table and two nice triggers to handle everything. I made a cron to check the artists are in alphabetical order when new ones are added and make the necessary updates.

I gained 0.24 seconds and am left with 2.98 to shave off.

As it looks right now the issue is the title ORDER and GROUP, mostly GROUP, order seems to consume only 20% of the time.

Query

SELECT *
  FROM `records`
  WHERE `deleted` = 0 AND `hidden` = 0
  GROUP BY `artist_id`, `title`, `format_id`
  ORDER BY `artist_id` ASC, `title` ASC
  LIMIT 0, 100;

Schema

`deleted` tinyint 1 unsigned key
`hidden` tinyint 1 unsigned key
`format_id` tinyint 2 unsigned key
`artist_id` int 11 unsigned key
`title` varchar 255 key

Answer 1

Create new table

artistID int
artist varchar

and replace artist in your table with artistID.

Then join tables by id and group by artistID...

database normalization is your friend :)