MySQL高效连接查询秘籍：掌握这四种Join算法

大家好，欢迎来到IT知识分享网。

联接查询

在数据库，如果表内容比较小，那么我们还是会经常使用Join查询来完成业务需求。MySQL提供了一些Join算法，我们今天来讨论一下，如果有任何问题请评论告知，谢谢。

如果你自己实现Join算法，你会怎么做？

我们来先分析下Join的目的是获取左右量表的数据来组成一个新的结果集。

那我们把两张表看做两个数组，比如数组A和数组B。我们把这两个数组连接起来的算法有哪些？

1. 两个for循环进行简单联接
2. 先对数组进行处理，然后再联接

其中，第一种方式比较简单，就是简单粗暴的组合，那第二种就会有很多组合。

1. 排序好的数组，二分查找
2. 对数组进行排序，查找匹配
3. 对数组进行哈希，哈希查找

看几个代码Demo

我们用一个TradeUser来表示用户表，TradeOrder表示订单表，我们目的是输出一个用户订单视图UserOrderView, 联接条件： user.id=order.user_id。
假设TradeUser表有M条记录，TradeOrder有N条记录。

// 用户表 type TradeUser struct { Id int Name string } // 订单表 type TradeOrder struct { Id int UserId int Amount uint } // 结果表 // Join条件: user.id=order.user_id type UserOrderView struct { UserId int UserName string OrderId int OrderAmount uint }

两个for循环进行简单联接

// 两个循环进行联接查询 // 算法复杂度：O(M * N) // 假设用户表有M条记录， 订单表有N条记录 func NestedLoopJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView { var userOrderViews []*UserOrderView = make([]*UserOrderView, 0) // 遍历用户表 for _, user := range users { // 遍历订单表 for _, order := range orders { // 条件匹配 if user.Id == order.UserId { // 添加视图结果 userOrderViews = append(userOrderViews, &UserOrderView{ UserId: user.Id, UserName: user.Name, OrderId: order.Id, OrderAmount: order.Amount, }) } } } return userOrderViews }

我们可以很容易分析得到使用两个for循环进行Join的算法复杂度为O(M*N), 实际业务场景中，TradeOrder表要大于TradeUser表，所以两个for循环的算法复杂度为O(N^2)。

排序好的数组，二分查找

// 排序进行联接查询 // 算法复杂度：O(M log N) func IndexJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView { userOrderViews := make([]*UserOrderView, 0) // 使用已排序的orders作为具有索引的表 // 复杂度：O(M) for _, user := range users { // 二分查找来寻找匹配的订单基于user.Id // 复杂度：: O(log N) index := sort.Search(len(orders), func(i int) bool { return orders[i].UserId >= user.Id }) // 检查是否找到订单，以及id是否匹配 for index < len(orders) && orders[index].UserId == user.Id { // Join条件满足添加视图结果 userOrderViews = append(userOrderViews, &UserOrderView{ UserId: user.Id, UserName: user.Name, OrderId: orders[index].OrderId, OrderAmount: orders[index].Amount, }) index++ } } return userOrderViews }

对于这个算法，for循环的复杂度是O(M）,二分查找的复杂度是log(N),但是二分查找要执行M次，所以整体二分查找要执行M(log(N)),所以整体复杂度为O(M) + M(log(N))。在算法复杂度领域中，这两个谁的值比较大就写谁，所以这个算法的复杂度是M(log(N))。

对数组进行排序，查找匹配

// 排序进行联接查询 // 算法复杂度：O(M log M + N log N) // 假设用户表有M条记录， 订单表有N条记录 func SortJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView { var userOrderViews []*UserOrderView = make([]*UserOrderView, 0) // 排序user表 // 算法复杂度：O(M log M) sort.Slice(users, func(i, j int) bool { return users[i].Id < users[j].Id }) // 排序order表 // 算法复杂度：O(N log N) sort.Slice(orders, func(i, j int) bool { return orders[i].Id < orders[j].Id }) // 遍历订单表，查找用户 // 算法复杂度：O(M) userIdx := 0 for _, order := range orders { // 在user.id为主键的情况下，这里还可以执行二分查找 for idx < len(users) && users[userIdx].Id < order.UserId { userIdx++ } // 如果找到用户，添加到结果集合 if userIdx < len(users) && users[userIdx].id == order.UserId { // Join条件满足添加视图结果 userOrderViews = append(userOrderViews, &UserOrderView{ UserId: user.Id, UserName: user.Name, OrderId: order.Id, OrderAmount: order.Amount, }) } } return userOrderViews }

这个算法的复杂度是O(M log M + N log N)，如果用户远大于订单则复杂度为：O(M log M），否则为：O(N log N)。

对数组进行哈希，哈希查找

// 哈希进行联接查询 // 算法复杂度：O(M + N) // 假设用户表有M条记录， 订单表有N条记录 func HashJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView { var userOrderViews []*UserOrderView = make([]*UserOrderView, 0) // 将用户表以用户ID为Key，用户为Value转换为Hash表 // 算法复杂度：O(M) userTable := make(map[int]TradeUser) for _, user := range users { userTable[user.Id] = user } // 遍历订单表，查找用户 // 算法复杂度：O(N) for _, order := range orders { // 复杂度，接近:O(1) if user, exists := userTable[order.UserId]; exists { // 添加视图结果 userOrderViews = append(userOrderViews, &UserOrderView{ UserId: user.Id, UserName: user.Name, OrderId: order.Id, OrderAmount: order.Amount, }) } } return userOrderViews }

我们可以很容易分析得到使用哈希进行Join的算法复杂度为O(M+N), 这个结果比两个for循环要好很多了。

总结

我们上面总共提到了四种算法：

1. 两个for循环进行简单联接 – Nested Loop Join
2. 排序好的数组，二分查找 -Index Join
3. 对数组进行排序，查找匹配 – Sort Merge Join
4. 对数组进行哈希，哈希查找 – Hash Join

MySQL主要使用了以上的Join算法，我们只是大概模拟，MySQL实现比我们代码复杂多了。我们中的SQL的join操作的复杂度如下表：