Java 开发视频教程！MySQL8

MySQL 因为没有实现 hashjoin 而受到批评。最新的 8.0.18 版本带来了这一功能，令人欣慰。有时候我想知道为什么 MySQL 不支持 hashjoin？我认为这可能是因为 MySQL 主要用于简单的 OLTP 场景，而且它广泛应用于 Internet 应用程序中，所以需求并不那么迫切。另一方面，这可能是因为以前完全依赖社区。毕竟 MySQL 的进化速度是有限的。甲骨文收购 mysql 后，mysql 发布的演进速度明显加快。

• 源点：提供流的节点（入度为 0），类比成为一个无限放水的水厂

• 汇点：接受流的节点（出度为 0），类比成为一个无限收水的小区

• 弧：类比为水管

• 弧的容量：类比为水管的容量；用函数 c(x,y)c(x,y)表示弧(x,y)(x,y)的容量

• 弧的流量：类比为当前在水管中水的量；用函数 f(x,y)f(x,y)表示弧(x,y)(x,y)的流量

• 弧的残量：即容量-流量

• 容量网络：对于一个网络流模型，每一条弧都给出了容量，则构成一个容量网络。

• 流量网络：对于一个网络流模型，每一条弧都给出了流量，则构成一个流量网络。

• 残量网络：对于一个网络流模型，每一条弧都给出了残量，则构成一个残量网络。最初的残量网络就是容量网络。

hashjoin 本身的算法实现并不复杂。要说它很复杂，可能是优化器选择执行计划时，是否选择 hashjoin，选择外观，内部表可能更复杂。无论如何，现在使用 hashjoin，优化器在选择 join 算法时还有另一个选择。MySQL 基于实用主义。我相信这个增强也回答了一些问题。有些职能并非无能，而是有优先权。

在 8.0.18 之前，MySQL 只支持 nestlopjoin 算法。最简单的是简单的 nestloop 连接。MySQL 对该算法进行了一些优化，包括块嵌套循环连接、索引嵌套循环连接和批密钥访问。通过这些优化，可以在一定程度上缓解 hashjoin 的紧迫性。接下来，我们将用一个单独的章节来讨论 MySQL 的这些连接优化。接下来，我们将讨论 hashjoin。

Hash Join 算法

Nestloopjoin algorithm is simply a double loop, which traverses the surface (drive table), for each row of records on the surface, then traverses the inner table, and then determines whether the join conditions are met, and then determines whether to spit out the records to the last execution node. In terms of algorithm, this is a complexity of M * n. Hash join is an optimization for equal join scenarios. The basic idea is to load the external data into memory and establish a hash table. In this way, you can complete the join operation and output the matching records only by traversing the internal table once. If all the data can be loaded into memory, of course, the logic is simple. Generally speaking, this kind of join is called CHJ (classic hash join). MariaDB has implemented this kind of hash join algorithm before. If all the data cannot be loaded into memory, it needs to be loaded into memory in batches, and then joined in batches. The following describes the implementation of these join algorithms.

In-Memory Join(CHJ)

HashJoin 一般包括两个过程，创建 hash 表的 build 过程和探测 hash 表的 probe 过程。

1).build phase

遍历外表，以 join 条件为 key，查询需要的列作为 value 创建 hash 表。这里涉及到一个选择外表的依据，主要是评估参与 join 的两个表(结果集)的大小来判断，谁小就选择谁，这样有限的内存更容易放下 hash 表。

2).probe phase

hash 表 build 完成后，然后逐行遍历内表，对于内表的每个记录，对 join 条件计算 hash 值，并在 hash 表中查找，如果匹配，则输出，否则跳过。所有内表记录遍历完，则整个过程就结束了。过程参照下图，来源于MySQL官方博客

? ?

左侧是 build 过程，右侧是 probe 过程，country_id 是 equal_join 条件，countries 表是外表，persons 表是内表。

On-Disk Hash Join

CHJ 的局限性在于需要内存来适应整个曲面。在 mysql 中，join 可以使用的内存由 join buffer size 参数控制。如果一个连接所需的内存超过了连接缓冲区的大小，CHJ 会忍不住将曲面分成几个段，逐个构建每个段，然后遍历内部表，再次探测每个段。假设表面被分成 n 块，然后扫描内表 n 次。当然，这种方式比较弱。在 MySQL 8.0 中，如果一个 join 所需的内存超过了 join 缓冲区的大小，那么构建阶段将首先使用哈希计算来划分外表面并生成一个临时的磁盘分区；然后在探测阶段，使用相同的哈希算法来划分内表。由于相同的哈希函数，相同的键（相同的连接条件）必须在相同的分区号中。接下来，对外部表和内部表中具有相同分区号的数据执行 CHJ。在所有的 CHJ 片段完成之后，整个连接过程就完成了。该算法的代价是外部表读 IO 两次，内部表写 IO 一次。与以往的 n 扫描内表 IO 相比，目前的处理方法更好。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct data
{
    int to,next,val;
}e[2*100005];
int cnt,head[10005],prep[10005],pree[10005],flow[10005],ans;
queue<int> que;
int n,m,s,t,u,v,w;
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].val=w;
}
int bfs(int s,int t)
{
    while (!que.empty()) que.pop();
    flow[s]=0x3f3f3f3f;//flow记录的是在增广路上经过该点的流量
    que.push(s);
    for (int i=1;i<=n;i++) 
    {
        prep[i]=-1;//用于记录前驱节点
        pree[i]=0;//用于记录前驱边的编号
    }
    prep[s]=0;
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        if (now==t) break;
        for (int i=head[now];i;i=e[i].next)
        {
            if (e[i].val>0&&prep[e[i].to]==-1)
            {
                que.push(e[i].to);
                flow[e[i].to]=min(flow[now],e[i].val);
                pree[e[i].to]=i;
                prep[e[i].to]=now;
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
void EK(int s,int t)
{
    int delta=bfs(s,t);//寻找最短增广路的最大流量
    while (delta!=-1)
    {
        ans+=delta;
        for (int j=t;j;j=prep[j])
        {
            e[pree[j]].val-=delta;
            e[pree[j]^1].val+=delta;

# **结尾**
![查漏补缺：Java岗 千+道面试题Java基础+全家桶+容器+反射+异常等](https://static001.geekbang.org/infoq/c6/c679ccbcbeaf59c04522495b095668a8.png)
这不止是一份面试清单，更是一种”被期望的责任“，因为有无数个待面试者，希望从这篇文章中，找出通往期望公司的”钥匙“，所以上面每道选题都是结合我自身的经验于千万个面试题中经过艰辛的两周，一个题一个题筛选出来再次对好答案和格式做出来的，面试的答案也是再三斟酌，深怕误人子弟是小，影响他人仕途才是大过，也希望您能把这篇文章分享给更多的朋友，让他帮助更多的人，帮助他人，快乐自己，最后，感谢您的阅读。
**[资料领取方式：戳这里免费获取](https://gitee.com/vip204888/java-p7)**
**由于细节内容实在太多啦，在这里我花了两周的时间把这些答案整理成一份文档了，在这里只把部分知识点截图出来粗略的介绍，每个小节点里面都有更细化的内容！**