The following query is taking more than 20 seconds to execute on a table with around half million rows:

Code:
    SELECT images.id, images.user_id, images_locale.filename, extension, size, width, height, views, batch, source, status, images.created_at, images.category_id, title, short_description, long_description, alternate, slugs.name as slug, images_locale.slug_id, path_cache AS category_path, full_name, users.username
    FROM images
    JOIN images_locale ON images_locale.image_id = images.id JOIN slugs ON images_locale.slug_id = slugs.id JOIN categories_locale ON images.category_id = categories_locale.category_id JOIN users ON users.id = images.user_id
    WHERE slugs.name = 'THE_SLUG_HERE' AND images.status = '1' AND images_locale.locale_id = 1 AND categories_locale.locale_id = 1
    LIMIT 1
Now when I remove `slugs.name = 'THE_SLUG_HERE' AND` I get the result in a few milliseconds.

This is my slug table:

Code:
    CREATE TABLE `slugs` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `name` varchar(250) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL DEFAULT '',
      `type` tinyint(4) NOT NULL,
      `locale_id` smallint(6) NOT NULL,
      PRIMARY KEY (`id`),
      UNIQUE KEY `name` (`name`)
    ) ENGINE=InnoDB AUTO_INCREMENT=3611900 DEFAULT CHARSET=utf8;
I tried to `CREATE INDEX test_speed ON slugs(name)` but it didn't speed up things.

Here's the result of EXPLAIN: http://i.stack.imgur.com/DnUzd.png

Please help.