Geospatial queries basics in MongoDB - Time & Space Complexity

Time Complexity: Geospatial queries basics

O(log n)

Understanding Time Complexity

When we use geospatial queries in MongoDB, we want to find locations near a point or within an area.

We ask: How does the time to find these locations grow as we have more places stored?

Scenario Under Consideration

Analyze the time complexity of the following geospatial query.

db.places.createIndex({ location: "2dsphere" })

const nearbyPlaces = db.places.find({
  location: {
    $near: {
      $geometry: { type: "Point", coordinates: [ -73.97, 40.77 ] },
      $maxDistance: 5000
    }
  }
})
    

This code finds places within 5 kilometers of a given point using a 2dsphere index.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Searching the geospatial index to find matching locations.
• How many times: The index search visits parts of the tree structure depending on data size and query area.

How Execution Grows With Input

As we add more places, the search looks through more index nodes but not every place.

Input Size (n)	Approx. Operations
10	About 3-5 index checks
100	About 7-10 index checks
1000	About 10-15 index checks

Pattern observation: The search grows slowly, checking only parts of the index, not every place.

Final Time Complexity

Time Complexity: O(log n)

This means the query time grows slowly as the number of places grows, thanks to the index.

Common Mistake

[X] Wrong: "The query checks every place one by one, so it takes longer linearly as data grows."

[OK] Correct: The 2dsphere index lets MongoDB skip many places, searching efficiently like a tree, not a list.

Interview Connect

Understanding how geospatial queries scale shows you know how databases handle location data efficiently.

Self-Check

"What if we removed the 2dsphere index? How would the time complexity change?"

Practice

1. What does the $near operator do in MongoDB geospatial queries?

easy

A. Finds documents with locations closest to a specified point

B. Deletes documents within a certain distance

C. Updates documents with new coordinates

D. Sorts documents alphabetically by location name

Solution

1. Step 1: Understand the purpose of $near

   The $near operator is used to find documents that are geographically close to a given point.

2. Step 2: Compare options with $near functionality

   Only Finds documents with locations closest to a specified point correctly describes finding documents near a location. Other options describe unrelated actions.

3. Final Answer:

   Finds documents with locations closest to a specified point -> Option A

4. Quick Check:

   $near = Finds nearby points [OK]

Hint: Remember: $near finds closest points to a location [OK]

Common Mistakes:

• Thinking $near deletes or updates documents
• Confusing $near with sorting operators
• Assuming $near works without a geospatial index

2. Which of the following is the correct syntax to find documents near a point using $near in MongoDB?

easy

A. { location: { $near: { $geometry: { type: 'Point', coordinates: [-70, 40] } } } }

B. { location: { $near: { $geometry: { type: 'Point', coordinates: [40, -70] } } } }

C. { location: { $near: { $geometry: { type: 'Point', coordinates: [70, 40] } } } }

D. { location: { $near: { $geometry: { type: 'Point', coordinates: [-40, 70] } } } }

Solution

1. Step 1: Recall coordinate order in MongoDB

   Coordinates must be in [longitude, latitude] order, so longitude comes first.

2. Step 2: Check each option's coordinate order

   { location: { $near: { $geometry: { type: 'Point', coordinates: [-70, 40] } } } } uses [-70, 40], which is [longitude, latitude]. Others have latitude first or wrong signs.

3. Final Answer:

   { location: { $near: { $geometry: { type: 'Point', coordinates: [-70, 40] } } } } -> Option A

4. Quick Check:

   Coordinates = [longitude, latitude] [OK]

Hint: Coordinates always [longitude, latitude] in MongoDB [OK]

Common Mistakes:

• Swapping latitude and longitude order
• Using positive latitude as longitude
• Forgetting to use $geometry inside $near

3. Given a collection with a 2dsphere index on location, what will this query return?

{ location: { $near: { $geometry: { type: 'Point', coordinates: [-73.97, 40.77] }, $maxDistance: 500 } } }

medium

A. All documents regardless of location

B. Documents with locations within 500 meters of [-73.97, 40.77]

C. Documents with locations more than 500 meters away

D. Documents with locations exactly at [-73.97, 40.77]

Solution

1. Step 1: Understand $near with $maxDistance

   The query finds documents near the point within the maximum distance specified (500 meters).

2. Step 2: Interpret the query result

   It returns documents whose location is within 500 meters of the given coordinates, not exactly at or beyond that distance.

3. Final Answer:

   Documents with locations within 500 meters of [-73.97, 40.77] -> Option B

4. Quick Check:

   $near + $maxDistance = nearby points within distance [OK]

Hint: Use $maxDistance to limit how far results can be [OK]

Common Mistakes:

• Thinking $maxDistance means exact match
• Assuming it returns points beyond maxDistance
• Ignoring the need for a 2dsphere index

4. You run this query but get an error:

{ location: { $near: { $geometry: { type: 'Point', coordinates: [40.77, -73.97] } } } }

What is the most likely cause?

medium

A. Coordinates are in wrong order; should be [longitude, latitude]

B. Missing $maxDistance parameter

C. The location field is not indexed with 2dsphere

D. The type should be 'Polygon' instead of 'Point'

Solution

1. Step 1: Requirements for $near with $geometry

   The $near operator with $geometry requires a 2dsphere index on the location field.

2. Step 2: Identify the most likely error cause

   Without a 2dsphere index, MongoDB throws an error for geospatial queries like $near. Coordinate order affects results but does not cause an error.

3. Final Answer:

   The location field is not indexed with 2dsphere -> Option C

4. Quick Check:

   $near requires 2dsphere index [OK]

Hint: Always put longitude before latitude in coordinates [OK]

Common Mistakes:

• Swapping latitude and longitude
• Assuming $maxDistance is required
• Confusing geometry types

5. You want to find all restaurants within 1 km of a user's location stored as { type: 'Point', coordinates: [-122.42, 37.77] }. Which query correctly finds these restaurants assuming a 2dsphere index on location?

hard

A. { location: { $near: { $geometry: { type: 'Point', coordinates: [-122.42, 37.77] }, $minDistance: 1000 } } }

B. { location: { $geoWithin: { $centerSphere: [[-122.42, 37.77], 1] } } }

C. { location: { $nearSphere: { $geometry: { type: 'Point', coordinates: [37.77, -122.42] }, $maxDistance: 1000 } } }

D. { location: { $near: { $geometry: { type: 'Point', coordinates: [-122.42, 37.77] }, $maxDistance: 1000 } } }

Solution

1. Step 1: Identify correct coordinate order and operator

   Coordinates must be [longitude, latitude], so [-122.42, 37.77] is correct. The $near operator with $maxDistance finds points within distance.

2. Step 2: Evaluate each option

   { location: { $near: { $geometry: { type: 'Point', coordinates: [-122.42, 37.77] }, $maxDistance: 1000 } } } uses correct coordinates and $near with $maxDistance 1000 meters (1 km). { location: { $geoWithin: { $centerSphere: [[-122.42, 37.77], 1] } } } uses $geoWithin with radius in radians, not meters. { location: { $nearSphere: { $geometry: { type: 'Point', coordinates: [37.77, -122.42] }, $maxDistance: 1000 } } } swaps coordinates. { location: { $near: { $geometry: { type: 'Point', coordinates: [-122.42, 37.77] }, $minDistance: 1000 } } } uses $minDistance which finds points farther than 1 km, not within.

3. Final Answer:

   { location: { $near: { $geometry: { type: 'Point', coordinates: [-122.42, 37.77] }, $maxDistance: 1000 } } } -> Option D

4. Quick Check:

   $near + $maxDistance + correct coords = find nearby points [OK]

Hint: Use $near with $maxDistance and correct coords for nearby search [OK]

Common Mistakes:

• Swapping latitude and longitude
• Using $minDistance instead of $maxDistance
• Confusing meters with radians in $geoWithin