Two ways to sort coordinates by geographical distance in Postgres
Tags: postgres, database, math
Published: 2022-08-30 00:08:53

In my last project, I wanted to present to my users a list of places geographically near them. Obviously I wanted the list to be sorted by its distance from their current position, and while it may seems trivial, it’s a complex query since we only store the place coordinates and therefore need to calculate the distance for each user’s coordinates. This is the table we have:

```sql
CREATE TABLE places (
	name TEXT PRIMARY KEY,
	latitude FLOAT8,
	longitude FLOAT8
);
```
In this article, we will cover two methods to calculate this distance. The first one is by **Euclidean distance** which uses the Pythagorean theorem and only accurate for small distances as it based on earth's surface, and the other one is by **Spherical distance**, which uses the Haversine formula and is more accurate as it uses earth's radius and takes into account the curvature of the earth.

##Euclidean distance
As we said, the formula to calculate the distance between two points in a plane is based on the Pythagorean theorem, and luckily it’s quite easy to use. We only need to replace {% katex inline %}(x_1,y_1){% endkatex %} with the user’s coordinates and {% katex inline %}(x_2,y_2){% endkatex %} with the coordinates of each place.

{% katex %}
d = \sqrt {\left( {x_1 - x_2 } \right)^2 + \left( {y_1 - y_2 } \right)^2 }
{% endkatex %}

Now, in order to use it, I created a PostgreSQL function that implements just that. The function takes two parameters, the latitude and longitude of the user, and returns a table with a new column added specifying the distance between the two points, which is the result of the formula above. Please note that the distance is neither in kilometers or miles but in degrees, for another unit we’ll have to use the next formula.

```sql
CREATE OR REPLACE FUNCTION order_by_distance(lat float8, long float8)
RETURNS TABLE (name text, latitude float8, longitude float8, distance float8)
AS $$
SELECT name, latitude, longitude, sqrt((latitude - lat)^2 + (longitude - long)^2) AS distance
FROM places
ORDER BY distance ASC;
$$
LANGUAGE SQL;
```

##Spherical distance
Calculating spherical distance (also known as great-circle distance or orthodromic distance) is a little bit more complicated and requires the use of the Haversine formula with earth radius. 

{% katex %}
d = \frac{6371 \cdot \arccos}{\cos(x_1) \cdot \cos(x_2) \cdot \cos(y_1 - y_2) + \sin(x_1) \cdot \sin(x_2)}
{% endkatex %}

To implements it in a PostgreSQL function we take the same approach as above, with only replacing the formula in use.

```sql
CREATE OR REPLACE FUNCTION order_by_distance(lat float8, long float8)
RETURNS TABLE (name text, latitude float8, longitude float8, distance float8)
AS $$
SELECT name, latitude, longitude, 6371 * acos(cos(radians(lat)) * cos(radians(latitude)) * cos(radians(longitude) - radians(long)) + sin(radians(lat)) * sin(radians(latitude))) AS distance
FROM places
ORDER BY distance ASC;
$$
LANGUAGE SQL;
```

##Use the function
Now, all we need to do is to call our function with the following query (providing the user’s coordinates as arguments, of course). Travel safe!
```sql
SELECT * FROM order_by_distance(40.758896, -73.985130)
```

###For further reading
- Giovanni Dejan, *[The Magic of Haversine Distance](https://medium.com/ninjavan-tech/the-magic-of-haversine-distance-1c4e1641d880)*
- Movable Type Scripts, *[Calculate distance, bearing and more between Latitude/Longitude points](https://www.movable-type.co.uk/scripts/latlong.html)*