Description:
A query returning hierarchical information was originally designed to return the children of a particular entry. Using 'explain' on the query, everything in the query was using the proper indexes. Changing the query to also return its parent by adding an 'or' to the where clause resulted in an unexpected full table scan. Even issuing an 'or false' to the where clause would result in the full table scan.
How to repeat:
A test schema and sample query is provided that exhibits the behavior.
---------------------------------------------------------------------
CREATE DATABASE IF NOT EXISTS testschema;
USE testschema;
--
-- Definition of table `context`
--
DROP TABLE IF EXISTS `context`;
CREATE TABLE `context` (
`context_id` int(11) NOT NULL,
`node_id` int(11) default NULL,
PRIMARY KEY (`context_id`),
KEY `fk_context_node` (`node_id`),
CONSTRAINT `fk_context_node` FOREIGN KEY (`node_id`) REFERENCES `node` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
--
-- Dumping data for table `context`
--
/*!40000 ALTER TABLE `context` DISABLE KEYS */;
INSERT INTO `context` (`context_id`,`node_id`) VALUES
(1,1);
/*!40000 ALTER TABLE `context` ENABLE KEYS */;
--
-- Definition of table `hierarchy`
--
DROP TABLE IF EXISTS `hierarchy`;
CREATE TABLE `hierarchy` (
`id` int(11) NOT NULL auto_increment,
`parent_id` int(11) default NULL,
`node_id` int(11) default NULL,
PRIMARY KEY (`id`),
KEY `fk_hierarchy_hierarchy` (`parent_id`),
KEY `fk_hierarchy_node` (`node_id`),
CONSTRAINT `fk_hierarchy_hierarchy` FOREIGN KEY (`parent_id`) REFERENCES `hierarchy` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION,
CONSTRAINT `fk_hierarchy_node` FOREIGN KEY (`node_id`) REFERENCES `node` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8;
--
-- Dumping data for table `hierarchy`
--
/*!40000 ALTER TABLE `hierarchy` DISABLE KEYS */;
INSERT INTO `hierarchy` (`id`,`parent_id`,`node_id`) VALUES
(1,NULL,1),
(2,1,2),
(3,1,3),
(4,1,4),
(5,1,5);
/*!40000 ALTER TABLE `hierarchy` ENABLE KEYS */;
--
-- Definition of table `node`
--
DROP TABLE IF EXISTS `node`;
CREATE TABLE `node` (
`id` int(11) NOT NULL auto_increment,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8;
--
-- Dumping data for table `node`
--
/*!40000 ALTER TABLE `node` DISABLE KEYS */;
INSERT INTO `node` (`id`) VALUES
(1),
(2),
(3),
(4),
(5);
/*!40000 ALTER TABLE `node` ENABLE KEYS */;
------------------------------------------------------------------------------
Sample query:
select * from hierarchy hchild
left join hierarchy as hparent on hparent.id = hchild.parent_id
left join node as nchild on nchild.id=hchild.node_id
left join node as nparent on nparent.id=hparent.node_id
left join context as ctxchild on ctxchild.node_id=nchild.id
left join context as ctxparent on ctxparent.node_id=nparent.id
where ctxparent.context_id=1 or ctxchild.context_id=1;
Output from Explain command:
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: hchild
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 5
Extra:
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: hparent
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: testschema.hchild.parent_id
rows: 1
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: nchild
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: testschema.hchild.node_id
rows: 1
Extra: Using index
*************************** 4. row ***************************
id: 1
select_type: SIMPLE
table: nparent
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: testschema.hparent.node_id
rows: 1
Extra: Using index
*************************** 5. row ***************************
id: 1
select_type: SIMPLE
table: ctxchild
type: ref
possible_keys: fk_context_node
key: fk_context_node
key_len: 5
ref: testschema.nchild.id
rows: 1
Extra: Using index
*************************** 6. row ***************************
id: 1
select_type: SIMPLE
table: ctxparent
type: ref
possible_keys: fk_context_node
key: fk_context_node
key_len: 5
ref: testschema.nparent.id
rows: 1
Extra: Using where; Using index
6 rows in set (0.00 sec)
Note: Removing any one of the 'or' operands in the where clause will use the proper index. Changing the where clause to 'or false' will cause a full table scan.
Suggested fix:
I think that this is not optimized correctly, however I may be incorrect in my assumptions.
Description: A query returning hierarchical information was originally designed to return the children of a particular entry. Using 'explain' on the query, everything in the query was using the proper indexes. Changing the query to also return its parent by adding an 'or' to the where clause resulted in an unexpected full table scan. Even issuing an 'or false' to the where clause would result in the full table scan. How to repeat: A test schema and sample query is provided that exhibits the behavior. --------------------------------------------------------------------- CREATE DATABASE IF NOT EXISTS testschema; USE testschema; -- -- Definition of table `context` -- DROP TABLE IF EXISTS `context`; CREATE TABLE `context` ( `context_id` int(11) NOT NULL, `node_id` int(11) default NULL, PRIMARY KEY (`context_id`), KEY `fk_context_node` (`node_id`), CONSTRAINT `fk_context_node` FOREIGN KEY (`node_id`) REFERENCES `node` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION ) ENGINE=InnoDB DEFAULT CHARSET=utf8; -- -- Dumping data for table `context` -- /*!40000 ALTER TABLE `context` DISABLE KEYS */; INSERT INTO `context` (`context_id`,`node_id`) VALUES (1,1); /*!40000 ALTER TABLE `context` ENABLE KEYS */; -- -- Definition of table `hierarchy` -- DROP TABLE IF EXISTS `hierarchy`; CREATE TABLE `hierarchy` ( `id` int(11) NOT NULL auto_increment, `parent_id` int(11) default NULL, `node_id` int(11) default NULL, PRIMARY KEY (`id`), KEY `fk_hierarchy_hierarchy` (`parent_id`), KEY `fk_hierarchy_node` (`node_id`), CONSTRAINT `fk_hierarchy_hierarchy` FOREIGN KEY (`parent_id`) REFERENCES `hierarchy` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION, CONSTRAINT `fk_hierarchy_node` FOREIGN KEY (`node_id`) REFERENCES `node` (`id`) ON DELETE NO ACTION ON UPDATE NO ACTION ) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8; -- -- Dumping data for table `hierarchy` -- /*!40000 ALTER TABLE `hierarchy` DISABLE KEYS */; INSERT INTO `hierarchy` (`id`,`parent_id`,`node_id`) VALUES (1,NULL,1), (2,1,2), (3,1,3), (4,1,4), (5,1,5); /*!40000 ALTER TABLE `hierarchy` ENABLE KEYS */; -- -- Definition of table `node` -- DROP TABLE IF EXISTS `node`; CREATE TABLE `node` ( `id` int(11) NOT NULL auto_increment, PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8; -- -- Dumping data for table `node` -- /*!40000 ALTER TABLE `node` DISABLE KEYS */; INSERT INTO `node` (`id`) VALUES (1), (2), (3), (4), (5); /*!40000 ALTER TABLE `node` ENABLE KEYS */; ------------------------------------------------------------------------------ Sample query: select * from hierarchy hchild left join hierarchy as hparent on hparent.id = hchild.parent_id left join node as nchild on nchild.id=hchild.node_id left join node as nparent on nparent.id=hparent.node_id left join context as ctxchild on ctxchild.node_id=nchild.id left join context as ctxparent on ctxparent.node_id=nparent.id where ctxparent.context_id=1 or ctxchild.context_id=1; Output from Explain command: *************************** 1. row *************************** id: 1 select_type: SIMPLE table: hchild type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 5 Extra: *************************** 2. row *************************** id: 1 select_type: SIMPLE table: hparent type: eq_ref possible_keys: PRIMARY key: PRIMARY key_len: 4 ref: testschema.hchild.parent_id rows: 1 Extra: *************************** 3. row *************************** id: 1 select_type: SIMPLE table: nchild type: eq_ref possible_keys: PRIMARY key: PRIMARY key_len: 4 ref: testschema.hchild.node_id rows: 1 Extra: Using index *************************** 4. row *************************** id: 1 select_type: SIMPLE table: nparent type: eq_ref possible_keys: PRIMARY key: PRIMARY key_len: 4 ref: testschema.hparent.node_id rows: 1 Extra: Using index *************************** 5. row *************************** id: 1 select_type: SIMPLE table: ctxchild type: ref possible_keys: fk_context_node key: fk_context_node key_len: 5 ref: testschema.nchild.id rows: 1 Extra: Using index *************************** 6. row *************************** id: 1 select_type: SIMPLE table: ctxparent type: ref possible_keys: fk_context_node key: fk_context_node key_len: 5 ref: testschema.nparent.id rows: 1 Extra: Using where; Using index 6 rows in set (0.00 sec) Note: Removing any one of the 'or' operands in the where clause will use the proper index. Changing the where clause to 'or false' will cause a full table scan. Suggested fix: I think that this is not optimized correctly, however I may be incorrect in my assumptions.