共计 5204 个字符，预计需要花费 14 分钟才能阅读完成。
欢迎大家前往腾讯云 + 社区，获取更多腾讯海量技术实践干货哦~
本文由腾讯云数据库 TencentDB 发表于云 + 社区专栏
作者介绍：王晓宇，腾讯数据库 TDSQL 团队成员，目前参与 TDSQL 数据库内核研发工作。
腾讯与高校合作的论文入选数据库顶会
腾讯 TDSQL 团队携手中国人民大学信息学院、武汉大学计算机学院合作的 DEMO 论文“MSQL+: a Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems”被国际数据库顶级会议 VLDB 2018 录取。
该论文设计了一款基于 RDBMS 的插件式近似查询工具 MSQL+。MSQL+ 遵循 SQL 标准，支持面向度量空间（一种比文本空间、向量空间等更为简洁和通用的表达方式）的近似查询，依托分布式数据库系统 TDSQL，实现了通用、易用、高效的相似查询处理技术。
会议期间，团队展示了基于腾讯分布式数据库 TDSQL 实现的相似查询工具 MSQL+，用于在分布式系统 TDSQL 中实现相似查询。在 TDSQL 数据库内部集成更多的计算功能，赋予数据库更为丰富的计算能力。
原论文请见 http://www.vldb.org/pvldb/vol…。论文信息如下：
Wei Lu, Xinyi Zhang, Zhiyu Shui, Zhe Peng, Xiao Zhang, Xiaoyong Du, Hao Huang, Xiaoyu Wang, Anqun Pan, Haixiang Li: MSQL+: a Plugin Toolkit for Similarity Search under Metric Spaces in Distributed Relational Database Systems. VLDB 2018 Demonstration
如果您想了解更多技术细节，请参考如下内容（如下重点介绍 MSQL+ 的产生背景、功能、架构、设计）：
论文解读
以下重点介绍 MSQL+ 的产生背景、功能、架构、设计，原论文请见 http://www.vldb.org/pvldb/vol…。
MSQL+ 产生背景
相似查询是诸多数据库应用的基本操作。
举例来说，相似查询在文本检索、拼写检查、指纹认证、人脸识别等场景作用显著。
那么这些应用是如何进行相似查询的？给出对象 q 和集合 R，返回 R 中与 q 相似度相差不超过 θ 的元素。最直接地，遍历 r∈R，计算 r 与 q 的相似度，可想而知，此方法效率很低。
各领域已发展出多种方式对上述相似查询方式针对优化，但仍存在以下问题：
1 与现有数据库系统剥离：现有的相似查询方法，大量建立新系统或新式索引提高效率，如 M -Tree、D-Index、kd-tree 等，虽说性能得以提升，但很难将其融合到现有 RDBMS。另有一些方法基于 B +-tree 实现相似查询，但要在现有 RDBMS 上开发新 API，而且效率表现不佳。这些方法缺少统一标准、兼容性差，每接触新方法，都要付出额外的学习成本。
2 数据空间有限，普适性差：众多应用场景对“相似”的定义不同，衡量维度、数据类型不同，难以建立通用的相似查询模型。借助于定制化的剪枝规则，特定场景相似查询性能得到提升，但几乎不可能移植到其他应用场景。作为基本操作，相似查询应该具有普适性，在不同 RDBMS 应用中都能保证良好表现。
3 仅适用中心化系统，难应对“大数据”场景：大数据时代下，借助于分布式系统维护日益增长的数据是大势所趋。遗憾的是现有的相似查询方式，并未良好地支持分布式系统。
为避免上述问题，MSQL+ 被设计为：基于 RDBMS，遵循 SQL 标准，借力分布式数据库，以实现通用、易用、高效。在实际生产系统中，MSQL+ 以腾讯公司的分布式数据库 TDSQL 为依托，高效地实现了论文提出的思想和功能。
MSQL+ 主要功能
MSQL+ 由两大模块组成：
1 构建索引：MSQL+ 为每个数据对象生成可比较的签名（Signature），并在签名上建立 B +-tree 索引，签名值位于相似度范围内的对象，作为相似查询的候选项；
2 查询处理：用户提交 SELECT-FROM-WHERE 语句，该语句须提供两个约束条件，分别为：a) 用户定义的相似度函数，b) 相似度范围，条件 b)初步筛选候选项，条件 a)精炼候选项、返回相似结果集。
相比于现有的相似查询方式，MSQL+ 具备以下优势：
1 基于 RDBMS 现有功能实现，使用 B +-tree 索引数据，使用 SELECT-FROM-WHERE 语句相似查询；
2 支持广泛的数据空间：任意类型数据可被合理地索引（见下文设计），经由统一接口相似查询；
3 可运行于单机和分布式 RDBMS，依托分布式关系数据库系统 TDSQL，能够加快预处理及相似查询进程。
MSQL+ 设计方案
本节将对 MSQL+ 近似查询方案做简单介绍，细节请见原论文。
1. Similarity Search in Metric Spaces
MSQL+ 采用分治策略，将完整的数据集划分成多个独立的分片，每个分片筛选出若干较为相似的候选者，这些候选者后续会被二次精选。
MSQL+ 如何划分数据集？论文说明，数据集内一些对象被选为 pivot（下节介绍选举 pivot 的策略），剩余的数据对象按某种策略分配到唯一的 pivot（比如，与之最近的 pivot），这些 pivot 和分配至此的数据对象构成了一个分片。如此，完整的数据集被划分成多个互不相交的小数据集，然后在各分片内筛选较为相似的候选者。
筛选候选者的规则是什么呢？我们从一个例子入手：给出对象 q 和数据集 R，相似查询返回 R 中与 q 相差不超过 θ 的数据对象。对分区 Pi 而言，筛选 r∈Pi，且 |q,r|≦θ 的对象 r 作为候选者。
定理 1：
对于分区 Pi（其 pivot 为 Pi），∀r∈Pi，|q,r|≦θ 的必要条件是：
LBi=|pi, q|-θ≦|pi, r|≦|pi, q|+θ = UBi
Pivot 的挑选，是上述过程的基础，那么，MSQL+ 如何挑选 pivot？
2. Pivot Selection
选择合适的 pivot，可以加快筛选候选者及精选结果集的过程，论文提出了四种 pivot 选择方式：
1Random：从集合 R 中随机挑选对象作为 pivot；
2MaxVariance：从集合 R 中挑选方差最大的一组对象作为 pivots；
3MaxProb：pivot 需满足，预期筛选出的候选项的个数最少；
4Heuristic：采取类似于 k -means 的启发式算法，整体上看，各分区中的元素尽量靠近 pivot。
到此，已经可以筛选较为相近的候选者，那么，如何从中精选出更相近的结果集呢？
3. Processing similarity queries in RDBMS
为了快速精选出结果集，MSQL+ 在数据集上构建 B +-tree 索引，以下分两步，介绍该索引如何构建、如何使用。
论文做出定义：某表存储了数据集 R，表上有 M 个属性（即 M 列），部分属性作为相似度的度量，记作 A:{A1, A2, …, An} n≦M , 对于 r∈R，r[A]表示数据 r 属性 {A1, A2, …, An} 的值。
3.1 Index Building
在 A 上建立 B +-tree 索引，有两个条件：a) 域 {A1, A2, …, An} 都是可比较的，b) 只需比较 A 各域的值即可精选候选项。借助于此索引，可方便地实现相似查询。那么，如何构建这样的索引？论文做出这样的设计：
对于 r∈R，一张“签名表”（Signature generation schema）记录了 r 的签名 S(r[A])，S(r[A])=<i, |r, Pi|>，其中 i 是分区 ID，|r, Pi| 是分区内数据对象 r 和 pivot Pi 的差距，签名的比较规则为：
原表（存储数据集 R）上新增一列 I 记录签名 <i, |r, Pi|>，并在 I 上建立 B +-tree 索引，此索引满足“可比较”和“比较索引可确定候选项”两要素，故可借助此索引方便地近似查询。
3.2 Query Processing
至此，已经构建了合适的 B +-tree 索引，如何利用该索引精选候选者？
MSQL+ 支持用户自定义相似度函数 DIST(r[A], q[A], θ)，此函数判断 r[A]和 q[A]的距离未超过 θ，用户定义相似度函数这一设计，扩展了 MSQL+ 支持的数据空间和类型。有了 DIST 函数，用户输入 SELECT-FROM-WHERE 语句形如：
SELECT R.A1,…,R.An
FROM R
WHERE DIST(r[A], q[A], θ)
上面这条 SQL，直接从数据集 R 中精确筛选结果集，效率堪忧。
候选者此时派上用场，定理 1（见 Similarity Search in Metric Spaces）描述了如何筛选候选者，减少精确筛选的数据量，加速精拣过程。结合定理 1 和 DIST 函数，用户输入 SELECT-FROM-WHERE 语句形如：
SELECT R.A1,…,R.An
FROM R, PivotsRangeSet PRS
WHERE I BETWEEN PRS.LB and PRS.UB AND
DIST(r[A], q[A], θ)
其中，临时表 PivotsRangeSet 维护了各 pivot 的 LU 和 UB。因为 PivotsRangeSet 规模很小，查询优化器总会先索引扫描得到候选项，然后 DIST 函数精炼结果集。
MSQL+ 分布式架构
MSQL+ 既可在本地 RDBMS 上工作，又可部署在分布式 RDBMS。论文给出 MSQL+ 基于 TDSQL 的架构。
1. System Architecture
1.1 TDSQL 介绍
TDSQL 是腾讯针对金融联机交易场景推出的高一致性，分布式数据库集群解决方案，能够保证强一致下的高可用，拥有灵活的全球部署架构，实现了倍数性能提升，增强了 MySQL 原生的安全机制，能够在水平方向上分布式扩展，具有自动化的运营体系和完善的配套设施。
TDSQL 由以下关键组件构成：
1Routing Node：负载均衡；
2ZooKeeprt：维护系统元信息，如表、索引、分区等；
3Global Executor：接收 SQL、下发 local executor、汇集本地结果、生成执行计划等；
4Local executor：本地数据存、取、计算等。
1.2 TDSQL 增益
MSQL+ 是一款由用户自定义函数、存储过程实现的插件式工具，可以无缝融入 TDSQL。
MSQL+ 如何在 TDSQL 上工作呢？
ZooKeeper 维护 MSQL+ 特需的元信息，并同步至各 local executors；Global executor 接收相似查询请求，分发至各 local executors 执行，汇集最终结果并给出执行计划；Local executor 完成本地分片相似查询，返回执行结果。
TDSQL 又能给 MSQL+ 带来什么样的增益？
首先是可靠、可用性，TDSQL 实现了多副本强一致性，最大程度地保障 MSQL+ 所需的大量样本数据的安全、可用、可靠。
其次，TDSQL 支持水平方向分布式扩展，免除单机存储容量不足的后顾之忧，无论 MSQL+ 样本数据多大，TDSQL 都可轻松应对。
TDSQL 在安全机制做出的优化，很大程度保证 MSQL+ 样本数据的安全和机密。
我们最关心的性能问题，从分布式角度看，TDSQL 多个本地节点并行查询，全局相似查询效率大幅度提升；具体到本地节点，TDSQL 在数据库内核方面做出大量优化，使得单节点效率也有很大提升。
2. Index Building
ZooKeeper 维护了全部 pivot 信息，并由 Global executor 将 pivot 信息下发至 local executors。Global executor 协调 local executors 构建索引，每个 local executor 维护一定数量的分片，也就维护对应的 pivots，基于这些 pivots，local executor 生成签名 S(r[A])，进而构建起索引。
3. Query Processing
用户发起相似查询请求时，routing node 选择一个 global executor，global executor 协调 local executors 并行执行相似查询，汇集本地执行结果并生成执行计划。
MSQL+ 界面展示
论文展示的操作界面如下，MSQL+ 支持相似查询、索引构建、客户端连接、集群管理、数据导入、查询状态显示、执行计划可视化等功能。
结论：
MSQL+ 是一款基于 RDBMS 的插件式近似查询工具，基于腾讯 TDSQL 实现，具有通用、易用、高效的特点：统一接口支持多种数据空间；遵循 SQL 标准，发起 SELECT-FROM-WHERE 命令即可完成相似查询任务；MSQL+ 依托腾讯分布式数据库 TDSQL，实现了负载均衡、多点并行，可高效地完成相似查询。
问答 PHP + MSQL + 函数在函数中使用请求相关阅读 TDSQL 参加全球数据库顶级盛会 VLDB 2018 回顾腾讯云数据库 MySQL 游戏行业数据安全实践分享 MySQL 8.0 版本功能变更介绍【每日课程推荐】机器学习实战！快速入门在线广告业务及 CTR 相应知识
