如何在HSQL中高效查找大表重复姓名记录（避免二次时间复杂度）

你描述的对数线性复杂度排查逻辑，在HSQL中不需要做全表自连接（避免O(n²)开销），通过分组/窗口函数即可实现，完全匹配函数式处理流程的时间复杂度要求，适配OpenOffice Base的内置HSQL引擎。

最高效的标准写法 #

OpenOffice当前分发版本默认搭载HSQL 2.x及以上版本，支持窗口函数，执行效率最高、代码最简洁：

-- 请将`person_info`替换为你实际使用的表名
SELECT ID, FORENAME, SURNAME
FROM (
    SELECT
        ID,
        FORENAME,
        SURNAME,
        COUNT(*) OVER (PARTITION BY SURNAME, FORENAME) AS repeat_count
    FROM person_info
) t
WHERE repeat_count >= 2
ORDER BY SURNAME, FORENAME, ID;

逻辑对应说明 #

这个写法和你列出的函数式处理流程完全对齐：

1. 窗口函数PARTITION BY SURNAME, FORENAME的底层执行逻辑，会先按SURNAME、FORENAME做有序排序，和你分步按姓、名排序的逻辑一致
2. 分区计数的过程就是相邻同姓名元素分组的过程，外层过滤repeat_count >=2直接剔除所有单元素分组，不需要额外调用长度判断逻辑
3. 最终返回结果已经按姓、名、ID排序，同名记录连续排列，就是展平后的可疑记录列表，直接满足人工核对的查看需求

整个执行流程的核心开销是一次全表排序，时间复杂度为O(n log n)，不存在全表连接产生的二次方计算量。

旧版本HSQL兼容写法 #

如果碰到极旧版本HSQL不支持窗口函数，可以用分组聚合定位重复键再关联的写法，时间复杂度依然保持对数线性：

-- 请将`person_info`替换为你实际使用的表名
SELECT m.ID, m.FORENAME, m.SURNAME
FROM person_info m
INNER JOIN (
    SELECT SURNAME, FORENAME
    FROM person_info
    GROUP BY SURNAME, FORENAME
    HAVING COUNT(*) >= 2
) dup_name 
    ON m.SURNAME = dup_name.SURNAME 
    AND m.FORENAME = dup_name.FORENAME
ORDER BY m.SURNAME, m.FORENAME, m.ID;

这个写法中子查询的GROUP BY操作本身就是O(n log n)的排序分组逻辑，产出的重复姓名键结果集远小于原表，关联回原表时不会产生笛卡尔积开销，性能远优于全表自连接方案。

性能优化建议 #

如果表数据规模极大，可以给(SURNAME, FORENAME)建立联合索引，两种写法都可以直接走索引的有序扫描，跳过内存排序步骤，查询速度会有明显提升。

内容的提问来源于stack exchange，提问作者fledermaus