Introduction

This issue talks about the various high level directions which are being proposed for Score combination and Normalization techniques to improve Semantic Search/Neural Search Queries in OpenSearch(META ISSUE: #123). The proposals tries to use already created extensions in OpenSearch as much as possible. Also, we try to make sure that directions we are choosing are long term; provides different level of customizations for users to tweak the Semantics Search as per their needs. The document also proposes phased design and implementation plan which will help us to improve and add new feature with every phase.

For information how normalization improves the overall Quality of Results please refer this OpenSearch Blog for Science Benchmarks: https://opensearch.org/blog/semantic-science-benchmarks/

Current Architecture

For simplicity, let's us consider a 3 node OpenSearch cluster, where we have 2 data nodes and 1 coordinator node. The data node stores the data and coordinator node helps in running the request. This is how OpenSearch works on a very high level.

1. Request lands on a Coordinator node and this node will rewrite the queries and send out the request to all the required shards as part of Query Phase.
2. The shards then use that query and pass it to Lucene(Index Search) along with all the relevant Collectors. Lucene then again rewrite the query and start performing the leaf queries on the segments sequentially. Its uses the different collectors like TopDocsCollector to collect the documents with Top Scores and return this result back to Coordinator node.
3. Once the query results arrive on the Coordinator node, we move to next phase which is Fetch phase. In the Fetch phase we have different sub-fetch phases that runs. Important one is Source Phase and Score phase. The Score phase will again send out the request to Data nodes to get the sources for the document ids and build the response to send back to the clients.

Requirements

The customer here is referenced as the OpenSearch customers, who wants to use OpenSearch and wants to run Semantics Search in their application.

1. As a customer, I want to combine different results coming from Transformers query(K-NN Query) and BM-25 based queries to obtain better search results. Github link: [FEATURE] Hybrid search using keyword matching and kNN k-NN#717 (comment)
2. As a customer I want to experiment with different ways to combine and rank the results in final search output. Github Link: Discussion on combination of result sets from different query types OpenSearch#4557

Why current requirement cannot be fulfilled with current OpenSearch Architecture?

Currently, OpenSearch uses a Query and Fetch model to do the search. In this, first the whole query object is passed to all the shards, to obtain the top results from those shards and then fetch phase begins which fetches the relevant information for the documents. If we talk about 2 types of queries in a typical Semantic Search use case will have a K-NN query and text match query both of which produces scores using different scoring methods.

So at 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(refer https://arxiv.org/abs/2210.11934). By this, we mean is 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) 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. Hence any effective combination query clause like Bool will suffer the problems.
Second, it is not possible to consider global hits for re-ranking. Because scores are assigned at the shard level, any rescoring will be done at the shard level. Hence if we try to normalize the scores, the normalization will be local normalization and not the global normalization.
Let’s use below example to understand the problem in more details.

Example

Using the same cluster setup as defined on top and look at an example to understand the above 2 problems. For this example lets assume that we have an index whose schema looks like this:

PUT product-info
{
    "mappings": {
        "properties": {
            "title": {
                "type": "text"
            },
            "description": {
                "type": "text"
            },
            "tile_and_descrption_knn": {
                "type": "knn_vector",
                "dimension": 768
            }
        }
    },
    "settings": {
        "index": {
            "refresh_interval": "-1",
            "number_of_shards": "2",
            "knn": "true",
            "number_of_replicas": "0",
            "default_pipeline": "text-embedding-trec-covid"
        }
    }
}

The title and description are product title and description. The tile_and_descrption_knn field is a K-NN vector field which has a 768 dimensions dense vector created using Dense Vector Model.

Query
We are using Bool query clause to combine the results of K-NN(neural query converted to K-NN Query) and a text based search query. Bool Query should clauses have their scores combined — the more matching clauses, the better.

POST product-info/_search
{
    "query" : {
        "bool": {
            "should": [
                {
                    "multi-match": {
                        "query": "sofa-set for living room",
                        "fields": ["tile", "description"]
                    }    
                },
                {
                    "neural": {
                        "tile_and_descrption_knn": {
                            "query_text": "sofa-set for living room",
                            "model_id": "dMGrLIQB8JeDTsKXjXNn"
                        }
                    }
                }
            ]
        }
    }
}

Scores Computation Examples Happening at different Levels
Combination using above provided query: As we can see here because both K-NN and BM-25 scores are at different scale if one of the query behaves badly like example for document d8, it is still coming as the first response because of BM-25. The standard boolean combination is not taking the advantage of relative ranking. Documents like d7 are still lower down the results even when it has good scores in both BM-25 and K-NN. This problem will become more elevated as BM-25 scores are unbounded.

To solve this problem of joining scores for different queries running at different scale is to first Normalize the scores of both the queries and then combine the scores. We can read about the same here(https://arxiv.org/abs/2210.11934).

Using Normalization: To see how normalization works let’s look at the below table. In the below table we have done 2 types of normalization one which is done for every shard/data node and another at the Coordinator node(Global Normalization).

Note: I did the normalization using the scores present here hence documents have 0 scores after normalization.

Final Sorted Documents to be returned based on above examples:

If we keep our focus on the d8 document we can see how that document changes its position based on without normalization, with Local Normalization and with Global Normalization. As Local Normalization only considers the scores at per shard level, it can suffer in cases if one of the score is lowest. But in the Global Normalization(aka Normalization at Coordinator Node level), as we start to look scores from whole corpus it smoothens out the above problem, because it can happen that more bad scores can come from other shards. We did experiments on that to verify it.

System Requirements

Functional Requirements:

1. System should be able to normalize the scores of each sub-query by using the relevant corpus level information.
2. System should be able to combine normalized scores of these different subqueries by using different techniques provided as input and by considering global rankings.
3. System should be able to get the information like max score and min score etc of the whole corpus, as these are required attributes for normalization.
4. System should be able to combine(not necessary sum) the results returned from different shards based at global level.
5. The solution should be generic enough to combine the scores of subqueries and not limited to k-NN and text matching.

Good to Have but not as P0:

1. The proposed solution should able to provide support different features like pagination, scripting, explain etc.
2. The solution shouldn’t degrade in terms of latency and CPU consumption over a normal query which does combination at Shard Level.

High Level Directions for Building the Solution

If we look at the requirements we see that we need solutions at different level of the whole search api flow. We can divide the whole flow in 3 parts:

1. Define the API input which can be used to run the sub-queries independently and return results at Coordinator node separately.
2. Obtain the relevant information like max scores, min scores at the global level for the provided sub-queries and perform normalization.
3. Define a component to normalize the all results obtained from different shards and combine them based on algorithms provided by users. After that let the Fetch phase run, to get the source for the documents ids, as it was working earlier.

Defining _search API Input

The proposal for the input is to use the _search api and define a new compound query clause. This new compound query clause will hold the array of Queries which will be executed in parallel at per data node level. The name of the new query clause is not yet defined. The interface of this new query clause is inspired from dis_max query clause. But dis_max query clause runs the queries sequentially. The new query clause will make sure that Scores are calculated at shard level independently for each sub query. The sub-queries re-writing will be done at Coordinator level to avoid duplicate computations.

Note: The interfaces defined here are not finalized. The interfaces will be refined as part of LLD github proposals. But we want to make sure that we align ourselves with high level approach. first

PUT <index-name>/_search
{
    "query": {
        "<new-compound-query-clause>": {
            "queries": [
                { /* neural query */ }, // this is added for an example
                { /* standard text search */ } // If a user want to boost some scores or update 
               // the scores he need to go ahead and do it in this query clause
            ],
            ... other things to be added and will come as part of next sections
        }
    }
}

Pros:

1. From customer standpoint, all their API calls will remain same, and they need to update only the body of the request.
2. From cohesion standpoint, as we are doing the search it make sense to include with the _search api to provide a unified experience for customers who are doing search via OpenSearch.
3. Less maintenance and consistent output format, as the new compound query is integrated with _search api.
4. Integration with other search capabilities like Explain Query, Pagination, _msearch will be possible, rather than reinventing the wheel.

Cons:

1. From implementation standpoint, we need define new concepts in OpenSearch like new Query clause, which will require customer education in terms of how to use it.

Alternatives Considered

Alternative-1: Implement a new Rest Handler instead of using creating a new compound query
The idea here to create a new rest handlers which define the list of queries whose scores needs to be normalized and combined.
Pros:

1. This will provide flexibility for the team to do experiments without touching core capabilities of OpenSearch.
2. Easier implementation as the new rest handlers is limited to Neural Search Plugin.

Cons:

1. Duplicate code and interfaces as we will be implementing the same search api functionality(size, from and to, include source fields, scripting etc.)
2. A higher learning curve and difficult in adoption for customers who are already using _search api for other search workloads.

Obtaining Relevant Information for Normalization and score Combination

This section talks about how OpenSearch will get the relevant information required for doing the Normalization. For example purpose lets say customer has defined the min-max normalization so for every subquery we will need the min and max sore for the whole corpus.
OpenSearch during the query phase it uses a QueryPhaseSearcher class to do the Query and collect the documents at shard level using TopDocsCollector interface. There is no extension point present in the QueryPhaseSearcher to use a different implementation of TopDocsCollector. The only extension we have is that a plugin can define a new QueryPhaseSearcher implementation. So we will define a new QueryPhaseSearcher implementation which will implement a new TopDocsCollector interface at shard level to gather the relevant information for doing normalization.

Pros:

1. It provides a cleaner way to modify the query phase at a shard level without adding extra round trips.
2. The interface is provides us full power on how to implement the query and return the results, so we can keep on updating this

Cons:

1. As of 1/18/2023, only a single plugin can define the queryphase searcher in the whole OpenSearch. We need to fix this to make sure that multiple QueryPhaseSearcher implementations can be added by plugins. This is similar to what we did for K-NN where only 1 engine implementation can be defined for the whole OpenSearch and CCR and K-NN was not working together.
2. We can get possible conflicts with Concurrent Phase Searcher defined here, as it also defines a query phase searcher.

Alternatives Considered

Alternative1: Enhance DFS Query Search type or create a new Query Search type to get information for doing normalization
The default search type in OpenSearch is Query and the Fetch, which first query the results and then fetch the actual source from the shards. The DFS query is another search type which customer can put as a query params to change the search type. In DFS Query and Fetch, OS will first Prequery each shard asking about Term and Document frequencies and send this information to all the shards where scores are calculated using this global Term/Document Frequencies.

We can build similar to this, where we can do the pre-query to find the min-max scores from all the shards and then pass this information where each shard can do the normalization of the scores for each sub-query.

Pros:

1. This avoids adding new phases/transformers in between query and fetch phases.

Cons:

1. An extra round trip to data nodes will be added which will lead to increase in latency. DFS query and fetch also faces this extra latency.
2. For DFS query and Fetch the information is already precomputed and present in the Lucene files (postings format files but for Normalization as the score calculation needs to be done we will end up running the queries twice. For K-NN queries this pre-fetch can only be done if we run the K-NN query.

Normalizing and Combining Scores using Search Pipeline

The idea here is to extend the Search Pipeline Request and Response transformers to create another type of Transformer which will be called after the query phase is completed. We will use this transformer interface to do the normalization and score combinations for the document ids returned from Query phase as per the user inputs. The transformed result will then be passed on the Fetch phase which will run as it is.
Below is the modified input of the above proposed API input. It adds relevant fields to do the Normalization and Score Combination.

Note: The interfaces defined here are not finalized. The interfaces will be refined as part of LLD github proposals. But we want to make sure that we align ourselves with high level approach.

PUT /_search_processing/pipeline/my_pipeline
{
  "description": "A pipeline that helps in doing the normalization",
  "<in-between-query-fetch-phase-processor>": [
    {
        "normalizaton-processor": {
            // we can bring in the normalization info from _search api to this place if required
            // It will be discussed as part of LLD.
        }
    }
  ]
}


PUT <index-name>/_search?pipeline=my_pipeline
{
    "query": {
        "<new-compound-query-clause>": {
            "queries": [
                { /* neural query */ }, // this is added for an example
                { /* standard text search */ } // If a user want to boost some scores or update 
               // the scores he need to go ahead and do it in this query clause
            ],
            // The below items be a part of processor also
            "normalization-technique" : "min-max" // min-max etc.., Optional Object
            "combination" : {
                "algorithm" : "harmonic-mean", // all the values defined in #3 above, interleave, harmonic mean etc
                "parameters" : {
                    // list of all the parameters that can be required for above algo
                    "weights" : [0.4, 0.7] // a floating pointing array which can be used in the algorithm
                }
            }
        }
    }
}

Alternatives Considered

Alternative-1: Create a new phase in between query and fetch phase
The high level idea here is to create a phase which runs in between the Query and Fetch phase which will do the Normalization.
Pros:

1. No specific pros that I can think for this approach apart from we will not have any dependency on Search Pipelines.

Cons:

1. Currently there is not extension points in OpenSearch to create a phase, so we need to build everything from scratch.
2. Problems will arrive in during implementation where code need to identify for which queries this new phase to run, and then we need implement some sophisticated logic to identify that.

Alternative-2: Create a Fetch Subphase which do the Normalization and score combination
OpenSearch provides an extension where plugins can add Fetch subphases which will run at the end when all Core Subphases are executed. We can create a Fetchsubphase that will do the normalization and score combination. But problem with this, as we have multiple sub-queries we need to change the interfaces to make sure that all the information required for Normalization needs to be passed in. This will result in duplicated information and multiple hacks to pass through the earlier fetch phases.
Pros:

1. No new extension points needs to be created as adding new subphases in Fetch phase is already present.

Cons:

1. Order of execution of fetch subphases is not consistent. It depends on which plugin got registered first and the fetch sub-phases of that plugin will run first. This will create inconsistency across clusters with different set of plugins. Code reference.
2. There is a source subphase which gets the source info for all the docIds, running this before normalization will make OpenSearch get sources for document Ids which we will not be sending in response. Hence waste of computation.

Alternative-3: Use SearchOperationListeners interface
SearchOperationListener runs at a Shard Level and not the Coordinator Node Level. Please check this, and this code reference. Hence we cannot use SearchOperationListeners. As we need the normalization to be done at Coordinator Node Level.

High Level Diagram

Based on the above 3 directions, below is the high level flow diagram. The 2 subqueries are provided as an example. There will be a limit on how many subqueries a customer can define in the query clause. This max number for the subqueries we will be keeping is 10(There is no specific reason for this limit, just want to make sure that we have limits imposed to make sure to avoid long running queries leading to Circuit Breaker and Cluster failures).

** There can be many sub-queries in the new compound query.**

Future Scope or Enhancements which will be picked up during next phases

Implementing Pagination in new Compound Query Clause

The proposed design doesn’t support for the Paginated Queries in the first phase to reduce the scope of the phase-1 launch. We also have not done deep-dive on how this can be implemented and what is the current solution of pagination.

Enhance the explain query functionality for new compound Query Clause

With the phase-1 implementation of the new query we won’t be providing the explain functionality for the query clause. Explain api provides information about why a specific document matches (or doesn’t match) a query. This is very useful api for customers to understand and do debugging.

Enabling Parallel/Concurrent Search on Segments functionality for new Compound Query

The idea here is to enable the parallel search for all the different queries provided in the Compound Query to improve the performance for this query. Parallel Search on Segments is already in sandbox for OpenSearch(https://github.com/opensearch-project/OpenSearch/tree/main/sandbox/plugins/concurrent-search).

Implement Script based Combination to allow customers to use any Score combination Techniques

The initial proposal provides customers only a set of functions to combine the scores with Script based combination customer can define custom scripts that can be used to combine the scores before we rank them.

Integrating the compound query to be written via Querqy etc to provide better experience for customers

The idea here is the new compound query clause can become overwhelming, hence we want to integrate it with different Query writing helpers like Querqy etc to facilitate easy query writings for customers.

Launch Plan

Below are some high level phased approach for building the feature. These are not set in stone and may change as we start making progress in the implementation

Phase-1

Given that we are defining new compound query clause for OpenSearch we will launch these features defined in this document and high level design under feature flag. High Level items:

1. Customers can use new compound query to do the normalization, we will lay the ground work and low level interfaces for doing running the compound query.
2. Adding support in OpenSearch to provide more than 1 QueryPhaseSearcher implementation
3. Customer can use standard normalization and score combination techniques defined in the phase 1. See appendix section for the different normalization and score combination techniques that will be present in phase-1.
4. Provide the first set of Performance testing results for customers with this new compound query.

Phase-2

The phase-2 will focus on these items:

1. Solidify the compound query interfaces and do GA after taking customer feedbacks.
2. We will add the capability for doing the Pagination queries for this new compound query clause.
3. Add explain query functionality for new this new compound query clause.
4. Integration in different Language specific opensearch clients.

Phase-3

The phase-3 will focus on these items:

1. Enabling Parallel segments search for the new compound query.
2. Implement Script based Combination to allow customers to use any Score combination Techniques

Phase-4

By this time we will have a good understanding of how customer are using this new compound query. This phase will start to focus on how we can now make it easier for customer to start using this new query clause. The below item helps us in doing that:

1. Integrating the compound query to be written via [Querqy] (https://opensearch.org/docs/latest/search-plugins/querqy/index/) to provide better experience for customers

FAQ:

Does other products support combining scores at Global Level?

Yes, Elastic Search supports this feature. But it combines the results of K-NN query with the text match query only. It is not generic enough. Also ES doesn’t support normalization of scores globally. Reference: https://www.elastic.co/guide/en/elasticsearch/reference/master/knn-search.html#_combine_approximate_knn_with_other_features.
As per the documentation limitation is:
Approximate kNN search always uses the dfs_query_then_fetch search type in order to gather the global top k matches across shards. You cannot set the search_type explicitly when running kNN search.

Example Query:

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": 10
}

Open Questions

Question1: Should we consider the case where subqueries are getting normalized using different techniques or customer only wants to normalize the single query and not the other queries?

After discussing, this is a very valid use case. But we don’t have enough data to prove this hypothesis. This will really depend on customer use case. I would suggest to start with lets do normalization on all the sub-queries as we can see from this blog that we should do normalization on all the sub-queries. Also as this is not a one way door.

Question2: How we are going to calculate the min score for the queries globally?

We will have a min score from different shards but as of now we don’t have a way to find the global min score for the K-NN queries. To do that we need to run exact K-NN. As of now I am trying to find a way to do this. For text matching, as we will iterate over the all the segments we will have min score. But more deep-dive is required the feasibility of the solution.

Next Steps:

1. I will working on creating the POCs for the proposal to validate the understandings of Query Clauses, DocsCollector and SearchPhase Searcher etc.
2. The API interface created for _search api is not final. This is more for understanding I have put my initial thought process. I will be creating more github issues to discuss on that in more details.

Appendix

What is Normalization?

Normalization is a data transformation process that aligns data values to a common scale or distribution of values.
Normalization requires that you know or are able to accurately estimate the minimum and maximum observable values. You may be able to estimate these values from your available data.

What are different ways to do the normalization?

1. y = (x – min) / (max – min)

Score Combination Techniques

Now you have 2 or more results. You need to combine both of them. There can be many way you can combine the results(Geometric Mean, Airthmatic Mean etc).

Approach 1: Normalized arithmetic mean

Assume we have 2 sets of results, resultsa​ and resultsb​. Each result has a score and a document id. First, we will only consider the intersection of results in a and b (i.e. resultsc​=resultsa​∩resultsb​). Then, each document in resultsc​ will have 2 scores: one from a and one from b. To combine the scores, we will first normalize all scores in resultsa​ and resultsb​, and then take the arithmetic mean of them:

score=(norm(scorea​)+norm(scoreb​))/2

Approach 2: Normalized geometric mean

Similar to Approach 1, but instead of taking the arithmetic mean, we will take the geometric mean:
score=(​norm(scorea​)∗norm(scoreb​))

Approach 3: Normalized harmonic mean

Similar to Approach1, but instead of taking the arithmetic mean, we will take the harmonic mean:

score=2/(1/norm(scorea​)+1/norm(scoreb​))

Approach 4: Normalized Weighted Linear Combination

Instead of taking the mean of the scores, we can just try different weights for each score and combine them linearly.

score=wa​∗norm(scorea​)+wb​∗norm(scoreb​)

Approach 5: Normalized Weighted Geometric Combination

Similar to above approach, but instead of combining with addition, we can combine with multiplication:

score=log(1+wa​∗norm(scorea​))+log(1+wb​∗norm(scoreb​))

This approach has previously been recommended for score combination with OpenSearch/Elasticsearch: elastic/elasticsearch#17116 (comment).

Approach 6: Interleave results

In this approach, we will produce the ranking by interleaving the results from each set together. So ranking 1, 3, 5, ... would come from resultsa​ and 2, 4, 6, ... would come from resultsb​.

Reference Links:

1. Meta Issue for Feature: [META] Score Combination and Normalization for Semantics Search. Score Normalization for k-NN and BM25 #123
2. Compound Queries: https://www.elastic.co/guide/en/elasticsearch/reference/7.17/compound-queries.html
3. Dis_max Query: https://www.elastic.co/guide/en/elasticsearch/reference/7.17/query-dsl-dis-max-query.html
4. DFS Query and Fetch: https://www.elastic.co/blog/understanding-query-then-fetch-vs-dfs-query-then-fetch
5. Querqy: https://opensearch.org/docs/latest/search-plugins/querqy/index/
6. Science Benchmarks: https://opensearch.org/blog/semantic-science-benchmarks/