-- Create tables
CREATE TABLE a (id INTEGER AUTO_INCREMENT NOT NULL PRIMARY KEY, b_id INTEGER NOT NULL) ENGINE=InnoDB;
CREATE TABLE b (id INTEGER AUTO_INCREMENT NOT NULL PRIMARY KEY) ENGINE=InnoDB;
CREATE TABLE c (id INTEGER AUTO_INCREMENT NOT NULL PRIMARY KEY, b_id INTEGER NOT NULL, val VARCHAR(255) NOT NULL) ENGINE=InnoDB;
CREATE TABLE d (a_id INTEGER NOT NULL, c_id INTEGER NOT NULL, val VARCHAR(255) NOT NULL) ENGINE=InnoDB;

-- Fill them with a few records
INSERT INTO a (b_id) VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1);
INSERT INTO b (id) VALUES (NULL),(NULL);
INSERT INTO c (b_id,val) VALUES (1,'c1');
INSERT INTO d (a_id) VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
UPDATE d SET c_id=1, val='d1';

-- This EXPLAIN query takes 94 seconds on my test machine, many many hours with a larger dataset 
-- The subqueries' inner join to B is redundant and eliminating it gets rid of the problem.
-- 
-- Time taken by EXPLAIN, depending on the number of records in B:
-- 1: 0.24s
-- 2: 1m34s
-- 3: 14s
-- 4: 10s
-- 5: 12s
-- 6: 14s
EXPLAIN SELECT a.`id` FROM a WHERE
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c1" AND (d.`val`="d1"))) AND
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c2" AND (d.`val`="d2"))) AND
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c3" AND (d.`val`="d3"))) AND
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c4" AND (d.`val`="d4"))) AND
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c5" AND (d.`val`="d5"))) AND
(a.`id` IN (SELECT a.`id` FROM a INNER JOIN b ON a.`b_id`=b.`id` INNER JOIN c ON a.`b_id`=c.`b_id` INNER JOIN d ON c.`id`=d.`c_id` AND a.`id`=d.`a_id` WHERE c.`val`="c6" AND (d.`val`="d6")));
