我在处理以下情况时遇到了SQL查询效率低的问题：
假设我们有一个包含两列的表格
groupId : int
value : float
这张表非常庞大（数百万行）。每个“groupId”具有不同数量的“values”，大约在100到50,000之间。所有浮点值都大于或等于零，但否则没有限制。
对于给定的“groupId”，查询应按相似性递减排序返回所有其他组，其中“相似”定义为两组中30个值的所有可能对之间的最小欧几里得距离。
这种相似性的定义让我很疑惑。我认为，针对上述定义计算相似性的朴素算法是O（n ^ 2）。现在我正在寻找重新定义“相似性”或有效实施上述内容的思路。我可以想象涉及k近邻的解决方案，类似于PostGis几何最近邻居或者可能是最长公共子序列算法（尽管我需要后者的“模糊”实现，因为“values”几乎永远不会完全相等）。
我们目前使用的是MySQL，如果有影响请告知。
谢谢！
Sören
您能确认我理解问题的正确性吗？
您的表格表示由groupId标识的向量。每个向量具有100到50,000之间的某个维度，但没有定义维度顺序。这意味着来自表中的向量实际上是等价类的代表。
现在，您将两个等价类的相似度定义为任意两个等价类的代表的投影到前30个维度的子空间的最小欧几里得距离。
投影至两个维度的示例：
A = <1, 2, 3, 4>
B = <5, 6, 7, 8, 9, 10>
A代表以下向量等价类。
<1, 2, 3, 4> <2, 1, 2, 3> <3, 1, 2, 4> <4, 1, 2, 3>
<1, 2, 4, 4> <2, 1, 3, 2> <3, 1, 4, 2> <4, 1, 3, 2>
<1, 3, 2, 4> <2, 3, 1, 4> <3, 2, 1, 4> <4, 2, 1, 3>
<1, 3, 4, 2> <2, 3, 4, 1> <3, 2, 4, 1> <4, 2, 3, 1>
<1, 4, 2, 2> <2, 4, 1, 3> <3, 4, 1, 2> <4, 3, 1, 2>
<1, 4, 3, 2> <2, 4, 3, 1> <3, 4, 2, 1> <4, 3, 2, 1>
<1, 2> <1, 3> <1, 4>
<2, 1> <2, 3> <2, 4>
<3, 1> <3, 2> <3, 4>
<4, 1> <4, 2> <4, 3>
B代表一个有720个元素的等价类。对前两个维度的投影得到30个元素。
< 5, 6> < 5, 7> < 5, 8> < 5, 9> < 5, 10>
< 6, 5> < 6, 7> < 6, 8> < 6, 9> < 6, 10>
< 7, 5> < 7, 6> < 7, 8> < 7, 9> < 7, 10>
< 8, 5> < 8, 6> < 8, 7> < 8, 9> < 8, 10>
< 9, 5> < 9, 6> < 9, 7> < 9, 8> < 9, 10>
<10, 5> <10, 6> <10, 7> <10, 8> <10, 9>
btree_gist模块并创建一个GIST索引。<->，并提供了使用此运算符进行最近邻搜索的GiST索引支持。为int2、int4、int8、float4、float8、带时区的时间戳、不带时区的时间戳、不带时区的时间、日期、间隔、oid和货币提供距离运算符。
float8是double precision。以下是一些不错的近似方法：
您可以计算每个组的质心，然后根据每个组的质心距离进行比较。
另一种方法是通过哈希每行的坐标，将哈希到相同位置的行视为相似，从而更新两个组的相似度。
更多信息会很有帮助，例如：
信息是否经常更新，如果是，则更新间隔是多少。 需要多新和多准确的信息？
select groupid, min(distance) as mindist
from
(select other.groupid as groupid,
min(abs(other.value - us.value)) as distance
from g us
join g other on other.groupid != us.groupid
where us.groupid = ?)
order by mindist
group by groupid
然后，为了利用索引：
select groupid, min(abs(value - usvalue)) as mindist
from
(select other.groupid as groupid,
max(other.value) as value,
us.value as usvalue
from g us
join g other on other.groupid != us.groupid and other.value <= us.value
where us.groupid = ?
union
select other.groupid as groupid,
min(other.value) as value,
us.value as usvalue
from g us
join g other on other.groupid != us.groupid and other.value >= us.value
where us.groupid = ?)
order by mindist
group by groupid
这样做有望使mysql使用索引快速查找连接中最近的邻居。
可能会有错误，但希望这种思路能够帮助。