Determine the default size, if any, to set for bypassing HNSW graph building for tiny segments in Elasticsearch vector format / wrappers.

[ChrisHegarty]

Determine the default size, if any, to set for bypassing HNSW graph building for tiny segments in Elasticsearch vector formats and wrappers.

This issue has been filed to as a followup to #137007.

relates apache/lucene#14963)

[elasticsearchmachine]

Pinging @elastic/es-search-relevance (Team:Search Relevance)

[mayya-sharipova]

I am looking at the formula used in Lucene by default:

public static final int HNSW_GRAPH_THRESHOLD = 100

shouldCreateGraph(graphThreshold, node + 1) 

private static boolean shouldCreateGraph(int k, int numNodes) {
    if (k <= 0) {
      return true;
    }
    int expectedVisitedNodes = expectedVisitedNodes(k, numNodes);
    return numNodes > expectedVisitedNodes && expectedVisitedNodes > 0;
  }

 public static int expectedVisitedNodes(int k, int graphSize) {
    return (int) (Math.log(graphSize) * k);
  }

which means we create graph starting from numNodes > Math.log(numNodes) * 100;
and that first numNodes will be 648.

Isn't that too little? In the past we were talking about skipping graphs < 1000 or even several thousands?

---

If we make threshold 1000 that starting from the node 9118 we need to build graph.

[benwtrent]

I would think our default is dictated by what we think the "default" behavior is for Elasticsearch. This might be something like num_candidates: 250 as k: 100 seems more typical? But, if we consider k: 1000 as the most likely request size, then we should choose 2500 (we by default provide num_candidates: 2.5*k).

[mayya-sharipova]

Currently in Elasticsearch:

k: Defaults to the search request size (10).

num_candidates: Defaults to 1.5 * k if k is set, or 1.5 * size if k is not set. 

So by default k is 10. But it is too small.
May be we can go with k equal to 100, num_candidates: 150; and pass 150 to LuceneHNSW writer instead of default NSW_GRAPH_THRESHOLD = 100? This would start graph construction with 1045 docs. I can do benchmarking.

[benwtrent]

@mayya-sharipova one caveate:

• We default to bbq_hnsw
• bbq_hnsw oversamples by 3x right now
• 100 k then becomes 300k

So, I would say 300 is a good value.

[benwtrent]

One other thing here @mayya-sharipova do we want to add a query time flag that allows users to skip these "flat indices" on queries?

Assuming our new merge policy grabs these tiny segments quickly, maybe users are OK with an even larger delay in NRT to get results more quickly?

[mayya-sharipova]

@benwtrent I can start with HNSW_GRAPH_THRESHOLD=300 for disk_bbq formats (which will start graph building from 2,327 nodes).

I will do benchmarking to see impact on queries, which will help us make a decision if we want to have an extra param for queries.