title: mysql not using indexes when "not in" statement is present
body: <p>The table structure is:</p>
  
  <pre><code>CREATE TABLE `test` (
    `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `from` int(10) unsigned NOT NULL,
    `to` int(10) unsigned NOT NULL,
    `message` text NOT NULL,
    `sent` int(10) unsigned NOT NULL DEFAULT '0',
    `read` tinyint(1) unsigned NOT NULL DEFAULT '0',
    `direction` tinyint(1) unsigned NOT NULL DEFAULT '0',
    PRIMARY KEY (`id`),
    KEY `one` (`to`,`direction`,`from`,`id`),
    KEY `two` (`from`,`direction`,`to`,`id`),
    KEY `three` (`read`,`direction`,`to`),
    KEY `four` (`read`,`direction`,`from`)
  ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
  </code></pre>
  
  <p>I have a strange issue. Please have a look at the following query:</p>
  
  <pre><code>select test.id, test.from, test.to, test.message, test.sent, test.read, test.direction from test 
  where (
  
      (test.to = 244975 and test.direction &lt;&gt; 2 and test.direction &lt;&gt; 3 and 
          (
          (test.from = 204177 and test.id &gt; 5341203) OR 
          (test.from = 214518 and test.id &gt; 5336549) OR
          (test.from = 231429 and test.id &gt; 5338284) OR
          (test.from = 242739 and test.id &gt; 5339541) OR
          (test.from = 243834 and test.id &gt; 5340438) OR
          (test.from = 244354 and test.id &gt; 5337489) OR
          (test.from = 244644 and test.id &gt; 5338572) OR
          (test.from = 244690 and test.id &gt; 5338467) 
          )
  
      )
  
      or 
  
      (test.from = 244975 and test.direction &lt;&gt; 1 and test.direction &lt;&gt; 3 and 
          (
          (test.to = 204177 and test.id &gt; 5341203) OR
          (test.to = 214518 and test.id &gt; 5336549) OR
          (test.to = 231429 and test.id &gt; 5338284) OR
          (test.to = 242739 and test.id &gt; 5339541) OR
          (test.to = 243834 and test.id &gt; 5340438) OR
          (test.to = 244354 and test.id &gt; 5337489) OR
          (test.to = 244644 and test.id &gt; 5338572) OR
          (test.to = 244690 and test.id &gt; 5338467)
          )
      )
  
      or 
  
      (test.read &lt;&gt; 1 and test.direction &lt;&gt; 3 and test.direction &lt;&gt; 2 and test.to = 244975  and test.from not in (204177, 214518, 231429, 242739, 243834, 244354, 244644, 244690)
  
      )
  
      or
  
      (test.read &lt;&gt; 1 and test.direction = 2 and test.from = 244975 and test.to not in (204177, 214518, 231429, 242739, 243834, 244354, 244644, 244690)
  
      )
  
  
       )
  
  
  
       order by test.id;
  </code></pre>
  
  <p>If I do an explain on this query, it goes through all the rows:</p>
  
  <pre><code>1   SIMPLE  test    index   PRIMARY,one,two,three,four  PRIMARY 4       1440596 Using where
  </code></pre>
  
  <p>If I remove both the "not in" statements, then it works fine:</p>
  
  <pre><code>select test.id, test.from, test.to, test.message, test.sent, test.read, test.direction from test 
  where (
  
      (test.to = 244975 and test.direction &lt;&gt; 2 and test.direction &lt;&gt; 3 and 
          (
          (test.from = 204177 and test.id &gt; 5341203) OR 
          (test.from = 214518 and test.id &gt; 5336549) OR
          (test.from = 231429 and test.id &gt; 5338284) OR
          (test.from = 242739 and test.id &gt; 5339541) OR
          (test.from = 243834 and test.id &gt; 5340438) OR
          (test.from = 244354 and test.id &gt; 5337489) OR
          (test.from = 244644 and test.id &gt; 5338572) OR
          (test.from = 244690 and test.id &gt; 5338467) 
          )
  
      )
  
      or 
  
      (test.from = 244975 and test.direction &lt;&gt; 1 and test.direction &lt;&gt; 3 and 
          (
          (test.to = 204177 and test.id &gt; 5341203) OR
          (test.to = 214518 and test.id &gt; 5336549) OR
          (test.to = 231429 and test.id &gt; 5338284) OR
          (test.to = 242739 and test.id &gt; 5339541) OR
          (test.to = 243834 and test.id &gt; 5340438) OR
          (test.to = 244354 and test.id &gt; 5337489) OR
          (test.to = 244644 and test.id &gt; 5338572) OR
          (test.to = 244690 and test.id &gt; 5338467)
          )
      )
  
      or 
  
      (test.read &lt;&gt; 1 and test.direction &lt;&gt; 3 and test.direction &lt;&gt; 2 and test.to = 244975 
  
      )
  
      or
  
      (test.read &lt;&gt; 1 and test.direction = 2 and test.from = 244975 
  
      )
  
  
       )
  
  
  
       order by test.id;
  </code></pre>
  
  <p>Now the explain query returns:</p>
  
  <pre><code>1   SIMPLE  test    index_merge PRIMARY,one,two,three,four  one,two 5,5     30  Using sort_union(one,two); Using where; Using filesort
  </code></pre>
  
  <p>I am not sure why it does not work right. What am I missing in the indexes?</p>