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?

Practice

1.

What is the main difference between geo_point and geo_shape types in Elasticsearch?

easy

A. geo_point stores a single location; geo_shape stores complex shapes like polygons.

B. geo_point stores polygons; geo_shape stores single points.

C. geo_point is used for text data; geo_shape is used for numbers.

D. geo_point stores multiple points; geo_shape stores only lines.

Solution

1. Step 1: Understand geo_point type

   geo_point stores a single geographic location using latitude and longitude coordinates.

2. Step 2: Understand geo_shape type

   geo_shape stores complex geographic shapes such as polygons, lines, or multi-points.

3. Final Answer:

   geo_point stores a single location; geo_shape stores complex shapes like polygons. -> Option A

4. Quick Check:

   Single point vs complex shape = C [OK]

Hint: Remember: point = one spot, shape = many spots connected [OK]

Common Mistakes:

• Confusing points with polygons
• Thinking geo_point stores multiple points
• Mixing data types with geo types

2.

Which of the following is the correct way to define a geo_point field in an Elasticsearch mapping?

{
  "properties": {
    "location": {
      "type": "?"
    }
  }
}

easy

A. "geo_shape"

B. "geo_point"

C. "point_geo"

D. "location_point"

Solution

1. Step 1: Recall Elasticsearch geo types

   Elasticsearch uses "geo_point" as the type name for single geographic points.

2. Step 2: Match the correct type in mapping

   The mapping must specify "type": "geo_point" to store latitude and longitude.

3. Final Answer:

   "geo_point" -> Option B

4. Quick Check:

   Mapping type for point = "geo_point" [OK]

Hint: Use exact type names: geo_point for points [OK]

Common Mistakes:

• Using incorrect type names like geo_shape for points
• Typos in type string
• Confusing field name with type

3.

Given this Elasticsearch document indexed with a geo_point field location:

{ "location": { "lat": 40.7128, "lon": -74.0060 } }

Which query will correctly find documents within 10km of this point?

medium

A. { "range": { "location": { "gte": "10km" } } }

B. { "geo_shape": { "location": { "shape": { "type": "point", "coordinates": [40.7128, -74.0060] }, "relation": "within" } } }

C. { "term": { "location": "40.7128,-74.0060" } }

D. { "geo_distance": { "distance": "10km", "location": { "lat": 40.7128, "lon": -74.0060 } } }

Solution

1. Step 1: Identify correct query type for geo_point

   For geo_point, geo_distance query finds documents within a distance from a point.

2. Step 2: Check query syntax and parameters

   { "geo_distance": { "distance": "10km", "location": { "lat": 40.7128, "lon": -74.0060 } } } uses geo_distance with correct distance and point coordinates.

3. Final Answer:

   { "geo_distance": { "distance": "10km", "location": { "lat": 40.7128, "lon": -74.0060 } } } -> Option D

4. Quick Check:

   geo_distance query = { "geo_distance": { "distance": "10km", "location": { "lat": 40.7128, "lon": -74.0060 } } } [OK]

Hint: Use geo_distance for points, geo_shape for polygons [OK]

Common Mistakes:

• Using geo_shape query on geo_point field
• Wrong coordinate order in geo_shape
• Using term or range queries for geo data

4.

What is wrong with this Elasticsearch mapping for a geo_shape field named area?

{
  "properties": {
    "area": {
      "type": "geo_point"
    }
  }
}

The data to be stored is a polygon shape.

medium

A. The type should be geo_shape to store polygons.

B. The field name area is invalid for geo data.

C. The mapping must include coordinates property.

D. The type geo_point supports polygons by default.

Solution

1. Step 1: Check field type for polygon data

   Polygons require geo_shape type, not geo_point.

2. Step 2: Identify mapping error

   Mapping uses geo_point which only supports single points, so it cannot store polygons.

3. Final Answer:

   The type should be geo_shape to store polygons. -> Option A

4. Quick Check:

   Polygon needs geo_shape type = D [OK]

Hint: Polygons need geo_shape, not geo_point [OK]

Common Mistakes:

• Using geo_point for polygon shapes
• Assuming field name affects type
• Adding coordinates in mapping instead of data

5.

You want to store a city boundary as a polygon and find all points inside it. Which Elasticsearch setup is correct?

{
  "mappings": {
    "properties": {
      "city_boundary": { "type": "?" },
      "user_location": { "type": "?" }
    }
  }
}

Choose the correct types for city_boundary and user_location.

hard

A. "geo_shape" for both city_boundary and user_location

B. "geo_point" for city_boundary and "geo_shape" for user_location

C. "geo_shape" for city_boundary and "geo_point" for user_location

D. "geo_point" for both city_boundary and user_location

Solution

1. Step 1: Determine type for city boundary polygon

   City boundary is a polygon, so it requires geo_shape type.

2. Step 2: Determine type for user location point

   User location is a single point, so it requires geo_point type.

3. Step 3: Match types to fields

   Assign geo_shape to city_boundary and geo_point to user_location.

4. Final Answer:

   "geo_shape" for city_boundary and "geo_point" for user_location -> Option C

5. Quick Check:

   Polygon = geo_shape, Point = geo_point [OK]

Hint: Polygon needs geo_shape; point needs geo_point [OK]

Common Mistakes:

• Swapping types between polygon and point
• Using geo_point for polygons
• Using geo_shape for single points unnecessarily