Don't use documents with 0 hits

[joancf]

If I have well understood the way elastiknn processes the queries is the following: (please correct me if I'm wrong)
Let's assume K=4 (hash functions), L=10 (hash tables) and that the query vector is V. This implies that there are 10 groups of 4 planes to discriminate.

• So first you compute for the 10 hash tables, a 4 bit vector (each bit corresponding if the vector to search is in the positive/negative part to each hash function) this gives, 10 values to query,( QVs ) ,each value having the form [num_hash,vector]

• Then for each shard,

  • you search for each QV and you get the list of documents that match that QV on that shard (this is obtained in the (hashAndFrequencies and their postings)
  • From the results you create a table of size the number of documents in that shard (new ArrayHitCounter(reader.maxDoc() )
  • For every QV you get the list of postings and then you acumulate them in the ArrayHitCounter
  • in the DocIdSetIterator you get the top documents , that is, the documents that have more matches, as having more matches in the different hash tables, would mean (and I think is a good approximation) that they are closer. And you return the top documents.

  In this last step you use the kthGreatest(candidates) to get the top(N) documents. To solve this, You generate a table that for each document you can get the number of hits. and you determine the minimum number of hits needed to be on the top(N) The problem, is that this minimum can be zero, so you are reporting documents that have no hits at all.

  I think that a minimum of one hit should be required for a document to be selected.

I would change this line from kthGreatest
while (kthGreatest > 0) {
to
while (kthGreatest > 1) {
I don't know if you agree ...

[joancf]

THe case of kthGreatest== 0 it is considered in the next lines in kthGreatest but then not when accessing the data as the comparison is done against candidates instead of kgr.numNonZero in MatchHashesAndScoreQuery DocIdSetIterator function

[alexklibisz]

I think your understanding is correct until the kthGreatest method.

The problem, is that this minimum can be zero, so you are reporting documents that have no hits at all.

In MatchHashesAndScoreQuery, we're iterating over the documents that match each hash:

elastiknn/elastiknn-lucene/src/main/java/org/apache/lucene/search/MatchHashesAndScoreQuery.java

Lines 76 to 80 in 9e320dd

	if (termsEnum.seekExact(new BytesRef(hf.hash))) {
	docs = termsEnum.postings(docs, PostingsEnum.NONE);
	while (docs.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
	counter.increment(docs.docID());
	}

We're reporting each document to the counter by calling counter.increment(docs.docId()):

elastiknn/elastiknn-lucene/src/main/java/org/apache/lucene/search/MatchHashesAndScoreQuery.java

Line 79 in 9e320dd

counter.increment(docs.docID());

So if a document has zero hits, we would never see it, and we would never report it to the counter.

That's at least my understanding of how it works. I'm happy to be wrong if it means we can make the search run faster :)

[joancf]

@alexklibisz
yes you only do the counter increment for those documents that do a hit,
but... the counter is an array the size of which is the number of documents in the shard.
So, after processing the hits, it has a value for each document in shard (a value than can be zero)
For example if we only have 5 documents it will be initialized as [0,0,0,0,0]
if the hits are for documents , 1,1,3,1,0 the final counter will be [1,3,0,1,0] (indicating for each documents how many hits)
then depending on the maximum number of documents to retrieve the counter computes the minimum hits a document must have to be selected (kthGreatest)
after that it goes again through the array of documents and gets the hits of each document, discarding those documents with less than the minimum number of hits (kthGratest),
but thre can be some documents having the same number of hits as the minimum hits that may be selected to reach the candidates, and these are the conflictive ones: Because when there not enough candidates the minimum hits will be zero and some zeros will go through

[alexklibisz]

Ok, I think I see what you're saying, and I think you're right.

Around here we start iterating back through all the docs found by the counter:

elastiknn/elastiknn-lucene/src/main/java/org/apache/lucene/search/MatchHashesAndScoreQuery.java

Lines 124 to 148 in 9e320dd

	public int nextDoc() {
	if (!started) {
	started = true;
	docID = counter.minKey() - 1;
	}
	// Ensure that docs with count = kgr.kthGreatest are only emitted when there are fewer
	// than `candidates` docs with count > kgr.kthGreatest.
	while (true) {
	if (numEmitted == candidates || docID + 1 > counter.maxKey()) {
	docID = DocIdSetIterator.NO_MORE_DOCS;
	return docID();
	} else {
	docID++;
	if (counter.get(docID) > kgr.kthGreatest) {
	numEmitted++;
	return docID();
	} else if (counter.get(docID) == kgr.kthGreatest && numEq < candidates - kgr.numGreaterThan) {
	numEq++;
	numEmitted++;
	return docID();
	}
	}
	}

And if kthGreatest == 0, there's a chance that we emit the doc, from here:

elastiknn/elastiknn-lucene/src/main/java/org/apache/lucene/search/MatchHashesAndScoreQuery.java

Lines 142 to 146 in 9e320dd

	} else if (counter.get(docID) == kgr.kthGreatest && numEq < candidates - kgr.numGreaterThan) {
	numEq++;
	numEmitted++;
	return docID();
	}

At least I think that could happen. I would need to test it out.

I'll go ahead and file an issue so we don't lose track of this.

[alexklibisz]

Filed here: #715

Feel free to give it a try to fix.

[alexklibisz]

I started on a PR to investigate the issue here: #716

[joancf]

Also I did ad a log, and I thought that the countHits function in elastiknn-lucene/src/main/java/org/apache/lucene/search/MatchHashesAndScoreQuery.java
should be called once per shard, but the numbers don't match
the buildDocIdSetIterator is called 1308 times in a system with k=10, L=116 and 64 shards,
I would expect a call for shard, but its doing it 20 times, any clue ?

[alexklibisz]

I believe it's actually once per segment. A shard can have multiple segments.

[alexklibisz]

This was fixed in #720 , released in https://github.com/alexklibisz/elastiknn/releases/tag/8.15.0.1