Q:

How to optimize correlated subquery?

I have this query that runs against MySQL:
SELECT DISTINCT tp.parts_group as PartsGroup, tpf.code as FeatureCode, CONVERT(tpf.market_id, char) as MarketID
FROM jpt_product_feature tpf
INNER JOIN jpt_product tp
ON tpf.product_id = tp.id
INNER JOIN jpt_product_model tpm
ON tp.model_id = tpm.id
JOIN ModelImport mi
ON tpm.Code = mi.ModelCode
WHERE NOT EXISTS (
      SELECT 1 
      FROM FeatureSequence fs
      WHERE tp.parts_group = fs.PartsGroup
      AND tpf.code = fs.FeatureCode
      AND (tpf.market_id = fs.MarketID or tpf.market_id is null)
) 
ORDER BY PartsGroup, FeatureCode, MarketID

It runs in 38 seconds on my PC, which is fine given the large numbers of rows across multiple tables. But running on VMs with less horsepower, this query runs for about 2 hours and then blows up with a FATAL ERROR.
Here are the indexes I have:
CREATE INDEX idxFeatureSequencePartsGroup ON FeatureSequence (PartsGroup); 
CREATE INDEX idxToyProductPartsGroup ON jpt_product (parts_group); 
CREATE INDEX idxToyProductFeature ON jpt_product_feature (code);
CREATE INDEX idxFeatureSequenceFeatureCode ON FeatureSequence (FeatureCode); 
CREATE INDEX idxToyProductFeatureMarketID ON jpt_product_feature (market_id);
CREATE INDEX idxFeatureSequenceMarketID ON FeatureSequence (MarketID); 

We're working on beefing up the VMs, but in the meantime, what can I do to speed up this query, optimize it, make it more efficient? I'm even open to exotic/inelegant approaches if it can dramatically speed up the query. Or if I'm missing indexes you think I should have, that could be an easy solution.

A:

Correlated queries tend to be much less efficient than a non-correlated alternative (when such an alternative is possible). In this case, I would try this alternative:
SELECT DISTINCT tp.parts_group as PartsGroup, tpf.code as FeatureCode, CONVERT(tpf.market_id, char) as MarketID
FROM jpt_product_feature tpf
INNER JOIN jpt_product tp ON tpf.product_id = tp.id
INNER JOIN jpt_product_model tpm ON tp.model_id = tpm.id
INNER JOIN ModelImport mi ON tpm.Code = mi.ModelCode
LEFT JOIN (
      SELECT DISTINCT 1 AS matchCheck
         , fs.PartsGroup AS fsPartsGroup
         , fs.FeatureCode AS fsFeatureCode
         , fs.MarketID AS fsMarketID
      FROM FeatureSequence fs
) AS fs ON tp.parts_group = fs.fsPartsGroup
      AND tpf.code = fs.fsFeatureCode
      AND (tpf.market_id = fs.fsMarketID OR tpf.market_id is null)
WHERE fs.matchCheck IS NULL
ORDER BY PartsGroup, FeatureCode, MarketID
;

Without knowing the specifics of the data distribution it is hard to tell if this would be faster (there are some situations where correlated subqueries are the best choice); but this is the first thing I would try. If FeatureSequence is relative large compared to the other tables involved, the correlated query may still be better (many small hits against a large table vs a single large hit).

