Python实现MySQL Hash Join完成两表等值连接的方法

你构思的嵌套循环交换方案无法得到正确结果，核心缺陷如下：

• 时间复杂度为O(n*m)，属于最朴素的嵌套遍历逻辑，数据量稍大时性能极差
• 交换逻辑存在语法错误：末尾table2.column[]缺失索引值，本身无法运行
• 即使补全索引，交换操作仅调整了关联列（Name）的元素位置，同表其他列（如Employee的ID、InvitedToParty的FavoriteFood）没有同步换位，最终会出现行数据完全错位的问题
• 匹配计数逻辑不支持重复键场景：如果关联键在任意一张表存在重复值，既可能漏算匹配行，也可能多算无效行，后续截断match_counter后行的逻辑完全无法对齐SQL的连接语义。

MySQL 8.0后等值连接默认采用Hash Join算法，核心逻辑分为两步，时间复杂度为O(n+m)，性能远高于嵌套循环，完全适配你当前用类实例按列存储表数据的结构：

1. 选择数据量更小的表作为构建表，遍历其所有行，以关联列的值为key、对应行需要返回的字段集合为value构建哈希表，同一个key对应多行时以列表形式存储
2. 遍历另一张探测表的每一行，用关联列的值去哈希表中查找，匹配成功时将两边行的字段拼接，存入最终结果集

实现代码如下：

def hash_join(tables, t1_name, t2_name, join_key, t1_select_cols, t2_select_cols):
    """
    等值连接实现，对齐MySQL Hash Join核心逻辑
    :param tables: 存储表实例的字典
    :param t1_name: 第一张表名
    :param t2_name: 第二张表名
    :param join_key: 关联列名（要求两边关联列名一致，不一致可自行增加键映射参数）
    :param t1_select_cols: 第一张表需返回的列名列表
    :param t2_select_cols: 第二张表需返回的列名列表
    :return: 连接结果，每个元素为一行数据，顺序和传入的select列顺序一致
    """
    t1 = tables[t1_name]
    t2 = tables[t2_name]

    # 自动选择更小的表构建哈希表，降低内存占用，和MySQL优化逻辑一致
    if len(getattr(t1, join_key)) > len(getattr(t2, join_key)):
        t1, t2 = t2, t1
        t1_select_cols, t2_select_cols = t2_select_cols, t1_select_cols

    # 构建阶段：生成哈希表
    hash_map = {}
    t1_total_rows = len(getattr(t1, join_key))
    for idx in range(t1_total_rows):
        key = getattr(t1, join_key)[idx]
        row_data = tuple(getattr(t1, col)[idx] for col in t1_select_cols)
        if key not in hash_map:
            hash_map[key] = []
        hash_map[key].append(row_data)

    # 探测阶段：遍历大表匹配结果
    result = []
    t2_total_rows = len(getattr(t2, join_key))
    for idx in range(t2_total_rows):
        key = getattr(t2, join_key)[idx]
        if key not in hash_map:
            continue
        t2_row_data = tuple(getattr(t2, col)[idx] for col in t2_select_cols)
        # 处理一个键对应多行的情况，符合SQL连接的笛卡尔积语义
        for t1_row_data in hash_map[key]:
            result.append((*t1_row_data, *t2_row_data))

    return result

针对你最开始写的SQL查询，调用方式如下：

# 对应SQL: SELECT Employee.Name, Employee.ID, InvitedToParty.Name, InvitedToParty.FavoriteFood FROM Employee, InvitedToParty WHERE Employee.Name = InvitedToParty.Name
query_result = hash_join(
    tables=tables,
    t1_name="Employee",
    t2_name="InvitedToParty",
    join_key="Name",
    t1_select_cols=["Name", "ID"],
    t2_select_cols=["Name", "FavoriteFood"]
)

该实现的优势：

• 不会修改原表的任何存储数据，不需要做交换、截断这类破坏性操作
• 取数时按同一行索引获取所有列的值，不会出现列错位问题
• 天然支持关联键重复的场景，完全符合SQL标准的内连接语义
• 如果需要处理超大规模表，可以在这个基础上扩展分桶、磁盘溢出逻辑，和MySQL企业版的Hash Join能力对齐。

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