Optimising MySQL query with lots of self-joins
How to fix it in MySQL

As can be seen from line 3 of the EXPLAIN statement, a [edit:]covering index is not being used here. It needs to join on the entity_id and the type and no key is available for that.

ALTER TABLE entity_relationship ADD KEY e_t_r 
   (entity_id, type, relationship_id);


This makes the key available, but MySQL chooses not to use it. It can be forced with: USE INDEX (e_t_r) :

SELECT lt.entity_id entity_id, 
       py.relationship_id relationship_id,
       'implied-constituent' `type` 
FROM entity_relationship lt,
     entity_relationship ly,
     entity_relationship pt USE INDEX (e_t_r),
     entity_relationship py
WHERE lt.type='constituent'
  AND lt.relationship_id = ly.relationship_id
  AND ly.type='constituency'
  AND ly.entity_id = pt.entity_id 
  AND pt.type='constituent' 
  AND pt.relationship_id = py.relationship_id 
  AND py.type='constituency';


This now runs in 0.8s. (compare to 17.7s without forcing it to use that index.) This is with MySQL 5.1.63.

How to fix it in MariaDb

Well, you don't have to! 

MariaDb executes the query very fast with or without the USE INDEX intervention (0.25s, but it's on a different host so I would expect this to be nearer the 0.8s in the optimised version above).

Also, MariaDb does not use the new index and is quite happy with the t_e_r index, including using it as a covering index (i.e. uses the index for the entire data fetch).

I'm getting more and more impressed with MariaDb and now considering switching.