Mysql – How to improve query to take less than 4s on ~10M records

I have to select id_category and its name, description and link_rewrite where number_products > 0. However it selects 1000+ rows where only 10-20 of them have number_products > 0, others are 0.

It needs like 3-4 seconds, how could I make it faster? My goal is to select only categories those have active products so whenever user selects a car I would like to show him few categories where he could find some products. Maybe the way I am doing it is completely wrong, but tried many ways to play with the query and could now achieve better results.

Please write in comments if you need more informations.

Query:

SELECT c.id_parent, c.id_category, cl.name, cl.description, cl.link_rewrite,
                (SELECT COUNT(DISTINCT cp.`id_product`)
                    FROM `ps_category_product` cp
                        INNER JOIN `ps_m4_car_type_product` ctp ON (cp.`id_product` = ctp.`id_product` AND ctp.`id_car_type` = 791)
                        INNER JOIN `ps_product` p ON (cp.`id_product` = p.`id_product` AND p.`active` = 1)
                    WHERE c.`id_category` = cp.`id_category`
                ) AS number_products
                FROM `ps_category` c
                LEFT JOIN `ps_category_lang` cl ON (c.`id_category` = cl.`id_category` AND cl.`id_lang` = 4)
                LEFT JOIN `ps_category_group` cg ON (cg.`id_category` = c.`id_category` AND cg.`id_group` = 4)
                WHERE c.`active` = 1
                AND c.`level_depth` <= 4

EXPLAIN (click for full size):

Tables:

ps_category_product 791K rows
ps_m4_car_type_product 8.5M rows
ps_product 300K rows
ps_category 1.6K rows
ps_category_lang 3.7K rows
ps_category_group 6.3K rows

Mysql version: 5.1.56

UPDATE:

ps_category_product

CREATE TABLE IF NOT EXISTS `ps_category_product` (
  `id_category` int(10) unsigned NOT NULL,
  `id_product` int(10) unsigned NOT NULL,
  `position` int(10) unsigned NOT NULL DEFAULT '0',
  KEY `category_product_index` (`id_category`,`id_product`),
  KEY `id_category` (`id_category`),
  KEY `idx_id_product` (`id_product`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

ps_m4_car_type_product

CREATE TABLE IF NOT EXISTS `ps_m4_car_type_product` (
  `id_car_type` int(10) unsigned NOT NULL,
  `id_product` int(10) unsigned NOT NULL,
  `info` text,
  KEY `id_product` (`id_product`),
  KEY `id_car_type` (`id_car_type`,`id_product`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

ps_product

CREATE TABLE IF NOT EXISTS `ps_product` (
  `id_product` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `id_supplier` int(10) unsigned DEFAULT NULL,
  `id_manufacturer` int(10) unsigned DEFAULT NULL,
  `id_tax_rules_group` int(10) unsigned NOT NULL,
  `id_category_default` int(10) unsigned DEFAULT NULL,
  `id_color_default` int(10) unsigned DEFAULT NULL,
  `on_sale` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `online_only` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `ean13` varchar(13) DEFAULT NULL,
  `upc` varchar(12) DEFAULT NULL,
  `ecotax` decimal(17,6) NOT NULL DEFAULT '0.000000',
  `quantity` int(10) NOT NULL DEFAULT '0',
  `minimal_quantity` int(10) unsigned NOT NULL DEFAULT '1',
  `price` decimal(20,6) NOT NULL DEFAULT '0.000000',
  `wholesale_price` decimal(20,6) NOT NULL DEFAULT '0.000000',
  `unity` varchar(255) DEFAULT NULL,
  `unit_price_ratio` decimal(20,6) NOT NULL DEFAULT '0.000000',
  `additional_shipping_cost` decimal(20,2) NOT NULL DEFAULT '0.00',
  `reference` varchar(32) DEFAULT NULL,
  `supplier_reference` varchar(255) DEFAULT NULL,
  `location` varchar(64) DEFAULT NULL,
  `width` float NOT NULL DEFAULT '0',
  `height` float NOT NULL DEFAULT '0',
  `depth` float NOT NULL DEFAULT '0',
  `weight` float NOT NULL DEFAULT '0',
  `out_of_stock` int(10) unsigned NOT NULL DEFAULT '2',
  `quantity_discount` tinyint(1) DEFAULT '0',
  `customizable` tinyint(2) NOT NULL DEFAULT '0',
  `uploadable_files` tinyint(4) NOT NULL DEFAULT '0',
  `text_fields` tinyint(4) NOT NULL DEFAULT '0',
  `active` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `available_for_order` tinyint(1) NOT NULL DEFAULT '1',
  `condition` enum('new','used','refurbished') NOT NULL DEFAULT 'new',
  `show_price` tinyint(1) NOT NULL DEFAULT '1',
  `indexed` tinyint(1) NOT NULL DEFAULT '0',
  `cache_is_pack` tinyint(1) NOT NULL DEFAULT '0',
  `cache_has_attachments` tinyint(1) NOT NULL DEFAULT '0',
  `cache_default_attribute` int(10) unsigned DEFAULT NULL,
  `date_add` datetime NOT NULL,
  `date_upd` datetime NOT NULL,
  PRIMARY KEY (`id_product`),
  KEY `product_supplier` (`id_supplier`),
  KEY `product_manufacturer` (`id_manufacturer`),
  KEY `id_category_default` (`id_category_default`),
  KEY `id_color_default` (`id_color_default`),
  KEY `date_add` (`date_add`),
  KEY `location` (`location`),
  KEY `reference` (`reference`),
  KEY `on_sale` (`on_sale`) USING BTREE
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=10004719 ;

ps_category

CREATE TABLE IF NOT EXISTS `ps_category` (
  `id_category` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `id_parent` int(10) unsigned NOT NULL,
  `level_depth` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `nleft` int(10) unsigned NOT NULL DEFAULT '0',
  `nright` int(10) unsigned NOT NULL DEFAULT '0',
  `active` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `date_add` datetime NOT NULL,
  `date_upd` datetime NOT NULL,
  `position` int(10) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`id_category`),
  KEY `category_parent` (`id_parent`),
  KEY `nleftright` (`nleft`,`nright`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=1000489 ;

ps_category_lang

CREATE TABLE IF NOT EXISTS `ps_category_lang` (
  `id_category` int(10) unsigned NOT NULL,
  `id_lang` int(10) unsigned NOT NULL,
  `name` varchar(128) NOT NULL,
  `description` text,
  `link_rewrite` varchar(128) NOT NULL,
  `meta_title` varchar(128) DEFAULT NULL,
  `meta_keywords` varchar(255) DEFAULT NULL,
  `meta_description` varchar(255) DEFAULT NULL,
  UNIQUE KEY `category_lang_index` (`id_category`,`id_lang`),
  KEY `category_name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

ps_category_group

CREATE TABLE IF NOT EXISTS `ps_category_group` (
  `id_category` int(10) unsigned NOT NULL,
  `id_group` int(10) unsigned NOT NULL,
  UNIQUE KEY `category_group_index` (`id_category`,`id_group`),
  KEY `id_category` (`id_category`),
  KEY `id_group` (`id_group`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;