一、背景
我们的⼀个早期项⽬使⽤了 MyBatis-Plus+MySQL，新⼀期需求中增加了按地理位置筛选最近的店铺列表的功能点。由于此需求相对简单，因此我们考虑在 MySQL 中实现地理位置筛选，并进⾏了以下探索。
二、方案一：MySQL 使⽤GEOMETRY/POINT 类型的字段存储地理位置
由于 MySQL5.6 及之后版本已基本⽀持空间位置扩展，对⼏何对象采⽤WKB 格式存储，WKT 格式展⽰。因此我们⾸先考虑在 MySQL 中使⽤ GEOMETRY/POINT 类型的字段存储地理位置（坐标）进⽽使⽤MySQL 提供的空间索引来进⾏地理位置筛选。
MySQL 中 GEOMETRY/POINT 类型的字段的编码格式为 WKB (Well-known Binary)：
可以通过 WKT 值来创建 GEOMETRY/POINT 类型的值
我们的代码中所使⽤的坐标可以轻松转换为 WKT 格式，然后在 WKT 和 WKB 之间进⾏转换即可。
MySQL 使⽤如下⽅式转换 WKT 和 WKB：
衍⽣问题 让 MyBatis-Plus⽀持 GEOMETRY/POINT 类型
如果我们使⽤MyBatis,那么直接在 mapper⾥的 SQL 语句中使⽤这些转换函数即可，但是我们项⽬中使⽤了 MyBatis-Plus,尽量不⼿⼯编写 SQL。因此希望能让 MyBatis-Plus⽀持对坐标和 GEOMETRY/POINT 类型进⾏转换。我们进⾏了⼀些尝试，并最终得到了⽐较合适的解决⽅案。
2.1 尝试⼀
使⽤MyBatis TypeHandler 将坐标和 WKT 格式的字符串进⾏转
因为 MySQL⽀持这样的写法来插⼊/更新 GEOMETRY/POINT 类型的字段
INSERT INTO t1 (pt_col) VALUES(Point(1,2));
复制代码
既然 MyBatis 可以扩展 TypeHandler。那么我们可以将应⽤中的坐标类型转换为 WKT 格式的字符串，传到 MySQL 后应该是可以被处理的。但是实际上这⼀思路⽆法成功，因为在 JDBC 驱动中会报错⽆法将 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(?)
复制代码
这个思路⼤致可以实现。但是实现起来⽐较⿇烦，有以下问题：
• 在需要转换的字段上需要通过注解或者其他⽅式进⾏标记
• 需要解析 SQL
• 需要处理字段名驼峰转下划线等细节
• 处理不了 GEOMETRY/POINT 有复杂操作的 SQL
• 查询，更新 SQL 需要分开处理
• 如果有符合条件的 SQL 不希望进⾏改写，还需要特殊处理
因此这个⽅案被放弃了。
2.3 尝试三
使⽤MyBatis TypeHandler 和 JTS 将坐标转换为 WKB 编码的字节
通过引⼊jts-core,我们可以在应⽤中直接将坐标转换为 WKB 编码的字节再传给 MySQL，也可以从 MySQl 中解读 WKB 编码的字节数组并解码为坐标。
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;
@Slf4jpublic class Converter {
private static final GeometryFactory GEOMETRY_FACTORY = new GeometryFactory(new PrecisionModel(), 0, CoordinateArraySequenceFactory.instance());
private Converter() { }
/** * 通过jts，读取数据库中的geometry对象并转换为GeoPoint * * @param bytes 数据库中的原始流 * @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("SRID different between database and application, db:{}, app:{}", 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("failed when reading points from database.", e); return null; } }
/** * 通过jts，将GeoPoint对象转换为数据库能识别的数据流 * * @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("failed when writing points to database.", e); return new byte[0]; } }
}
复制代码
方案一的缺陷
由于 MySQL 的空间索引函数存在以下缺陷，导致我们最终选择放弃⽅案⼀⾃⼰实现 Geohash。
三、方案二：⾃⼰实现 Geohash
Geohash 算法把⼀个空间点转化为⼀个哈希串。这个哈希串要求满⾜性质：前缀匹配相同的点，必然接近。这样才能在查询时，缩⼩查询范围。
我们在应⽤层⾯实现 Geohash 算法，计算地理位置的 Geohash 的值，存储在 MySQL 中，这样在 MySQL 中对 Geohash 进⾏字符串⽐较即可筛选地理位置。
Geohash 算法
1. 使⽤⼆分法，将坐标系划出矩形⽹格，将经度、纬度分别转化为⼆进制字符串。例如，⼀个 POINT(70, 10)，第⼀步，70 在(-180, 180)中属于较⼤的⼀半，取 1；10 在(-90, 90)中属于较⼤的⼀半，取 1。第⼆步，70 在(0, 180）中属于较⼩的⼀半，取 0；10 在(0, 90)中属于较⼩的⼀半，取 0。第三步，70 在(0, 90）中属于较⼤的⼀半，取 1；10 在(0, 45)中属于较⼩的⼀半，取 0。第四步，70 在(45, 90）中属于较⼤的⼀半，取 1；10 在(0, 22.5)中属于较⼩的⼀半，取 0。这样就得到四位有效数字，经度 1011，纬度 1000。可以看到，四位有效数字等价于±22.5 经度±5.625 纬度。
2.使⽤⽪亚诺曲线降维。错位归并即可。1011、1000 -> 11001010，从经度拿 1，从纬度拿 1；再从经度拿 0，从纬度拿 0；从经度拿 1，从纬度拿 0；从经度拿 1，从纬度拿 0。这样得到⼀个⼆进制字符串。
3.使⽤base32 算法，每 5 位转化为⼀个 char。使⽤的字符为 0-9、b-z（去掉 a, i, l, o）。
4.得到的就是 MySQL 默认的 Geohash 了，等价于
注意第⼆个参数 i 代表最后结果的有效数字，最常⽤的 i=8，相当于 8*5/2=20 位经纬度有效数字。
Geohash 的应⽤和问题
Geohash 的特征是，其前若⼲位有效字符，代表了包括对象的⼀个更⼤的区域范围。事实上，每少 2 位有效字符，都相当于 2*5/2=5 次⼆分，也就是 2^5=32 倍⼤⼩的⼀个区域。因此在需要查询给定位置附近的地理位置时，使⽤Geohash 可以快速定位到⼀个范围内。
不过，Geohash 同时有⼀个明显的问题。
如图，假设我们希望找到离 a 最近的点。假设我们过滤的时候，使⽤了格⼦5 作为 Geohash 匹配，那么我们找到的最近值会是 e。但实际最近的点，应为隔壁格的 b 点。怎么办呢？
最容易想到的⽅法是再度扩⼤匹配格。但问题是，⽪亚诺曲线是有突变点的
对于某⼀个特定的点，扩增后的范围只能保证包裹它⾃⼰，⽆法确定扩增到何种地步才能包括全部九个相邻格。例如：上图对于格⼦1100，不管是扩⼤为 110、11 哪怕是 1，都⽆法覆盖其左边的 0110 格。
因此，需要⼿动获得周围⼋个格⼦的匹配信息，并使⽤OR 做匹配。这⼀点实现起来也不难，因为相邻格恰好是其横纵坐标±1 即可。
例如，0110 -> (01, 10)，1100 -> (10, 10)，01 + 1 = 10。获得之后，使⽤or 匹配即可。
给⼀段具体的 Geohash 算法实现：
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位，经纬度各20位 */ 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 目标匹配段。即中间那个格子 * @return 供sql使用的匹配段。即所有九个格子 */ public static List<String> findNeighborGeohash(String GeohashPartial) { int accuracyLength = GeohashPartial.length(); // 精度必须为偶数，否则再忽略一位 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); } /** * 使用皮亚诺曲线升维 */ 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}; }
/** * 找到八个相邻格 */ 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; }
/** * 使用皮亚诺曲线降维 */ 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)); }
/** * 计算出一个坐标的Geohash */ 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)); }
/** * 通过给定的上下限，使用二分法计算出二进制字符串 */ 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; }
}
复制代码
四、总结
⽬前 MySQL 对于空间位置扩展的实现还是⽐较薄弱的，实际应⽤中存在诸多限制。因此在相对⽐较简单的地理位置需求上可以考虑使⽤MySQL。好在 Geohash 算法也⽐较成熟，⾃⼰实现起来也不太⿇烦。
如果有⽐较复杂的地理位置需求，还是要考虑 ElasticSearch 等对地理位置查询⽀持的更好的数据库/第三⽅组件。
参考链接：
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 亿美元，成为新加坡最大的独立科技创业公司之一。
往期回顾 BREAK AWAY
Spring data JPA 实践和原理浅析
如何解决海量数据更新场景下的 Mysql 死锁问题
企业级 APIs 安全实践指南 （建议初中级工程师收藏）
Cypress UI 自动化测试框架
serverless让我们的运维更轻松
评论