Hello fellow devs,
There was an interesting question posed by Ali in a conversation
between some committers and contributors that I wanted to bring to the
larger community for discussion. I think it has some interesting
design considerations, for all kinds of specialized indexes. I will
try to describe it as I remember it today and Ali can certainly
correct me if I am misremembering.
Consider a query like the following, without an index:
```
LET qvec = [1.1,2.2,3.3,4.4]
SELECT id
FROM col
WHERE year > 2000
ORDER BY ann_distance(qvec, embedding) LIMIT 20;
```
This query today might return something like this (falling back to KNN):
```
{"id": 1, "year": 2020, "embedding": 1}
{"id": 2, "year": 2020, "embedding": [2.1, 1.2, 3.4, 5.6]}
```
The thing to note here is that an embedding that isn't in the same
dimension gets returned in the ORDER clause, because KNN scans the
whole dataset, null is comparable, and we return null when the two
vectors being compared aren't of the same dimension.
Now consider what happens if you create a vector index like so on 'col':
```
CREATE INDEX idx
ON col(embedding VECTOR)
INCLUDE (year)
TYPE VTREE
WITH { "dimension": 4 }
EXCLUDE UNKNOWN KEY;
```
The query now might return something like this:
```
{"id": 2, "year": 2020, "embedding": [2.1, 1.2, 3.4, 5.6]}
```
Because this query can be answered with an index-only plan, and the
VTree doesn't include records which end up having unknown or null
distance, like those without the same dimension.
The main rub here is that there has been a general design point in
AsterixDB (and in other DBMS), that the presence or absence of an
index can't change the result of a query. The index should simply
(hopefully) accelerate the query, not change its semantics. This means
for an index-only plan, the index has to know about every record that
also exists in the primary.
Index-only plans for any other type that is supported by the
Heterogeneous index (which is a BTree) don't fall into this; it builds
a complete index. In fact this was one of the many advantages of this
index type, compared to older typed indexes, and enabled the use of
index-only plans without any schema information.
However this advantage can't be used for these kinds of special
indexes which can't index all types of data. They can only be complete
with respect to types within their domain. We have many indexes of
this type today: RTree, Fulltext/inverted, and VTree. Furthermore in
the case of VTree, not using index-only plans induce a particularly
severe performance penalty, so simply falling back to the primary
isn't ideal.
With all that, we now arrive at the main dilemma: Indexes, even
index-only plans, shouldn't change query results. However making a
VTree either include null keys, or not use an index-only plan for Top
K queries, will give a major performance hit.
My personal opinion is that we should, in this particular case, simply
make it abundantly clear that for approximate indexes, they are not
complete. For RTree it is a harder case because it is an exact index,
but I think it's similar that data which doesn't exist in the space
the RTree is over, it doesn't make much sense to return something from
a spatial predicate on it. Overall I think that these special indexes
are intended for special use cases, and that it is OK to bend some
design philosophies a little to accommodate them.
What does everyone else think? I sort of feel like there should be
some third way to break this dilemma, but I can't put my finger on it.
- Ian
