I have investigated this, however i still cannot explain why:

SELECT cl.`cl_boolean`, l.`l_name`
FROM `card_legality` cl
INNER JOIN `legality` l ON l.`legality_id` = cl.`legality_id`
WHERE cl.`card_id` = 23155

Is considerably reduced than:

SELECT cl.`cl_boolean`, l.`l_name`
FROM `card_legality` cl
LEFT JOIN `legality` l ON l.`legality_id` = cl.`legality_id`
WHERE cl.`card_id` = 23155

115ms Versus 478ms. Both are using InnoDB and you will find associations defined. The 'card_legality' consists of approximately 200k rows, as the 'legality' table consists of 11 rows. This is actually the structure for every:

CREATE TABLE `card_legality` (
  `card_id` varchar(8) NOT NULL DEFAULT '',
  `legality_id` int(3) NOT NULL,
  `cl_boolean` tinyint(1) NOT NULL,
  PRIMARY KEY (`card_id`,`legality_id`),
  KEY `legality_id` (`legality_id`),
  CONSTRAINT `card_legality_ibfk_2` FOREIGN KEY (`legality_id`) REFERENCES `legality` (`legality_id`),
  CONSTRAINT `card_legality_ibfk_1` FOREIGN KEY (`card_id`) REFERENCES `card` (`card_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

And:

CREATE TABLE `legality` (
  `legality_id` int(3) NOT NULL AUTO_INCREMENT,
  `l_name` varchar(16) NOT NULL DEFAULT '',
  PRIMARY KEY (`legality_id`)
) ENGINE=InnoDB AUTO_INCREMENT=12 DEFAULT CHARSET=latin1;

I possibly could simply employ LEFT-JOIN, however it does not appear quite right... any ideas, please?

UPDATE: As asked for, I have incorporated the outcomes of explain for every. I'd run it formerly, however i dont pretend to possess a thorough knowledge of it..

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  cl  ALL PRIMARY NULL    NULL    NULL    199747  Using where
1   SIMPLE  l   eq_ref  PRIMARY PRIMARY 4   hexproof.co.uk.cl.legality_id   1   

AND, inner join:

id  select_type table   type    possible_keys   key key_len         ref                         rows    Extra
1   SIMPLE  l   ALL PRIMARY NULL    NULL    NULL    11  
1   SIMPLE  cl  ref PRIMARY,legality_id legality_id 4   hexproof.co.uk.l.legality_id    33799   Using where

I'd try EXPLAIN on of individuals queries. Just prefix each Choose with EXPLAIN and run them. It gives really helpful information on how mySQL is optimizing and performing queries.