Indexes don't handle negation correctly

[erizocosmico]

Because FOO != 1 gets translated to NOT (FOO = 1), we can use FOO = 1 in the index. Afterwards, the condition NOT (FOO = 1) is evaluated. Because it is false, the result will be 0 rows.

Therefore, all queries using an index and != or NOT IN will have 0 results.

[erizocosmico]

As discussed via slack with @mcarmonaa, another part of the bug is the fact that when a NOT appears, index is not used (Because filters are split by and or or and does not go deeper than the NOT). But when this works, the behavior will be the one described in the bug.

[mcarmonaa]

There are different involved things here as discussed in slack:

• To use indexes on several columns we should be able to mix operations Multi column indexes are only used if all columns share operation #261 to make negation work.
• To handle indexes on negation properly we should have and IndexLookup retrieved with something similar to:

type Negate interface {
     Not(...IndexLookup) IndexLookup
}

• Although an index is created on single column either as

create index files_not_path_idx on files using pilosa (file_path)

or as

create index files_not_path_idx on files using pilosa (file_path != 'LICENSE')`

the index won't be used in a simple query like

select file_path from files where file_path!='LICENSE';

Right now the rule to assign indexes only manage AND, OR, IN, EQUALS expressions so when a NOT expression is found will no be an index assigned.

Because of the third point, I couldn't find a case where the query triggers the use of some index getting no rows as result.

@ajnavarro @erizocosmico Have I missed or misunderstood something?

[ajnavarro]

1- the correct Negate interface would be:

type Negate interface {
     Not() IndexLookup
}

2- Index created as create index files_not_path_idx on files using pilosa (file_path != 'LICENSE') is indexing true or false. I think we only check left and right expressions on filter expressions, not the filter expressions themselves, that's why that index doesn't work.

3- Yep, appears to be working correctly right now:

mysql> create index tree_entry_name_idx on tree_entries using pilosa (tree_entry_name);
Query OK, 0 rows affected (0,00 sec)

mysql> explain format=tree select tree_entry_name from tree_entries where tree_entry_name != 'README.md';
+----------------------------------------------------------------------+
| plan                                                                 |
+----------------------------------------------------------------------+
| Project(tree_entries.tree_entry_name)                                |
|  └─ PushdownProjectionAndFiltersTable                                |
|      ├─ Columns(tree_entries.tree_entry_name)                        |
|      ├─ Filters(NOT(tree_entries.tree_entry_name = "README.md"))     |
|      └─ Table(tree_entries)                                          |
|          ├─ Column(repository_id, TEXT, nullable=false)              |
|          ├─ Column(tree_entry_name, TEXT, nullable=false)            |
|          ├─ Column(blob_hash, TEXT, nullable=false)                  |
|          ├─ Column(tree_hash, TEXT, nullable=false)                  |
|          └─ Column(tree_entry_mode, TEXT, nullable=false)            |
+----------------------------------------------------------------------+
10 rows in set (0,00 sec)

mysql> explain format=tree select tree_entry_name from tree_entries where tree_entry_name = 'README.md';
+-----------------------------------------------------------------+
| plan                                                            |
+-----------------------------------------------------------------+
| Project(tree_entries.tree_entry_name)                           |
|  └─ IndexableTable                                              |
|      ├─ Columns(tree_entries.tree_entry_name)                   |
|      ├─ Filters(tree_entries.tree_entry_name = "README.md")     |
|      └─ Table(tree_entries)                                     |
|          ├─ Column(repository_id, TEXT, nullable=false)         |
|          ├─ Column(tree_entry_name, TEXT, nullable=false)       |
|          ├─ Column(blob_hash, TEXT, nullable=false)             |
|          ├─ Column(tree_hash, TEXT, nullable=false)             |
|          └─ Column(tree_entry_mode, TEXT, nullable=false)       |
+-----------------------------------------------------------------+
10 rows in set (0,00 sec)