Is it possible to optimize a query that uses the '<>' operator?

Question

This a follow-up to a previous question.

How can I optimize this query so that it does not perform a full table scan?

 SELECT Employee.name FROM Employee WHERE Employee.id <> 1000;

.

explain SELECT Employee.name FROM Employee WHERE Employee.id <> 1000;
+----+-------------+-------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table       | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | Employee    | ALL  | PRIMARY       | NULL | NULL    | NULL | 5000 | Using where |
+----+-------------+-------------+------+---------------+------+---------+------+------+-------------+

(Empoyee.id is the primary key, in case that isn't clear.)

Answer 1

Have a covering index for name and id, and it should be able to fulfill the query using the index. This might be faster, because there's a good chance the entire index will already be in memory, while a table scan is more likely to need to go to disk.

Because of the low (non-existent) selectivity of your where clause you may need to provide a hint to get the database to use your index. I'm a sql server guy, and so I'm not sure of the syntax needed in mysql to hint an index, or even if mysql is able to take advantage of a covering index in this manner.

That said, I doubt you can get much improvement: you're returning every row but one. You should expect that to need to scan the table.

Answer 2

In traditional databases, you cant!

Of course, you could just omit all Employees with the given Id (when it is key or has an index) -- but normally you will still have the total majority of the table under your feet. So using an index might complicate things and thus a fts normally is the faster option.

When you have specialized databases, you could store the names of all employees adjacent to each other.

Edit: I now saw the other answer of Joel. Yes, this could be a way, since in fact your special index is now a specialized form of storing a part of the content. Good databases can just use the index content when it covers the columns needed -- this is rather nice. Of course, you will endup in a so called "full index scan" (but normally much faster as a full-table-scan).

Answer 3

There are a lot of things to try, it depends on how the database engine chooses to parse it, really. Some options:

select employee.name from employee where employee.id not in (1000);

You could also try a union with a less than and then a greater than.

But in the specific example you are giving (which may just be too simple for your real case) a table scan isn't necessarily a bad thing. If all the records have to be returned except one, using an index may in fact be slower.

Answer 4

Nothing you can do will increase performance. In this case the database must do a complete table scan, as you are asking for every record save one. Reading every page in an index on top of that would only reduce performance. Fortunately, even if you added an index, the database would be smart enough to ignore it...

EDIT to address @Juergens comment.
Juergen, you are right about a covering index, but there are conflicting effects here. Any use of an index in a scenario like this has bad effects in one sense... The query engine could have to perform one I/O Operation for each level in the index, for each row it needs to examine. If there are, say, 5 levels in the index, and 1M rows, that would be 5 Million I/O operations, compared to only 1M I/Os to do a complete table scan. This is why, in this scenario, most query optimizers would ignore any available index and do the table scan anyway. (unless you force it to use the index with a hint) The only mitigating factor is if EVERY attribute required by the query is in the index (covering index) and the number of index rows per page on disk is sufficiently smaller than the number of table rows per page to counteract the negative effect of having to traverse each level of the index for each row returned by the query.