Discussion on combination of result sets from different query types

[jmazanec15]

Recently, from k-NN, we have received interest in combining results from text matching queries with k-NN queries (ref). So, I wanted to start a discussion about result combination and the problems doing it when scores are computed at the shard level.

From my understanding, the only way to currently combine scores from different queries is through a boolean query. In a boolean query, multiple query clauses are provided in the should or must section and the scores are combined via addition. On top of this, with function scoring, it is possible to manipulate the score of the results further before the addition of scores.

That being said, I see a few limitations with this approach.

First, it is difficult to combine result sets whose scores are produced via different scoring methods. In order to effectively combine results, the different queries' scores would need to be put on the same scale. By this, I mean that a score would need to meet 2 requirements: (1) indicates its relative relevance between it and the other documents scored in the query and (2) also be comparable with the relative relevance of results from other queries. For example, for k-NN, the score range may be 0-1 while BM25 scoring would be 0-Float.MAX_INT (I think). With this, it would be difficult to figure out an effective way to weight each result appropriately. One way to do this would be to normalize the scores before combining them. Normalization might be possible through rescoring, but this would happen at the shard level, which could cause problems when results are combined. For instance, if one shard has better results than another, normalization may skew the importance so that the top results from the latter shard are better than the former shard.

Second, it is not possible to consider global hits for re-ranking. Because scores are assigned at the shard level, any rescoring has to be done at the shard level. I see a problem with this in two cases: first, for score combination, if an index has a significant number of shards, a user may want only the top results to be combined instead of combining for the results of all shards in the index and then aggregating at the coordinator; second, in the future, a user may have a model that they want to run the results through to re-rank them that is expensive and they dont want to run for each shard in the index.

That being said, my preliminary thoughts to creating a solution for this would be to create some kind of search and merge api that might look like:

GET /{index_name}/_search_and_merge
{
    "queries": [
      {
        "query": {
          "knn": {
            "my_vector2": {
              "vector": [2, 3, 5, 6],
              "k": 2
            }
          }
        }
      },
      {
        "query": {
          "match_all": {}
        }
      }
    ],
    "merge": {
      "norm": true,
      "disjunctive": false,
      "strategy": "linear_combo"
      "params": {
        "weight_1": 10.2,
        "weight_2": 0.25
      }
    },
    "size": 100
}

Here the queries would be a list of queries to be executed independently and merge would contain the logic to combine the results at the coordinator level.

All that being said, I want to see what people think of doing this? Is there a way to accomplish this with the current search interface?

[dblock]

Would it make sense to extend rescoring to run on a higher level than shard (i.e. merge)?
Another idea is that merge could be seen as any map/reduce, so rescore (map) and merge (reduce)? That could scale like map/reduce as well.

[jmazanec15]

In general, I think it would be similar to rescore on coordinator level. The workflow I have in mind would:

1. Execute multiple queries that would return results to coordinator (almost like _msearch API)
2. Pre-process results from each query (i.e. normalization)
3. Expose rescore functionality based on these results (take into account score combination)
4. Reduce results based on score and execute fetch phase

I think extending rescore might be confusing from user perspective (i.e. when does it happen shard or coordinator).

[navneet1v]

Would it make sense to extend rescoring to run on a higher level than shard (i.e. merge)? Another idea is that merge could be seen as any map/reduce, so rescore (map) and merge (reduce)? That could scale like map/reduce as well.

Yes this can be seen as a possible solution and I think we should do some brainstorming around how we want to do this.

But as from requirements standpoint of the above ask, what Jack mentioned in the comment is the exact requirements. Do we want to call is rescore or some other name that we can debate.

[peterdm]

Take a look at this paper from the Pinecone team: https://arxiv.org/abs/2210.11934

Convex Combination shows promise as a simple/effective way to combine the two hybrid scores. (Normalize each, and regress to find a linear scaling factor between the two distributions).

Distributed normalization of course is the challenge. Shard-level might be workable.

I’d suggest starting with simply allowing the scores from each query type to be returned and combined as the developer sees fit.

For example convex combination could be implemented by two script_score queries inside a dismax tie=1 (where each script score employed a precomputed normalization function and boost for each query type).

[aishwaryabajaj-54]

What will be the order of execution of the BM25(may be multi-match) query and KNN query if we use a hybrid search query?

[navneet1v]

We have not decided yet as of now. I am working on building some proposal around the same. Will update this issue once I have some research done. But on high level I was thinking to run the queries in parallel. So that we can reduce the latency and then do the normalizations of the scores before we combine them.

But this is still very early thought. Will need to see what is best.

[navneet1v]

What will be the order of execution of the BM25(may be multi-match) query and KNN query if we use a hybrid search query?

@aishwaryabajaj-54 do we see a difference if the queries are performed in different order? As per my understanding if we are doing normalization of scores for each query and then combining the scores then it doesn't matter in which order the queries are executed.

Please let us know if you think otherwise and is there can be a case where this assumption doesn't hold true.

[navneet1v]

Would it make sense to extend rescoring to run on a higher level than shard (i.e. merge)? Another idea is that merge could be seen as any map/reduce, so rescore (map) and merge (reduce)? That could scale like map/reduce as well.

@dblock
The idea of extending the rescoring at higher level that shard looks very promising. But on a different level I was thinking to build another phase in the whole Query and Fetch phases flow. This can be used by different plugins to do operations at Manager Level before the control goes to Fetch phase. I will try to create a proposal for this to start some discussion.

[dblock]

Thanks @navneet1v. Since we're talking additional phases in query and fetch, cc-ing @nknize who has been thinking about refactoring aggregation, which I believe is either on the same path or at least related.