An indexed column in InnoDB always has an additional key to the gen_clust_index (aka Clustered Index) attached to it. This would be traversed by the first query to get to row 4000000 in the order of the index. Since it is the only column being requested, access to the table is unnecessary.

The second query has to collect the non-indexed column from the table along with the indexed column into a temp table. The temp table is then sorted before presenting the non-indexed column as SELECT output.

Notice another contrast

• The table count is 4636881
• The EXPLAIN plan for the first query traversed 4000010 indexed_column keys. No need to read the last 636871 keys.
• The EXPLAIN plan for the second query traversed 4636881 rows ordered by indexed_column. For every row picking up the non-indexed column out of the table, the indexed column (already sorted by the index) is looked up and comes along for the ride. The tmp table gets ordered by the indexed column, and mysqld then dismisses the first 4000000 rows, leaving 10 rows. All that interaction between table and index just for 10 rows is the bottleneck.

COMMON THINGS

In both instances, the query specfies the number of rows to traverse. Since the number of rows in the table is 4636881, we should readily expect a full scan. The contrast becomes apparent when the MySQL Query Optimizer decides where to perform the full scan.

• The first query is referencing an indexed column only in the SELECT list and the WHERE clause. The MySQL Query Optimizer chooses to perform a full index scan with no need to contact the table since everything needed is in the index.
• The second query is referencing an indexed column in the WHERE clause. However, it must reach out the table to retrieve the corresponding non-indexed column. The MySQL Query Optmizer was tipped off by the query that it must not use the index becasue of the number of rows it was expected to read. As a rule of thumb for any RDBMS, if more than 5% of a table has to be read to fulfill a query, the MySQL Query Optimizer will just throw the index 'under the bus' and do a full table scan.

Doing the math, here is what MySQL Query optimizer computes:

• 5% of 4636881 is 231844
• The second query is commanded to read 4000000 rows, which is way higher than 231844
• MySQL Query Optimizer realizes there would be too much interaction between table (because of the non-indexed column) and index (because of the indexed column) to get the needed data. It decides to read the table only (because both the indexed and non-indexed columns are residing together in the table) rather than bounce back and forth between them.

In my honest opinion, with the row count of the table, the present indexes the table has, and the number of rows prescribed by the query, the MySQL Query Optimizer made the correct decision.

RECOMMENDATION

Create this index

ALTER TABLE `table` ADD INDEX mynewndx (indexed_column,some_other_column);

and your second query will never touch the table again going forward. The MySQL Query Optimizer will behave quite differently when it sees this new index.

According to the Book

Page 198 says the following:

• Paragraph 6 : A MyISAM B-tree consists of leaf and nonleaf nodes, or pages.
• Paragraph 7 : Both leaf and nonleaf nodes key values and pointers to the record positions in the datafile. Nonleaf nodes additionally contains pointers to child nodes.

Given this description

• a unique index would have more nonleaf nodes. This would lend itself mode towards ordering and searching.
• nonunique index would requires less nonleaf nodes. This would lend itself mode towards doing range scans (tables and index)
• A covering index (which would contain all needed columns for specific SELECT queries) would combine the best and worst of both. This would allow for a range scans that would need more nonleaf nodes and provide for ordering/searching. The additional benefit would be bypassing the need for reading table data if all needed columns are present and accounted for in the index.
• I mentioned other aspects in my past post Benefits of BTREE in MySQL

SPACE

• Unique Indexes would take up more space for nonleaf nodes.
• Covering indexes would need more space than a nonunqiue index but would have a higher multi-columns index cardinality that can approach the actual row count of the table.

PERFORMANCE (Heavy-Write Environment)

• SELECTs would be very fast for exact keys
• SELECTs that only touch a Covering Index would be extremely fast
• Random INSERTs can be a nightmare due to rotations/rebalancing of nonleaf nodes
• UPDATEs that change key values can be a nightmare due to rotations/rebalancing of nonleaf nodes
• The higher the cardinality, the more nonleaf nodes, the better the performance
• The lower the cardinality, the fewer the nonleaf nodes, the worse the performance
• The more columns in the index increases the effects of the cardinality

MEMORY

Depends on Storage Engine

• MyISAM : The key buffer only caches index pages. Covering indexs are your best friend here
• InnoDB : Buffer Pool Needs to be Big Enough to Hold Data Pages, Index Pages, and Index Page Changes (See InnoDB Architecture, What are the main differences between InnoDB and MyISAM?)