title: Speed up self join in MYSQL
body: <p>I have a table of connections between different objects and I'm basically trying a graph traversal using self joins.
  My table is defined as:</p>
  
  <pre><code>CREATE TABLE `connections` (
    `id` bigint(20) NOT NULL AUTO_INCREMENT,
    `position` int(11) NOT NULL,
    `dId` bigint(20) NOT NULL,
    `sourceId` bigint(20) NOT NULL,
    `targetId` bigint(20) NOT NULL,
    `type` bigint(20) NOT NULL,
    `weight` float NOT NULL DEFAULT '1',
    `refId` bigint(20) NOT NULL,
    `ts` bigint(20) NOT NULL,
    PRIMARY KEY (`id`),
    KEY `sourcetype` (`type`,`sourceId`,`targetId`),
    KEY `targettype` (`type`,`targetId`,`sourceId`),
    KEY `complete` (`dId`,`sourceId`,`targetId`,`type`)
  ) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
  </code></pre>
  
  <p>The table contains about 3M entries (~1K of type 1, 1M of type 2, and 2M of type 3).</p>
  
  <p>The queries over 2 or 3 hops are actually quite fast (of course it takes a while to receive all the results), but getting the count of a query for 3 hops is terribly slow (> 30s).</p>
  
  <p>Here's the query (which returns 2M):</p>
  
  <pre><code>SELECT
    count(*)
  FROM
    `connections` AS `t0`
  JOIN
    `connections` AS `t1` ON `t1`.`targetid`=`t0`.`sourceid`
  JOIN
    `connections` AS `t2` ON `t2`.`targetid`=`t1`.`sourceid`
  WHERE
    `t2`.dId = 1
    AND
    `t2`.`sourceid` = 1
    AND
    `t2`.`type` = 1
    AND
    `t1`.`type` = 2
    AND
    `t0`.`type` = 3;
  </code></pre>
  
  <p>Here's the corresponding EXPLAIN:</p>
  
  <pre><code>id  select_type  table  type  possible_keys                   key         key_len  ref                         rows  Extra  
  1   SIMPLE       t2     ref   targettype,complete,sourcetype  complete    16       const,const                  100  Using where; Using index
  1   SIMPLE       t1     ref   targettype,sourcetype           targettype   8       const                       2964  Using where; Using index
  1   SIMPLE       t0     ref   targettype,sourcetype           sourcetype  16       const,travtest.t1.targetId  2964  Using index
  </code></pre>
  
  <p>Edit: Here is the EXPLAIN after adding and index to <code>type</code>:</p>
  
  <pre><code>id  select_type  table  type  possible_keys                        key         key_len  ref                         rows  Extra     
  1   SIMPLE       t2     ref   type,complete,sourcetype,targettype  complete    16       const,const                 100   Using where; Using index
  1   SIMPLE       t1     ref   type,sourcetype,targettype           sourcetype  16       const,travtest.t2.targetId    2   Using index
  1   SIMPLE       t0     ref   type,sourcetype,targettype           sourcetype  16       const,travtest.t1.targetId    2   Using index
  </code></pre>
  
  <p>Is there a way to improve this?</p>
  
  <p>2nd edit:</p>
  
  <pre><code>EXPLAN EXTENDED:
  +----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+
  | id | select_type | table | type | possible_keys                       | key        | key_len | ref                        | rows | filtered | Extra                    |
  +----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+
  |  1 | SIMPLE      | t2    | ref  | type,complete,sourcetype,targettype | complete   | 16      | const,const                |  100 |   100.00 | Using where; Using index |
  |  1 | SIMPLE      | t1    | ref  | type,sourcetype,targettype          | sourcetype | 16      | const,travtest.t2.targetId |    1 |   100.00 | Using index              |
  |  1 | SIMPLE      | t0    | ref  | type,sourcetype,targettype          | sourcetype | 16      | const,travtest.t1.targetId |    1 |   100.00 | Using index              |
  +----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+
  
  SHOW WARNINGS;
  +-------+------+--------------------------------------------------------------------------------------------+
  | Level | Code | Message                                                                                    |
  +-------+------+--------------------------------------------------------------------------------------------+
  | Note  | 1003 | /* select#1 */ select count(0) AS `count(*)` from `travtest`.`connections` `t0`            |
  |       |      | join `travtest`.`connections` `t1` join `travtest`.`connections` `t2`                      |
  |       |      | where ((`travtest`.`t0`.`sourceId` = `travtest`.`t1`.`targetId`) and                       |
  |       |      | (`travtest`.`t1`.`sourceId` = `travtest`.`t2`.`targetId`) and (`travtest`.`t0`.`type` = 3) |
  |       |      | and (`travtest`.`t1`.`type` = 2) and (`travtest`.`t2`.`type` = 1) and                      |
  |       |      | (`travtest`.`t2`.`sourceId` = 1) and (`travtest`.`t2`.`dId` = 1))                          |
  +-------+------+--------------------------------------------------------------------------------------------+
  </code></pre>