query – how to optimize queries in magento 1.9 with lots of attributes (over 500)

I have a website running Magento 1.9 which is flooding mysql with slow queries like this

SELECT COUNT(DISTINCT e.entity_id) FROM `catalog_product_entity` AS `e`
 INNER JOIN `catalog_product_index_price` AS `price_index` ON price_index.entity_id = e.entity_id AND price_index.website_id = '1' AND price_index.customer_group_id = 0
 INNER JOIN `catalog_category_product_index` AS `cat_index` ON cat_index.product_id=e.entity_id AND cat_index.store_id='1' AND cat_index.visibility IN(3, 4) AND cat_index.category_id = '2' WHERE (`e`.`entity_id` IN(78661, 78664, 78668, 78659, 78660, 78658, 78657, 78656, ...about 1000 more ids)

I’m assuming this has to do with caregory and layered navigation so I disabled the layered navigation counts globally. It helped mitigate the problem but it’s still not quite solved so I want to takle it at the source.

Could someone help me understand when these queries are run and why this is happening?

Another example

SELECT `trofodosia_boyrtsas_idx`.`value`, COUNT(trofodosia_boyrtsas_idx.entity_id) AS `count` FROM `catalog_product_entity` AS `e`
 INNER JOIN `catalog_product_index_price` AS `price_index` ON price_index.entity_id = e.entity_id AND price_index.website_id = '1' AND price_index.customer_group_id = 0
 INNER JOIN `catalog_category_product_index` AS `cat_index` ON cat_index.product_id=e.entity_id AND cat_index.store_id='1' AND cat_index.visibility IN(3, 4) AND cat_index.category_id = '2'
 INNER JOIN `catalog_product_index_eav` AS `trofodosia_boyrtsas_idx` ON trofodosia_boyrtsas_idx.entity_id = e.entity_id AND trofodosia_boyrtsas_idx.attribute_id = '321' AND trofodosia_boyrtsas_idx.store_id = '1' WHERE (`e`.`entity_id` IN(78661, 78664, ...more ids)
GROUP BY `trofodosia_boyrtsas_idx`

They seem to be fairly common in all magento 1.9 running instances and connected to the layered navigation and pagination.

Is there something I could change on mysql server to improve this?
Is this behaviour something documented in Magento 1.9?

PS: Due to the amount of attributes I can’t enable flat catalog because it hits the max row limit in mysql.