Rewriting the query to use the nonconstructor expression results in the optimizer using all three columns in the index ( key_len=12 ): Thus, for better results, avoid mixing row constructors with  AND / OR  expressions. Use one or the other. Under certain conditions, the optimizer can apply the range access method to  IN()  expressions that have row constructor arguments. See Range Optimization of Row Constructor Expressions. The output from  EXPLAIN  shows  ALL  in the  type  column when MySQL uses a full table scan to resolve a query. This usually happens under the following conditions: For small tables, a table scan often is appropriate and the performance impact is negligible. For large tables, try the following techniques to avoid having the optimizer incorrectly choose a table scan: See Section 8.9.4, “Index Hints” . 1693 •Start  mysqld  with the  --max-seeks-for-key=1000  option or use  SET max_seeks_for_key=1000 to tell the optimizer to assume that no key scan causes more than 1,000 key seeks. See Section 5.1.8, “Server System Variables” . •Use  ANALYZE TABLE  tbl_name  to update the key distributions for the scanned table. See Section 13.7.3.1, “ANALYZE TABLE Statement” . •Use  FORCE INDEX  for the scanned table to tell MySQL that table scans are very expensive compared to using the given index: SELECT * FROM t1, t2 FORCE INDEX ( index_for_column ) WHERE t1. col_name =t2. col_name ; •The table is so small that it is faster to perform a table scan than to bother with a key lookup. This is common for tables with fewer than 10 rows and a short row length. •There are no usable restrictions in the  ON  or  WHERE  clause for indexed columns. •You are comparing indexed columns with constant values and MySQL has calculated (based on the index tree) that the constants cover too large a part of the table and that a table scan would be faster. See Section 8.2.1.1, “WHERE Clause Optimization” . •You are using a key with low cardinality (many rows match the key value) through another column. In this case, MySQL assumes that by using the key probably requires many key lookups and that a table scan would be faster. 8.2.1.23 Avoiding Full Table Scans (c2,c3) > (1,1) c2 > 1 OR ((c2 = 1) AND (c3 > 1)) mysql>  EXPLAIN SELECT * FROM t1 WHERE c1 = 1 AND (c2 > 1 OR ((c2 = 1) AND (c3 > 1)))\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 partitions: NULL type: range possible_keys: PRIMARY key: PRIMARY key_len: 12 ref: NULL rows: 3 filtered: 100.00 Extra: Using where Optimizing SELECT Statements