SELECT Parts.*, Image.type, Image.width, Image.height,
(SELECT name FROM Location_State WHERE id = Parts.state_id) AS state,
(SELECT name FROM Location_Region WHERE id = Parts.region_id) AS region,
(SELECT start_date FROM Promotion WHERE id = Parts.promotion_id) AS promotion_start_date,
(SELECT end_date FROM Promotion WHERE id = Parts.promotion_id) AS promotion_end_date
FROM ( SELECT parts_id FROM Parts_Category WHERE Parts_Category.category_id = '40'
UNION SELECT parts_id FROM Parts_Category WHERE Parts_Category.main_category_id = '40') cid
LEFT JOIN Image ON Parts.image_id = Image.id
JOIN Parts ON Parts.id = cid.parts_id AND Parts.status = 'A'
ORDER BY Parts.level DESC, Parts.warehouse DESC, Parts.updated DESC LIMIT 0, 15

(status, level, warehouse, updated)

SELECT  p.*, i.type, i.width, i.height,
        (SELECT name FROM Location_State WHERE id = p.state_id) AS state,
        (SELECT name FROM Location_Region WHERE id = p.region_id) AS region,
        (SELECT start_date FROM Promotion WHERE id = p.promotion_id) AS promotion_start_date,
        (SELECT end_date FROM Promotion WHERE id = p.promotion_id) AS promotion_end_date
FROM    parts p
LEFT JOIN
        image i
ON      i.id = p.image_id
WHERE   EXISTS (
        SELECT  NULL
        FROM    Parts_Category pc
        WHERE   pc.category_id = '40'
                AND pc.parts_id = p.id
        UNION ALL
        SELECT  NULL
        FROM    Parts_Category pc
        WHERE   pc.main_category_id = '40'
                AND pc.parts_id = p.id
        )
        AND p.status = 'A'
ORDER BY
        p.status DESC, p.level DESC, p.warehouse DESC, p.updated DESC
LIMIT   15

parts (status, level, warehouse, updated) -- this one you have
parts_category (category_id, parts_id)
parts_category (main_category_id, parts_id)

DROP TABLE IF EXISTS `test`.`image`;
CREATE TABLE  `test`.`image` (
  `id` int(11) NOT NULL,
  `type` int(11) NOT NULL,
  `width` int(11) NOT NULL,
  `height` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DROP TABLE IF EXISTS `test`.`location_region`;
CREATE TABLE  `test`.`location_region` (
  `id` int(11) NOT NULL,
  `name` varchar(20) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DROP TABLE IF EXISTS `test`.`location_state`;
CREATE TABLE  `test`.`location_state` (
  `id` int(11) NOT NULL,
  `name` varchar(20) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DROP TABLE IF EXISTS `test`.`parts`;
CREATE TABLE  `test`.`parts` (
  `id` int(11) NOT NULL,
  `status` char(1) NOT NULL,
  `level` int(11) NOT NULL,
  `warehouse` int(11) NOT NULL,
  `updated` int(11) NOT NULL,
  `state_id` int(11) NOT NULL,
  `region_id` int(11) NOT NULL,
  `promotion_id` int(11) NOT NULL,
  `image_id` int(11) NOT NULL DEFAULT '1',
  PRIMARY KEY (`id`),
  KEY `status` (`status`,`level`,`warehouse`,`updated`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DROP TABLE IF EXISTS `test`.`parts_category`;
CREATE TABLE  `test`.`parts_category` (
  `id` int(11) NOT NULL,
  `parts_id` int(11) NOT NULL,
  `category_id` int(11) NOT NULL,
  `main_category_id` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `ix_pc_cat_parts` (`category_id`,`parts_id`),
  KEY `ix_pc_main_parts` (`main_category_id`,`parts_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DROP TABLE IF EXISTS `test`.`promotion`;
CREATE TABLE  `test`.`promotion` (
  `id` int(11) NOT NULL,
  `start_date` datetime NOT NULL,
  `end_date` datetime NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT
INTO    parts
SELECT  id,
        CASE WHEN RAND() < 0.1 THEN 'A' ELSE 'B' END,
        RAND() * 100,
        RAND() * 100,
        RAND() * 100,
        RAND() * 50,
        RAND() * 50,
        RAND() * 50,
        RAND() * 50
FROM    t_source
LIMIT 500000;
INSERT
INTO    parts_category
SELECT  id,
        id,
        RAND() * 100,
        RAND() * 100
FROM    t_source
LIMIT 500000;
INSERT
INTO    location_state
SELECT  id, CONCAT('State ', id)
FROM    t_source
LIMIT 1000;
INSERT
INTO    location_region
SELECT  id, CONCAT('Region ', id)
FROM    t_source
LIMIT 1000;
INSERT
INTO    promotion
SELECT  id,
        '2009-07-22' - INTERVAL RAND() * 5 - 20 DAY,
        '2009-07-22' - INTERVAL RAND() * 5 DAY
FROM    t_source
LIMIT 1000;

1, 'PRIMARY', 'p', 'ref', 'status', 'status', '3', 'const', 107408, 'Using where'
1, 'PRIMARY', 'i', 'eq_ref', 'PRIMARY', 'PRIMARY', '4', 'test.p.image_id', 1, ''
6, 'DEPENDENT SUBQUERY', 'pc', 'ref', 'ix_pc_cat_parts', 'ix_pc_cat_parts', '8', 'const,test.p.id', 1, 'Using index'
7, 'DEPENDENT UNION', 'pc', 'ref', 'ix_pc_main_parts', 'ix_pc_main_parts', '8', 'const,test.p.id', 1, 'Using index'
, 'UNION RESULT', '<union6,7>', 'ALL', '', '', '', '', , ''
5, 'DEPENDENT SUBQUERY', 'Promotion', 'eq_ref', 'PRIMARY', 'PRIMARY', '4', 'test.p.promotion_id', 1, ''
4, 'DEPENDENT SUBQUERY', 'Promotion', 'eq_ref', 'PRIMARY', 'PRIMARY', '4', 'test.p.promotion_id', 1, ''
3, 'DEPENDENT SUBQUERY', 'Location_Region', 'eq_ref', 'PRIMARY', 'PRIMARY', '4', 'test.p.region_id', 1, ''
2, 'DEPENDENT SUBQUERY', 'Location_State', 'eq_ref', 'PRIMARY', 'PRIMARY', '4', 'test.p.state_id', 1, ''

SELECT
  Parts.*,
  Image.type, Image.width, Image.height,
  Location_State.name AS state,
  Location_Region.name AS region,
  Promotion.start_date AS promotion_start_date,
  Promotion.end_date AS promotion_end_date
FROM Parts
LEFT JOIN Image ON Parts.image_id = Image.id
LEFT JOIN Location_State ON Parts.state_id = Location_State.id
LEFT JOIN Location_Region ON Parts.state_id = Location_Region.id
LEFT JOIN Promotion ON Parts.promotion_id = Promotion.id
INNER JOIN Parts_Category ON (Parts_Category.category_id = 40 OR Parts_Category.main_category_id = 40)
WHERE Parts.status = 'A'
GROUP BY Parts.id
ORDER BY Parts.level DESC, Parts.warehouse DESC, Parts.updated DESC LIMIT 0, 15

SHOW CREATE TABLE Parts;

EXPLAIN <my query here>G