Time Complexity: Cross-cluster search
O(n)
0
0
Cross-cluster search in Elasticsearch - Time & Space Complexity
Understanding Time Complexity
When using cross-cluster search, we want to know how the search time changes as we add more clusters or data.
We ask: How does the search cost grow when searching across multiple clusters?
Scenario Under Consideration
Analyze the time complexity of the following Elasticsearch cross-cluster search query.
GET /cluster_one:index_one,cluster_two:index_two/_search
{
"query": {
"match": { "field": "value" }
}
}
This query searches for documents matching "value" in "field" across two clusters and their indexes.
Identify Repeating Operations
Look at what repeats when the query runs:
- Primary operation: Searching each cluster's index for matching documents.
- How many times: Once per cluster-index pair involved in the search.
How Execution Grows With Input
As you add more clusters or indexes, the search runs more times, once per cluster-index.
| Input Size (number of clusters) | Approx. Operations |
|---|---|
| 2 | 2 searches |
| 10 | 10 searches |
| 100 | 100 searches |
Pattern observation: The total work grows directly with the number of clusters searched.
Final Time Complexity
Time Complexity: O(n)
This means the search time grows linearly as you add more clusters to search.
Common Mistake
[X] Wrong: "Searching multiple clusters happens all at once with no extra cost."
[OK] Correct: Each cluster runs its own search, so total time adds up with more clusters.
Interview Connect
Understanding how cross-cluster search scales helps you explain real-world search performance and design better queries.
Self-Check
What if we limited the search to only a subset of clusters? How would the time complexity change?