Great discussion (and issue) summary, Ian...! To have "perfect" SQL++
semantics, the following query actually cannot be run as an index-only plan:
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;
However, the following query (Q2) could indeed be run index-only:
LET qvec = [1.1,2.2,3.3,4.4]
SELECT id
FROM col
WHERE year > 2000
AND ann_distance(qvec, embedding) IS NOT NULL
ORDER BY ann_distance(qvec, embedding) LIMIT 20;
The difference is that IS NOT UNKNOWN says that it's okay that the index
is partial with respect to bad embeddings. Semantically,
ann_distance(...) is just a function and it will return NULL if qvec and
col.embedding aren't comparable, and ORDER BY is not unhappy ordering
NULLs as well as non-null distances.
The challenge is that most users probably want to write Q1 for
simplicity yet they really want Q2's semantics. Moreover, in normal
cases there will probably be no "crap embeddings", so the two queries
will yield the same results in such cases (modulo ann vs. knn) - so this
issue is really a corner case, but an important one.
One minor simplification might be to offer users the ability to say more
at collection creation time. If users could tell us that col.embedding
is an embedding field during CREATE COLLECTION, and could say that the
field is an array of 4 doubles, and that non-compliant incoming objects
should be rejected as erroneous, then we would know that col.embedding
is NOT NULL in the collection, and that if vec is also legit, the two
queries will be the same semantically because ann_distance won't return
NULL.
A challenge that Ali pointed out in the discussion is that we can't
always control what the user puts into their collections - so....
I know this isn't an answer, but I'm hoping it will spur more thinking
and ideas here.
Cheers,
Mike
On 8/26/26 9:43 AM, Ian Maxon wrote:
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
