LEFT JOIN'ы не нужны - их данные нигде не используются. Условия из WHERE можно попробовать перенести в ON.
SELECT COUNT(DISTINCT `p`.`id`)
FROM `product` AS `p`
JOIN `product_to_category` AS `p2c` ON `p`.`id` = `p2c`.`product_id`
AND `p`.`publish` = 1
AND `p2c`.`category_id` IN (917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950)
JOIN `city` AS `c` ON `c`.`id` = `p`.`city_id`
AND (`c`.`id` = 108 OR `c`.`parent_id` = 108)
Ну и правильные индексы, тут уже смотрите EXPLAIN/