EXPLAIN EXTENDED

CREATE TABLE filler (
        id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE dev_product (
        id INT NOT NULL PRIMARY KEY,
        name VARCHAR(30) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE market_product (
        id INT NOT NULL PRIMARY KEY,
        name VARCHAR(30) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE dev_product_comp (
        prodID INT NOT NULL,
        substID INT NOT NULL,
        PRIMARY KEY (prodID, substID)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE market_product_comp (
        prodID INT NOT NULL,
        substID INT NOT NULL,
        PRIMARY KEY (prodID, substID)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
        DECLARE _cnt INT;
        SET _cnt = 1;
        WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(500);
COMMIT;

INSERT
INTO    dev_product
SELECT  id, CONCAT('Dev product ', id)
FROM    filler;

INSERT
INTO    market_product
SELECT  id, CONCAT('Market product ', id)
FROM    filler;

INSERT
INTO    dev_product_comp
SELECT  *
FROM    (
        SELECT  d.id AS prodID, s.id AS substID
        FROM    dev_product d
        CROSS JOIN
                (
                SELECT  id
                FROM    filler
                ORDER BY
                        id
                LIMIT 15
                ) s
        ) q
WHERE   RAND(20090908) < 0.5;

INSERT
INTO    market_product_comp
SELECT  *
FROM    (
        SELECT  m.id AS prodID, s.id AS substID
        FROM    market_product m
        CROSS JOIN
                (
                SELECT  id
                FROM    filler
                ORDER BY
                        id
                LIMIT 15
                ) s
        ) q
WHERE   RAND(20090908 << 1) < 0.5;
&#91;/sourcecode&#93;
</div>

There are <strong>500</strong> products both on market and in development, each having a random number of components (<strong>7.5</strong> in average).

Since <strong>MySQL</strong> lacks <code>FULL OUTER JOIN</code>, we need to mimic it.

We could use <code>LEFT JOIN</code>'s in a <code>UNION</code>, however, <strong>MySQL</strong> has a nasty <a href="http://bugs.mysql.com/bug.php?id=35455">bug</a> (introduced somewhere on its way to version <strong>5</strong>): it does not allow using outer query expression in <code>ON</code> clauses of correlated subqueries.

To work around this, we could use a self join inside each correlated subquery which would allow us to use <strong>WHERE</strong> clause instead. However, even a join on <code>id</code> will degrade the query performance.

That's why we'll have to rewrite this query as a bunch of nested <code>EXISTS</code> statements. This will be less readable, however, more efficient.

We need to find all development products for which exists a market product that shares the component set. This means that for the given development/market pair there is neither a development product component not found in a market product nor a market component not found in development product.

Here's this query in <strong>SQL</strong>:


SELECT  *
FROM    dev_product dp
WHERE   EXISTS
        (
        SELECT  NULL
        FROM    market_product mp
        WHERE   NOT EXISTS
                (
                SELECT  NULL
                FROM    dev_product_comp dpc
                WHERE   dpc.prodID = dp.id
                        AND NOT EXISTS
                        (
                        SELECT  NULL
                        FROM    market_product_comp mpc
                        WHERE   mpc.prodID = mp.id
                                AND mpc.substID = dpc.substID
                        )
                )
                AND NOT EXISTS
                (
                SELECT  NULL
                FROM    market_product_comp mpc
                WHERE   mpc.prodID = mp.id
                        AND NOT EXISTS
                        (
                        SELECT  NULL
                        FROM    dev_product_comp dpc
                        WHERE   dpc.prodID = dp.id
                                AND dpc.substID = mpc.substID
                        )
                )

        )

And here are the results:

Show results and execution plan

This query does almost what it says: it takes each dev/market pair and checks the missing components in both ways.

EXISTS conditions return as soon as anything is found, that's why in fact not every pair is checked.

However, misses are very probable (the query returns only 6 products of 500 possible), so this query actually shows the worst case.

Nevertheless, it completes in only 5 seconds which is quite fast for 250,000 pairs.

In case of more probable hits, the query will complete even sooner.