Geo-point and geo-shape types in Elasticsearch - Time & Space Complexity

Time Complexity: Geo-point and geo-shape types

O(n)

Understanding Time Complexity

When working with geo-point and geo-shape types in Elasticsearch, it is important to understand how query time grows as the number of locations or shapes increases.

We want to know how the search time changes when we add more geographic data.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch geo query.

GET /places/_search
{
  "query": {
    "geo_shape": {
      "location": {
        "shape": {
          "type": "polygon",
          "coordinates": [[[30, 10], [40, 40], [20, 40], [10, 20], [30, 10]]]
        },
        "relation": "within"
      }
    }
  }
}
    

This query finds documents where the geo-shape field "location" is within the given polygon.

Identify Repeating Operations

In this geo-shape query, Elasticsearch checks each document's shape against the query polygon.

• Primary operation: Checking spatial relation between shapes.
• How many times: Once per document in the index.

How Execution Grows With Input

As the number of documents with geo-shapes grows, the number of shape comparisons grows roughly the same.

Input Size (n)	Approx. Operations
10	10 shape checks
100	100 shape checks
1000	1000 shape checks

Pattern observation: The work grows linearly as more geo-shapes are stored.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows in direct proportion to the number of geo-shape documents.

Common Mistake

[X] Wrong: "Geo queries always run instantly no matter how many shapes there are."

[OK] Correct: Each shape must be checked, so more shapes mean more work and longer query times.

Interview Connect

Understanding how geo queries scale helps you explain performance in real projects and shows you can think about data size effects clearly.

Self-Check

What if we added a spatial index like an R-tree? How would the time complexity change?