当前位置：网站首页>"Find nearby shops" | Geohash+MySQL realizes geographic location filtering

"Find nearby shops" | Geohash+MySQL realizes geographic location filtering

2022-08-01 15:01:00 【InfoQ】

一、背景

我们的⼀an early item⽬使⽤了MyBatis-Plus+MySQL,新⼀The function point of filtering the nearest store list by geographical location has been added to the current demand.Since this requirement is relatively simple,因此我们考虑在MySQLImplement geographic filtering,并进⾏explored the following.

二、方案一：MySQL使⽤GEOMETRY/POINTA field of type stores the geographic location

由于MySQL5.6and later versions are basic⽀Holds the space position to expand,对⼏What object to pick⽤WKB格式存储,WKTformat exhibition⽰.因此我们⾸先考虑在MySQL中使⽤ GEOMETRY/POINT A field of type stores the geographic location（坐标）进⽽使⽤MySQLThe provided spatial index comes in⾏Geographical filtering.

MySQL中GEOMETRY/POINTThe encoding format of the field of type is WKB (Well-known Binary)：

可以通过WKT值来创建GEOMETRY/POINT类型的值

used in our code⽤The coordinates can be easily converted to WKT格式,然后在WKT和WKB之间进⾏转换即可.

MySQL使⽤如下⽅式转换WKT和WKB：

衍⽣问题让MyBatis-Plus⽀持GEOMETRY/POINT类型

如果我们使⽤MyBatis,那么直接在mapper⾥的SQL语句中使⽤These conversion functions are sufficient,But our items⽬中使⽤了MyBatis-Plus,尽量不⼿⼯编写SQL.So hope to make itMyBatis-Plus⽀Hold pair coordinates and GEOMETRY/POINT类型进⾏转换.我们进⾏了⼀些尝试,并最终得到了⽐more appropriate solution⽅案.

2.1尝试⼀ 

使⽤MyBatis TypeHandler Combine the coordinates and WKTFormat string in⾏转

因为MySQL⽀Insert this way of writing⼊/更新GEOMETRY/POINT类型的字段

INSERT INTO t1 (pt_col) VALUES(Point(1,2));

既然MyBatis 可以扩展TypeHandler.Then we can respond⽤The coordinate type in is converted toWKT格式的字符串,传到MySQLshould be able to be processed.但是实际上这⼀思路⽆法成功,因为在JDBCAn error will be reported in the driver⽆法将String转换成为GEOMETRY/POINT类型.

2.2尝试二

使⽤MyBatis-Plus Interceptor机制,改写SQL进⾏转换

例如：

/*应用中使用的SQL为 */
update `t_table` set `geom`=?
/* 在MyBatis-Plus Interceptor 把上面的SQL改写成 */
update `t_table` set `geom`=geomfromtext(?)

这个思路⼤can be achieved.但是实现起来⽐较⿇烦,有以下问题：

• On the fields that need to be converted, you need to pass annotations or other⽅式进⾏标记

• 需要解析SQL

• Need to deal with the details of the field name camel case to underscore

• 处理不了GEOMETRY/POINTThere are complex operationsSQL

• 查询,更新SQL需要分开处理

• 如果有符合条件的SQLI don't want to enter⾏改写,还需要特殊处理

因此这个⽅The case was dropped.

2.3尝试三

使⽤MyBatis TypeHandler 和JTS 将坐标转换为WKB编码的字节

通过引⼊jts-core,我们可以在应⽤directly convert the coordinates to WKBThe encoded bytes are then passed to MySQL,也可以从MySQl中解读WKBEncoded byte array and decoded to coordinates.

import org.apache.ibatis.type.BaseTypeHandler;
import org.apache.ibatis.type.JdbcType;

import java.sql.CallableStatement;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;

/**
 * @author shishi on 21/3/22
 */
public class GeoPointHandler extends BaseTypeHandler<GeoPoint> {

 @Override
 public void setNonNullParameter(PreparedStatement ps, int i, GeoPoint geoPoint, JdbcType jdbcType) throws SQLException {
 ps.setBytes(i, Converter.geoPointToBytes(geoPoint));
 }

 /**
 * Gets the nullable result.
 *
 * @param rs the rs
 * @param columnName Column name, when configuration <code>useColumnLabel</code> is <code>false</code>
 * @return the nullable result
 * @throws SQLException the SQL exception
 */
 @Override
 public GeoPoint getNullableResult(ResultSet rs, String columnName) throws SQLException {
 return Converter.geoPointFromBytes(rs.getBytes(columnName));
 }

 @Override
 public GeoPoint getNullableResult(ResultSet rs, int columnIndex) throws SQLException {
 return Converter.geoPointFromBytes(rs.getBytes(columnIndex));
 }

 @Override
 public GeoPoint getNullableResult(CallableStatement cs, int columnIndex) throws SQLException {
 return Converter.geoPointFromBytes(cs.getBytes(columnIndex));
 }
}

import lombok.extern.slf4j.Slf4j;
import org.locationtech.jts.geom.*;
import org.locationtech.jts.geom.impl.CoordinateArraySequence;
import org.locationtech.jts.geom.impl.CoordinateArraySequenceFactory;
import org.locationtech.jts.io.*;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;

@Slf4j
public class Converter {

 private static final GeometryFactory GEOMETRY_FACTORY =
 new GeometryFactory(new PrecisionModel(), 0, CoordinateArraySequenceFactory.instance());


 private Converter() {
 }

 /**
 * 通过jts,读取数据库中的geometryobject and converted toGeoPoint
 *
 * @param bytes Raw stream in database
 * @return GeoPoint对象
 */
 public static GeoPoint geoPointFromBytes(byte[] bytes) {
 if (bytes == null) {
 return null;
 }

 try (ByteArrayInputStream inputStream = new ByteArrayInputStream(bytes)) {
 byte[] sridBytes = new byte[4];
 inputStream.read(sridBytes);
 int srid = ByteOrderValues.getInt(sridBytes, ByteOrderValues.LITTLE_ENDIAN);

 GeometryFactory geometryFactory = GEOMETRY_FACTORY;
 if (srid != Constants.SPATIAL_REFERENCE_ID) {
 log.error(&quot;SRID different between database and application, db:{}, app:{}&quot;, srid, Constants.SPATIAL_REFERENCE_ID);
 geometryFactory = new GeometryFactory(new PrecisionModel(), srid, CoordinateArraySequenceFactory.instance());
 }

 WKBReader wkbReader = new WKBReader(geometryFactory);
 Geometry geometry = wkbReader.read(new InputStreamInStream(inputStream));
 Point point = (Point) geometry;
 return new GeoPoint(point.getX(), point.getY());
 } catch (Exception e) {
 log.error(&quot;failed when reading points from database.&quot;, e);
 return null;
 }
 }

 /**
 * 通过jts,将GeoPointObjects are converted into data streams that the database can recognize
 *
 * @param geoPoint 原始GeoPoint对象
 * @return mybatis可识别的byte[]
 */
 public static byte[] geoPointToBytes(GeoPoint geoPoint) {
 if (geoPoint == null) {
 return new byte[0];
 }

 CoordinateArraySequence arraySequence = new CoordinateArraySequence(
 new Coordinate[]{new Coordinate(geoPoint.getX(), geoPoint.getY())}, 2);
 Point point = new Point(arraySequence, GEOMETRY_FACTORY);

 try (ByteArrayOutputStream outputStream = new ByteArrayOutputStream()) {
 byte[] sridBytes = new byte[4];
 ByteOrderValues.putInt(point.getSRID(), sridBytes, ByteOrderValues.LITTLE_ENDIAN);
 outputStream.write(sridBytes);

 WKBWriter wkbWriter = new WKBWriter(2, ByteOrderValues.LITTLE_ENDIAN);
 wkbWriter.write(point, new OutputStreamOutStream(outputStream));
 return outputStream.toByteArray();
 } catch (Exception e) {
 log.error(&quot;failed when writing points to database.&quot;, e);
 return new byte[0];
 }
 }


}

Option 1 flaws

由于MySQLThe spatial index function has the following flaws,led us to finally choose to give up⽅案⼀⾃⼰实现Geohash.

三、方案二：⾃⼰实现Geohash

Geohash算法把⼀A space point is converted to ⼀a hash string.This hash string is required to be full⾜性质：The prefix matches the same dot,must be close.This can be done when querying,缩⼩查询范围.

We are responding⽤层⾯实现Geohash算法,Calculate geographic locationGeohash的值,存储在MySQL中,这样在MySQL中对Geohash进⾏字符串⽐Compare to filter geographic locations.

Geohash算法

1. 使⽤⼆分法,Draw the coordinate system out of a rectangle⽹格,将经度、Latitude is converted to ⼆进制字符串.例如,⼀个POINT(70, 10),第⼀步,70在(-180, 180)belongs to comparison⼤的⼀半,取1;10在(-90, 90)belongs to comparison⼤的⼀半,取1.第⼆步,70在(0, 180）belongs to comparison⼩的⼀半,取0;10在(0, 90)belongs to comparison⼩的⼀半,取0.第三步,70在(0, 90）belongs to comparison⼤的⼀半,取1;10在(0, 45)belongs to comparison⼩的⼀半,取0.第四步,70在(45, 90）belongs to comparison⼤的⼀半,取1;10在(0, 22.5)belongs to comparison⼩的⼀半,取0.This gives four significant digits,经度1011,纬度1000.可以看到,Four significant digits are equivalent to ±22.5经度±5.625纬度.

2.使⽤⽪Arno curve dimensionality reduction.Misalignment can be merged.1011、1000 -> 11001010,Take from longitude1,Take from latitude1;Then take it from longitude0,Take from latitude0;Take from longitude1,Take from latitude0;Take from longitude1,Take from latitude0.这样得到⼀个⼆进制字符串.

3.使⽤base32算法,每5位转化为⼀个char.使⽤的字符为0-9、b-z（去掉a, i, l, o）.

4.得到的就是MySQL默认的Geohash了,等价于

st_Geohash(`geom`, i)

注意第⼆个参数iA significant number representing the final result,最常⽤的i=8,相当于8*5/2=20Number of significant digits of latitude and longitude.

Geohash的应⽤和问题

Geohash的特征是,If before⼲位有效字符,Represents the included object⼀个更⼤的区域范围.事实上,每少2位有效字符,都相当于2*5/2=5次⼆分,也就是2^5=32倍⼤⼩的⼀个区域.So when you need to query geographic locations near a given location,使⽤Geohash可以快速定位到⼀个范围内.

不过,Geohash同时有⼀个明显的问题.

如图,Suppose we wish to find the distancea最近的点.Suppose we filter,使⽤out of order⼦5作为Geohash匹配,Then the closest value we found would bee.But the actual closest point,Should be next doorb点.怎么办呢？

最容易想到的⽅The law is expanded again⼤matching grid.但问题是,⽪The Arno curve has abrupt points

对于某⼀个特定的点,The expanded range is only guaranteed to wrap it⾃⼰,⽆method to determine how far to expand to include all nine adjacent squares.例如：The picture above is for the grid⼦1100,Either expansion⼤为110、11哪怕是1,都⽆to cover the left side0110格.

因此,需要⼿Move around to get around⼋个格⼦的匹配信息,并使⽤OR做匹配.这⼀It is not difficult to achieve,Because the adjacent grid is exactly its horizontal and vertical coordinates±1即可.

例如,0110 -> (01, 10),1100 -> (10, 10),01 + 1 = 10.获得之后,使⽤or匹配即可.

给⼀paragraph specificGeohash算法实现：

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

public class GeohashUtils {
 /**
 * 一共八位,每位通过base32编码,实际相当于40位,Latitude and longitude20位
 */
 private static final int GEO_HASH_MAX_LENGTH = 8 * 5;
 private static final char[] BASE32_DIGITS = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
 '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
 private static final HashMap<Character, Integer> BASE32_DIGIT_MAP = new HashMap<>();
 static {
 int i = 0;
 for (char c : BASE32_DIGITS) {
 BASE32_DIGIT_MAP.put(c, i++);
 }
 }
 private GeohashUtils() {}

 /**
 *
 * @param GeohashPartial Target matching segment.That is the grid in the middle
 * @return 供sqlThe match segment to use.i.e. all nine squares
 */
 public static List<String> findNeighborGeohash(String GeohashPartial) {
 int accuracyLength = GeohashPartial.length();
 // Precision must be even,Otherwise, one more bit is ignored
 String middle = ((accuracyLength & 1) == 0)? GeohashPartial: GeohashPartial.substring(0, accuracyLength - 1);
 long middleDecode = decodeBase32(middle);
 long[] middleCoordinates = ascensionUsingPeano(middleDecode);
 List<long[]> allCoordinates = findNeighborCoordinates(middleCoordinates);

 return allCoordinates.stream().map(it -> encodeBase32(dimensionUsingPeano(it)) + '%')
 .collect(Collectors.toList());
 }

 /**
 * 解码Base32
 */
 private static long decodeBase32(String str) {
 StringBuilder buffer = new StringBuilder();
 for (char c : str.toCharArray()) {
 int j = BASE32_DIGIT_MAP.get(c) + 32;
 buffer.append(Integer.toString(j, 2).substring(1) );
 }
 return Long.parseLong(buffer.toString(), 2);
 }
 
 /**
 * Use the Peano curve to increase the dimension
 */
 private static long[] ascensionUsingPeano(long number) {
 int i = 0;
 long x = 0;
 long y = 0;
 while (number > 0) {
 y += (number & 1) << i;
 number >>>= 1;
 x += (number & 1) << i;
 number >>>= 1;
 i++;
 }
 return new long[]{x, y};
 }

 /**
 * Find eight adjacent squares
 */
 private static List<long[]> findNeighborCoordinates(long[] middle) {
 List<long[]> result = new ArrayList<>(9);

 result.add(new long[]{middle[0] - 1, middle[1] - 1});
 result.add(new long[]{middle[0] - 1, middle[1]});
 result.add(new long[]{middle[0] - 1, middle[1] + 1});
 result.add(new long[]{middle[0], middle[1] - 1});
 result.add(middle);
 result.add(new long[]{middle[0], middle[1] + 1});
 result.add(new long[]{middle[0] + 1, middle[1] - 1});
 result.add(new long[]{middle[0] + 1, middle[1]});
 result.add(new long[]{middle[0] + 1, middle[1] + 1});
 return result;
 }

 /**
 * Dimensionality reduction using Peano curve
 */
 private static long dimensionUsingPeano(long[] coordinates) {
 int i = 0;
 long x = coordinates[0];
 long y = coordinates[1];
 long result = 0;
 while (i < GEO_HASH_MAX_LENGTH) {
 result += (y & 1) << (i++);
 result += (x & 1) << (i++);
 y >>>= 1;
 x >>>= 1;
 }
 return result;
 }

 /**
 * 编码Base32
 */
 private static String encodeBase32(long number) {
 char[] buf = new char[65];
 int charPos = 64;
 boolean negative = (number < 0);
 if (!negative){
 number = -number;
 }
 while (number <= -32) {
 buf[charPos--] = BASE32_DIGITS[(int) (-(number % 32))];
 number /= 32;
 }
 buf[charPos] = BASE32_DIGITS[(int) (-number)];
 if (negative){
 buf[--charPos] = '-';
 }
 return new String(buf, charPos, (65 - charPos));
 }

 /**
 * Calculate a coordinateGeohash
 */
 public static String getGeohash(double longitude, double latitude) {
 BitSet longitudeBits = encodeBits(longitude, -180, 180);
 BitSet latitudeBits = encodeBits(latitude, -90, 90);
 StringBuilder sb = new StringBuilder();
 int singleBits = GEO_HASH_MAX_LENGTH / 2;

 for (int i = 0; i < singleBits; i++) {
 sb.append((longitudeBits.get(i))? '1': '0');
 sb.append((latitudeBits.get(i))? '1': '0');
 }
 return encodeBase32(Long.parseLong(sb.toString(), 2));
 }

 /**
 * through the given upper and lower bounds,Computes the binary string using the dichotomy method
 */
 private static BitSet encodeBits(double number, double floor, double ceiling) {
 int singleBits = GEO_HASH_MAX_LENGTH / 2;
 BitSet buffer = new BitSet(singleBits);
 for (int i = 0; i < singleBits; i++) {
 double mid = (floor + ceiling) / 2;
 if (number >= mid) {
 buffer.set(i);
 floor = mid;
 } else {
 ceiling = mid;
 }
 }
 return buffer;
 }

}

四、总结

⽬前MySQLThe implementation of spatial location expansion is still the same⽐weaker,实际应⽤There are many limitations.So relative⽐It can be considered for simpler geographical location requirements⽤MySQL.好在Geohash算法也⽐较成熟,⾃⼰It's not very real⿇烦.

如果有⽐More complex geographic requirements,还是要考虑ElasticSearchEtc. for geolocation queries⽀a better database/第三⽅组件.

参考链接：

1.Geohash算法原理及实现 - 简书

https://www.jianshu.com/p/2fd0cf12e5ba

2.mybatis读写数据库 geometry类型数据 - CodeAntenna

https://codeantenna.com/a/iBy59n9uan

3.Mybatis拦截器实现Geometry类型数据存储与查询 - 掘金

https://juejin.cn/post/6857012707901341710

关于领创集团（Advance Intelligence Group）

领创集团成立于 2016 年,致力于通过科技创新的本地化应用,改造和重塑金融和零售行业,以多元化的业务布局打造一个服务于消费者、企业和商户的生态圈.集团旗下包含企业业务和消费者业务两大板块,企业业务包含 ADVANCE.AI 和 Ginee,分别为银行、金融、金融科技、零售和电商行业客户提供基于 AI 技术的数字身份验证、风险管理产品和全渠道电商服务解决方案;消费者业务 Atome Financial 包括亚洲领先的先享后付平台 Atome 和数字金融服务.

2021 年 9 月,领创集团宣布完成超 4 亿美元 D 轮融资,融资完成后领创集团估值已超 20 亿美元,成为新加坡最大的独立科技创业公司之一.