Geospatial queries in Redis and Memurai

Alexander Gugel on geospatialJune 16, 2021 22 min read

Golden Gate Bridge

Redis can be used for efficiently querying geospatial data. Redis was not designed as a spatial database as it lacks built-in functionality for certain more sophisticated queries that one might be used to in more feature-rich distributions, such as PostGIS. Nonetheless, it presents a more than adequate solution for a wide variety of use cases and can be easily extended when needed.

In this article, we cover the most important geospatial commands and focus on a couple of examples of how those commands can be combined to execute common geospatial queries. We will use Lua, a convenient scripting language that is built into Redis, to achieve this.

Redis is compatible with most POSIX systems, such as Linux, *BSD, and OS X. The application programming interfaces (APIs) and examples provided as part of this article also work under Memurai, an actively maintained Windows port of Redis that has been derived from Microsoft’s OpenTech Redis project. Memurai is available free of charge, with commercial subscription licenses available via memurai.com.

Since many developers, including myself, work with Redis under Windows, we will use the terms Redis and Memurai interchangeably in this article. Memurai’s API is 100% compatible with Redis.

Background

Redis lacks dedicated data types for geospatial objects. Instead, points are stored in sorted sets. The scores of the sets are used for encoding coordinate pairs. This is achieved using a technique called “geohashing.” A point’s geohash is computed based on its geographic coordinates and uniquely identifies a rectangular “cell” in a two-dimensional coordinate system. This hash has several useful properties that make its use for geospatial indices especially appealing. These properties include the following.

  • The hash can be arbitrarily precise. We do not have to worry about this in practice, as Redis automatically computes the geohash and stores an internal representation of it.
  • Nearby points tend to have similar prefixes. In other words, if the geohashes of two different points start with the same prefix, it is safe to assume that they are spatially closer together than if they did not share such a prefix. The longer the prefix, the closer the points will be together. This can be shown to be true, as each character in the geohash uniquely identifies a rectangular cell at varying resolutions.

The idea of using such a hash in combination with sorted sets predates first-class support for geospatial operations, which was introduced in Redis 3.2. However, since those properties have been added, we no longer have to worry about manually computing the aforementioned geohash, although it is still useful to have a high-level understanding of the underlying data model.

Adding points

Now that we have familiarized ourselves with Redis’ internal representation of geospatial objects, it is time to take a look at the actual API that enables the use of those features.

The GEOADD command can be used for adding points to the provided key. It expects the latitude, longitude, and name of a point as arguments. Redis then computes the geohash based on the coordinates that were provided:

127.0.0.1:6379> GEOADD cities -122.34 47.61 Seattle
(integer) 1

The return value “1” indicates that the item has been added successfully.

As mentioned earlier, geospatial indices are based on sorted sets. Consequently, we can use the ZRANGE commands to query the newly added item:

127.0.0.1:6379> ZRANGE cities 0 -1 WITHSCORES
1) "Seattle"
2) "1558507288382415"

The returned score is used internally by Redis to facilitate geospatial queries. It is based on the point’s geohash, and we cannot override it.

If we want to inspect the item’s real geohash, we can use the built-in GEOHASH command:

127.0.0.1:6379> GEOHASH cities Seattle
1) "c23nb54sr70"

The “c23nb54sr70” value is our point’s geohash.

To read back the original set of coordinates that were used for adding the point, we can use the GEOPOS command:

127.0.0.1:6379> GEOPOS cities Seattle
1) 1) "-122.33999758958816528"
   2) "47.61000085169597185"

Notice that we provided –122.34 as longitude and 47.61 as latitude when calling GEOADD, but received –122.33999758958816528 and 47.61000085169597185, respectively, in return.

This is an unfortunate consequence of Redis using a 52-bit geohash to store the coordinates: Redis does not store the raw set of coordinates that we provide, but instead decodes the internally stored geohash to generate a GEOPOS response.

If one has a requirement to store an exact set of coordinates, it may have to be done separately. One can think of GEOADD as a way to add points to a geospatial index, which may not be 100% precise. Querying points within a given radius To query points that are within a given radius of the provided coordinate pair, we can use the GEOSEARCH command.

To demonstrate this, we will first add a number of major USA cities to our “cities” key. The GEOADD command can be used for adding multiple points in bulk:

127.0.0.1:6379> GEOADD cities -74.0059413 40.7127837 "New York" -118.2436849 34.0522342 "Los Angeles" -87.6297982 41.8781136 "Chicago" -95.3698028 29.7604267 "Houston" -75.1652215 39.9525839 "Philadelphia" -112.0740373 33.4483771 "Phoenix" -98.49362819999999 29.4241219 "San Antonio" -117.1610838 32.715738 "San Diego" -96.79698789999999 32.7766642 "Dallas" -121.8863286 37.3382082 "San Jose" -97.7430608 30.267153 "Austin" -86.158068 39.768403 "Indianapolis" -81.65565099999999 30.3321838 "Jacksonville" -122.4194155 37.7749295 "San Francisco" -82.99879419999999 39.9611755 "Columbus" -80.8431267 35.2270869 "Charlotte" -97.3307658 32.7554883 "Fort Worth" -83.0457538 42.331427 "Detroit" -106.4424559 31.7775757 "El Paso" -90.0489801 35.1495343 "Memphis" -122.3320708 47.6062095 "Seattle" -104.990251 39.7392358 "Denver" -77.0368707 38.9071923 "Washington" -71.0588801 42.3600825 "Boston" -86.7816016 36.1626638 "Nashville-Davidson" -76.6121893 39.2903848 "Baltimore" -97.5164276 35.4675602 "Oklahoma City" -85.7584557 38.2526647 "Louisville/Jefferson County" -122.6764816 45.5230622 "Portland" -115.1398296 36.1699412 "Las Vegas" -87.9064736 43.0389025 "Milwaukee" -106.6055534 35.0853336 "Albuquerque" -110.926479 32.2217429 "Tucson" -119.7725868 36.7468422 "Fresno" -121.4943996 38.5815719 "Sacramento" -118.1937395 33.7700504 "Long Beach" -94.5785667 39.0997265 "Kansas City" -111.8314724 33.4151843 "Mesa" -75.97798499999999 36.8529263 "Virginia Beach" -84.3879824 33.7489954 "Atlanta" -104.8213634 38.8338816 "Colorado Springs" -95.99798829999999 41.2523634 "Omaha" -78.6381787 35.7795897 "Raleigh" -80.1917902 25.7616798 "Miami" -122.2711137 37.8043637 "Oakland" -93.2650108 44.977753 "Minneapolis" -95.99277500000001 36.1539816 "Tulsa" -81.6943605 41.49932 "Cleveland" -97.336111 37.688889 "Wichita" -97.10806559999999 32.735687 "Arlington"
(integer) 50

Source: https://jsfiddle.net/7a9xfnLw/3/

In order to query points that are within a 500 km radius of Washington, we can use the GEOSEARCH command:

127.0.0.1:6379> GEOSEARCH cities FROMMEMBER Washington BYRADIUS 500 km WITHCOORD WITHDIST WITHHASH
1) 1) "Washington"
   2) "0.0000"
   3) (integer) 1790437241089913
   4) 1) "-77.03687041997909546"
      2) "38.90719290381756679"
2) 1) "Baltimore"
   2) "56.2166"
   3) (integer) 1790521436838452
   4) 1) "-76.61219090223312378"
      2) "39.29038444452294954"
3) 1) "Philadelphia"
   2) "198.4242"
   3) (integer) 1791689799529163
   4) 1) "-75.16521960496902466"
      2) "39.95258288212141196"
4) 1) "New York"
   2) "327.6765"
   3) (integer) 1791873974571312
   4) 1) "-74.00594204664230347"
      2) "40.71278377862454789"
5) 1) "Raleigh"
   2) "375.5669"
   3) (integer) 1786797495908595
   4) 1) "-78.63817602396011353"
      2) "35.77959032642458936"
6) 1) "Virginia Beach"
   2) "246.6698"
   3) (integer) 1787238858478694
   4) 1) "-75.97798258066177368"
      2) "36.85292560551014418"
7) 1) "Cleveland"
   2) "489.4351"
   3) (integer) 1784970484826011
   4) 1) "-81.69436007738113403"
      2) "41.49932042797322396"

Notice that for each matching city, Redis returns the name of the member (name of the city), the distance to the center of the circle (Washington), the geohash, and the coordinate pair.

Source: https://jsfiddle.net/7a9xfnLw/4/

We can also query points that are within a given distance from an arbitrary point, instead of using a preexisting member of the set:

127.0.0.1:6379> GEOSEARCH cities FROMLONLAT -77.0368707 38.9071923 BYRADIUS 500 km WITHCOORD WITHDIST WITHHASH
1) 1) "Washington"
   2) "0.0000"
   3) (integer) 1790437241089913
   4) 1) "-77.03687041997909546"
      2) "38.90719290381756679"
2) 1) "Baltimore"
   2) "56.2166"
   3) (integer) 1790521436838452
   4) 1) "-76.61219090223312378"
      2) "39.29038444452294954"
3) 1) "Philadelphia"
   2) "198.4242"
   3) (integer) 1791689799529163
   4) 1) "-75.16521960496902466"
      2) "39.95258288212141196"
4) 1) "New York"
   2) "327.6765"
   3) (integer) 1791873974571312
   4) 1) "-74.00594204664230347"
      2) "40.71278377862454789"
5) 1) "Raleigh"
   2) "375.5669"
   3) (integer) 1786797495908595
   4) 1) "-78.63817602396011353"
      2) "35.77959032642458936"
6) 1) "Virginia Beach"
   2) "246.6698"
   3) (integer) 1787238858478694
   4) 1) "-75.97798258066177368"
      2) "36.85292560551014418"
7) 1) "Cleveland"
   2) "489.4351"
   3) (integer) 1784970484826011
   4) 1) "-81.69436007738113403"
      2) "41.49932042797322396"


Querying points within a given bounding box

GEOSEARCH can also be used to query points within a given bounding box. This can be achieved using the BYBOX argument:

127.0.0.1:6379> GEOSEARCH cities FROMLONLAT -77.0368707 38.9071923 BYBOX 800 800 km WITHCOORD WITHDIST WITHHASH
1) 1) "Washington"
   2) "0.0001"
   3) (integer) 1790437241089913
   4) 1) "-77.03687041997909546"
      2) "38.90719290381756679"
2) 1) "Baltimore"
   2) "56.2167"
   3) (integer) 1790521436838452
   4) 1) "-76.61219090223312378"
      2) "39.29038444452294954"
3) 1) "Philadelphia"
   2) "198.4243"
   3) (integer) 1791689799529163
   4) 1) "-75.16521960496902466"
      2) "39.95258288212141196"
4) 1) "New York"
   2) "327.6765"
   3) (integer) 1791873974571312
   4) 1) "-74.00594204664230347"
      2) "40.71278377862454789"
5) 1) "Raleigh"
   2) "375.5668"
   3) (integer) 1786797495908595
   4) 1) "-78.63817602396011353"
      2) "35.77959032642458936"
6) 1) "Virginia Beach"
   2) "246.6697"
   3) (integer) 1787238858478694
   4) 1) "-75.97798258066177368"
      2) "36.85292560551014418"

Source: https://jsfiddle.net/7a9xfnLw/7/

“BYBOX 800 800 km” describes an 800  800 km bounding box. Redis supports units other than kilometers (km), such as meters (m), feet (ft), and miles (mi).

Advanced queries

Redis has built-in commands for querying points within a given radius or bounding box, as demonstrated in the previous sections. However, it does not have support for more complex geospatial queries or a notion of more complex spatial objects, such as polygons or lines.

We generally have two options when it comes to executing complex geospatial queries.

1. Do additional client-side filtering and processing. For example, if we were to determine the points that are within a given polygon, we could start by doing some coarse filtering using GEOSEARCH in Redis itself, followed by some additional filtering on the client side. This leads to some over-fetching of data and can incur a certain performance penalty due to additional round trips. 2. Extend Redis by uploading custom scripts. Redis has built-in support for Lua, a lightweight, high-performance scripting language that is especially suited for embedded use cases. We can upload custom Lua scripts to do additional filtering and processing directly on the server side. Furthermore, the uploaded scripts are client-agnostic, so if we query Redis using different clients, we do not have to repeatedly implement filtering logic for each use case, but we can instead leverage a single script that only needs to be uploaded once to the server.

In the following sections, we are mostly going to focus on the second approach. We will show how Lua can be used for implementing more sophisticated geospatial queries for which Redis does not have built-in support. Querying points within a given polygon

Overview

Suppose we are given a polygon consisting of four points, and we want to execute a geospatial query in order to identify all specific points of interest that are within the provided polygon (red).

Source: https://jsfiddle.net/7a9xfnLw/10/

One approach that we could start with is to construct a bounding box (blue) around the polygon.

Source: https://jsfiddle.net/7a9xfnLw/11/

This would allow us to filter out the vast majority of points that are certainly not within the given polygon. However, it is not perfect and some points would still be included, as they are within the bounding box, but not within the polygon.

For example, Raleigh is within the bounding box, but not within the polygon.

Thus, we need to do some additional filtering of the points that fall within our bounding box.

One approach to achieving this is via raycasting. The general approach is as follows.

  1. We pick a random point X. We call this the “test point.” Its coordinates are not particularly important and can be selected at random. This point must be different from the points that we want to check.
  2. For every point P that we want to check, we construct a line between P and X. This line is also called a “ray,” thus the name “raycasting.” We count the number of intersections between the ray and the polygon’s edges.
  3. If the number of intersections is odd, it means the point is within the provided polygon. If the number of intersections is even, it indicates that the point is outside.

We can now implement the aforementioned in Lua. Getting started with Lua Our script will accept the key of the sorted set containing the points that we want to filter, as well as a variable number of arguments denoting the points that constitute the polygon:

EVAL {script} cities -74.0059413 40.7127837 -82.99879419999999 39.9611755 -84.3879824 33.7489954 -75.97798499999999 36.8529263

Redis’ EVAL command can be used for evaluating arbitrary Lua scripts. This is how we are actually going to upload our script to the server and execute it.

Especially during development, it is rather inconvenient to pass the entire multiple-line spanning script as a command argument.

Therefore, we will create a new file called pip.lua (“point in polygon”) to store our script. We can evaluate our script using the redis-cli’s --eval flag:

% redis-cli --eval pip.lua cities -74.0059413 40.7127837 -82.99879419999999 39.9611755 -84.3879824 33.7489954 -75.97798499999999 36.8529263
(nil)

For now, we will simply validate and print the coordinate pairs that were provided:

local key = KEYS[1]

-- 1. Validate provided arguments

if (table.getn(KEYS) - 1) == 0 or (table.getn(KEYS) - 1) % 2 ~= 0 then
    return redis.error_reply("Unexpected number of arguments")
end

-- 2. Extract polygon points

local polygon_points = {}

for i = 2, table.getn(KEYS), 2 do
    local lng = tonumber(KEYS[i])
    local lat = tonumber(KEYS[i+1])
    table.insert(polygon_points, {lng, lat})
end

for _, point in pairs(polygon_points) do
    print("latitude", point[1], "longitude", point[2])
end
pip.lua
latitude    -74.0059413    longitude    40.7127837
latitude    -82.9987942    longitude    39.9611755
latitude    -84.3879824    longitude    33.7489954
latitude    -75.977985    longitude    36.8529263
Output (redis-server)


Coarse filtering

We now construct an axis-aligned bounding box (AABB) around the polygon (shown in blue in the figure above). This can be achieved by iterating over the polygon points and identifying the leftmost, rightmost, top, and bottom edge of the geometry:

-- 3. Compute axis-aligned minimum bounding box (AABB)

-- longitude range: -180 +180
-- latitude range: -90 +90

local max_lng = polygon_points[1][1]
local min_lng = polygon_points[1][1]

local max_lat = polygon_points[1][2]
local min_lat = polygon_points[1][2]

for _, point in pairs(polygon_points) do
    local lng = point[1]
    local lat = point[2]

    max_lng = math.max(max_lng, lng)
    min_lng = math.min(min_lng, lng)

    max_lat = math.max(max_lat, lat)
    min_lat = math.min(min_lat, lat)
end

print("max_lng", max_lng)
print("min_lng", min_lng)
print("max_lat", max_lat)
print("max_lat", max_lat)
pip.lua (continued)
max_lng    -74.0059413
min_lng    -84.3879824
max_lat    40.7127837
max_lat    40.7127837
Output (redis-server)

At this point, we can trivially identify the midpoint (red marker) of the bounding box (blue).

Source: https://jsfiddle.net/6hso4cyx/2/

-- 4. Compute midpoint

local mid_lng = min_lng + (max_lng - min_lng) * .5
local mid_lat = min_lat + (max_lat - min_lat) * .5

print("mid_lng", mid_lng)
print("mid_lat", mid_lat)
pip.lua (continued)
mid_lng    -79.19696185
mid_lat    37.23088955
Output (redis-server)

We then need to compute the dimensions of the blue rectangle. This is because Redis’ GEOSEARCH command can be used for querying points within a given bounding box, but it expects both the midpoint and dimensions of the bounding box.

Computing the “dimensions” of a rectangle on a sphere is slightly more complicated than it seems. Technically, what we are really looking for is the great-circle distance between points on a sphere.

A common way of calculating such a distance is to use the haversine formula. We will not go into detail here as to why this formula works. For now, it is important to remember that we need to calculate the distances between the sides of the bounding box:

-- 5. Compute dimensions

local function haversine (lat_a, lng_a, lat_b, lng_b)
    -- convert to radians
    local phi_1 = lat_a * math.pi / 180
    local phi_2 = lat_b * math.pi / 180

    local delta_phi = (lat_b - lat_a) * math.pi / 180
    local delta_lambda = (lng_b - lng_a) * math.pi / 180
    local a = math.sin(delta_phi/2) * math.sin(delta_phi/2) + math.cos(phi_1) * math.cos(phi_2) * math.sin(delta_lambda/2) * math.sin(delta_lambda/2)
    local c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    return 6371e3 * c
end

local width = haversine(max_lat, min_lng, max_lat, max_lng)
local height = haversine(min_lat, min_lng, max_lat, min_lng)

print("width", width)
print("height", height)
pip.lua (continued)
width    874535.06964028
height    774337.92918674
Output (redis-server)

When we have both the midpoint and dimensions of the rectangle, we can do some initial coarse filtering to identify all points that are within the bounding box (blue).

As we learned earlier, we can use the GEOSEARCH command to construct such a query. We can arbitrarily call “native” Redis commands from Lua scripts using the redis.call function:

-- 6. Query points within AABB

local geosearch_results = redis.call(
    "GEOSEARCH",
    key,
    "FROMLONLAT",
    mid_lng,
    mid_lat,
    "BYBOX",
    width,
    height,
    "m",
    "WITHCOORD")

local candidates = {}

for i = 1, table.getn(geosearch_results), 1 do
    local member = geosearch_results[i][1]
    local lng = tonumber(geosearch_results[i][2][1])
    local lat = tonumber(geosearch_results[i][2][2])
    table.insert(candidates, {member, lng, lat})
end

for i = 1, table.getn(candidates), 1 do
    print(candidates[i][1], candidates[i][2], candidates[i][3])
end
pip.lua (continued)
Columbus    -82.99879342317581177    39.96117558685156013
Charlotte    -80.84312885999679565    35.2270870164388441
Washington    -77.03687041997909546    38.90719290381756679
Baltimore    -76.61219090223312378    39.29038444452294954
Philadelphia    -75.16521960496902466    39.95258288212141196
Raleigh    -78.63817602396011353    35.77959032642458936
Virginia Beach    -75.97798258066177368    36.85292560551014418
Output (redis-server)

The “candidates” variable contains all the points of interest that are within the blue bounding box. However, notice that it also contains Raleigh, which is within the AABB, but not within the polygon. Raycasting We need to do some additional filtering in order to exclude points that are not within the polygon. This is where raycasting comes into play.

It entails casting a “ray” through each point that we need to test and counting the number of intersections with the vertices of the polygon. Doing so is considerably more expensive than the coarse filtering we did earlier. Thus, it is essential to first exclude points that are not within the specified bounding box:

-- 7. Ray casting

local results = {}

for c = 1, table.getn(candidates), 1 do
    local candidate = candidates[c]

    local is_odd = false
    local j = table.getn(polygon_points)

    for i = 1, table.getn(polygon_points), 1 do
        if ((polygon_points[i][2]>candidate[3]) ~= (polygon_points[j][2]>candidate[3])) and
            candidate[2] < (polygon_points[j][1]-polygon_points[i][1]) * (candidate[3]-polygon_points[i][2]) / (polygon_points[j][2]-polygon_points[i][2]) + polygon_points[i][1] then
            is_odd = not is_odd
        end
        j = i
    end

    if is_odd then
        table.insert(results, candidate)
    end
end

for i = 1, table.getn(results), 1 do
    print(results[i][1], results[i][2], results[i][3])
end
pip.lua (continued)
Charlotte    -80.843128859997    35.227087016439
Washington    -77.036870419979    38.907192903818
Baltimore    -76.612190902233    39.290384444523
Philadelphia    -75.165219604969    39.952582882121
Output (redis-server)

The abovementioned implementation is based on Randolph Franklin’s “Point Inclusion in Polygon Test,” which is a common way of implementing queries related to point inclusions in polygons. Putting it all together All that remains to be done now is to return the results:

local key = KEYS[1]

-- 1. Validate provided arguments

if (table.getn(KEYS) - 1) == 0 or (table.getn(KEYS) - 1) % 2 ~= 0 then
    return redis.error_reply("Unexpected number of arguments")
end

-- 2. Extract polygon points

local polygon_points = {}

for i = 2, table.getn(KEYS), 2 do
    local lng = tonumber(KEYS[i])
    local lat = tonumber(KEYS[i+1])
    table.insert(polygon_points, {lng, lat})
end

for _, point in pairs(polygon_points) do
    print("latitude", point[1], "longitude", point[2])
end

-- 3. Compute axis-aligned minimum bounding box (AABB)
-- longitude range: -180 +180
-- latitude range: -90 +90

local max_lng = polygon_points[1][1]
local min_lng = polygon_points[1][1]

local max_lat = polygon_points[1][2]
local min_lat = polygon_points[1][2]

for _, point in pairs(polygon_points) do
    local lng = point[1]
    local lat = point[2]

    max_lng = math.max(max_lng, lng)
    min_lng = math.min(min_lng, lng)

    max_lat = math.max(max_lat, lat)
    min_lat = math.min(min_lat, lat)
end

print("max_lng", max_lng)
print("min_lng", min_lng)
print("max_lat", max_lat)
print("max_lat", max_lat)

-- 4. Compute midpoint

local mid_lng = min_lng + (max_lng - min_lng) * .5
local mid_lat = min_lat + (max_lat - min_lat) * .5

print("mid_lng", mid_lng)
print("mid_lat", mid_lat)

-- 5. Compute dimensions

local function haversine (lat_a, lng_a, lat_b, lng_b)
    -- convert to radians
    local phi_1 = lat_a * math.pi / 180
    local phi_2 = lat_b * math.pi / 180

    local delta_phi = (lat_b - lat_a) * math.pi / 180
    local delta_lambda = (lng_b - lng_a) * math.pi / 180
    local a = math.sin(delta_phi/2) * math.sin(delta_phi/2) + math.cos(phi_1) * math.cos(phi_2) * math.sin(delta_lambda/2) * math.sin(delta_lambda/2)
    local c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    return 6371e3 * c
end

local width = haversine(max_lat, min_lng, max_lat, max_lng) * 1.05
local height = haversine(min_lat, min_lng, max_lat, min_lng) * 1.05

print("width", width)
print("height", height)

-- 6. Query points within AABB

local geosearch_results = redis.call(
    "GEOSEARCH",
    key,
    "FROMLONLAT",
    mid_lng,
    mid_lat,
    "BYBOX",
    width,
    height,
    "m",
    "WITHCOORD")

local candidates = {}

for i = 1, table.getn(geosearch_results), 1 do
    local member = geosearch_results[i][1]
    local lng = tonumber(geosearch_results[i][2][1])
    local lat = tonumber(geosearch_results[i][2][2])
    table.insert(candidates, {member, lng, lat})
end

for i = 1, table.getn(candidates), 1 do
    print(candidates[i][1], candidates[i][2], candidates[i][3])
end

-- 7. Ray casting

local results = {}

for c = 1, table.getn(candidates), 1 do
    local candidate = candidates[c]

    local is_odd = false
    local j = table.getn(polygon_points)

    for i = 1, table.getn(polygon_points), 1 do
        if ((polygon_points[i][2]>candidate[3]) ~= (polygon_points[j][2]>candidate[3])) and
            candidate[2] < (polygon_points[j][1]-polygon_points[i][1]) * (candidate[3]-polygon_points[i][2]) / (polygon_points[j][2]-polygon_points[i][2]) + polygon_points[i][1] then
            is_odd = not is_odd
        end
        j = i
    end

    if is_odd then
        table.insert(results, candidate)
    end
end

for i = 1, table.getn(results), 1 do
    print(results[i][1], results[i][2], results[i][3])
end

return results
pip.lua (continued)

We can continue calling our script using --eval for debugging purposes:

% ./src/redis-cli --eval pip.lua cities -74.0059413 40.7127837 -82.99879419999999 39.9611755 -84.3879824 33.7489954 -75.97798499999999 36.8529263
1) 1) "Charlotte"
   2) (integer) -80
   3) (integer) 35
2) 1) "Washington"
   2) (integer) -77
   3) (integer) 38
3) 1) "Baltimore"
   2) (integer) -76
   3) (integer) 39
4) 1) "Philadelphia"
   2) (integer) -75
   3) (integer) 39

However, ideally we would want to upload our script only once. Currently, we are uploading the entire source code of our custom command on every call. This is quite inefficient.

In order to upload our script only once, we can use Redis’ SCRIPT LOAD command, which returns the SHA1 digest of the script. This checksum can then be used subsequently to call our script:

[email protected] redis % ./src/redis-cli SCRIPT LOAD "$(cat pip.lua)"
"d7ee2b921f9d4d4d86b3d51e2b1a58f40a71ca40"

EVALSHA is otherwise equivalent to the EVAL command that we used above:

127.0.0.1:6379> EVALSHA d7ee2b921f9d4d4d86b3d51e2b1a58f40a71ca40 9 cities -74.0059413 40.7127837 -82.99879419999999 39.9611755 -84.3879824 33.7489954 -75.97798499999999 36.8529263
1) 1) "Charlotte"
   2) (integer) -80
   3) (integer) 35
2) 1) "Washington"
   2) (integer) -77
   3) (integer) 38
3) 1) "Baltimore"
   2) (integer) -76
   3) (integer) 39
4) 1) "Philadelphia"
   2) (integer) -75
   3) (integer) 39


Conclusion

In this article, we have demonstrated how Redis can be used for storing geospatial data. Redis uses sorted sets to store points but lacks dedicated data types for geometries. However, both Redis and Memurai are more than adequate for geofencing applications or other types of use cases that require geospatial queries. Their built-in support for Lua can be used for implementing more sophisticated queries, such as point in polygon tests, while still benefiting from the performance benefits that result from using an established in-memory store.

Golden Gate Bridge