Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

17 | 如何正确地显示随机消息? #27

Open
git-zjx opened this issue Jul 31, 2019 · 0 comments

Comments

@git-zjx
Copy link
Owner

commented Jul 31, 2019

对于显示随机消息,一般会想到用 order by rand() 实现,以下是 explain 结果
59a4fb0165b7ce1184e41f2d061ce350
Extra 字段表示会用到临时表,会进行排序操作

内存临时表
对于内存表,回表过程只是简单地根据数据行的位置,直接访问内存得到数据,根本不会导致多访问磁盘。优化器没有了这一层顾虑,那么它会优先考虑的,就是用于排序的行越小越好了,所以,MySQL 这时就会选择 rowid 排序。

这条语句的执行流程是这样的:

  1. 创建一个临时表。这个临时表使用的是 memory 引擎,表里有两个字段,第一个字段是 double 类型,为了后面描述方便,记为字段 R,第二个字段是 varchar(64) 类型,记为字段 W。并且,这个表没有建索引。
  2. 从 words 表中,按主键顺序取出所有的 word 值。对于每一个 word 值,调用 rand() 函数生成一个大于 0 小于 1 的随机小数,并把这个随机小数和 word 分别存入临时表的 R 和 W 字段中,到此,扫描行数是 10000。
  3. 现在临时表有 10000 行数据了,接下来你要在这个没有索引的内存临时表上,按照字段 R 排序。
  4. 初始化 sort_buffer。sort_buffer 中有两个字段,一个是 double 类型,另一个是整型。
  5. 从内存临时表中一行一行地取出 R 值和位置信息,分别存入 sort_buffer 中的两个字段里。这个过程要对内存临时表做全表扫描,此时扫描行数增加 10000,变成了 20000。
  6. 在 sort_buffer 中根据 R 的值进行排序。注意,这个过程没有涉及到表操作,所以不会增加扫描行数。
  7. 排序完成后,取出前三个结果的位置信息,依次到内存临时表中取出 word 值,返回给客户端。这个过程中,访问了表的三行数据,总扫描行数变成了 20003。

2abe849faa7dcad0189b61238b849ffc

位置信息 rowid 是每个引擎用来唯一标识数据行的信息。

  • 对于有主键的 InnoDB 表来说,这个 rowid 就是主键 ID;
  • 对于没有主键的 InnoDB 表来说,这个 rowid 就是由系统生成的;
  • MEMORY 引擎不是索引组织表。在这个例子里面,你可以认为它就是一个数组。因此,这个 rowid 其实就是数组的下标。

磁盘临时表

tmp_table_size这个配置限制了内存临时表的大小,默认值是 16M。如果临时表大小超过了 tmp_table_size,那么内存临时表就会转成磁盘临时表
磁盘临时表使用的引擎默认是 InnoDB,是由参数 internal_tmp_disk_storage_engine 控制的
当使用磁盘临时表的时候,对应的就是一个没有显式索引的 InnoDB 表的排序过程

MySQL 5.6 版本引入了优先队列排序算法,可以减少很多计算量。
e9c29cb20bf9668deba8981e444f6897

随机排序方法-1

  1. 取得这个表的主键 id 的最大值 M 和最小值 N;
  2. 用随机函数生成一个最大值到最小值之间的数 X = (M-N)*rand() + N;
  3. 取不小于 X 的第一个 ID 的行。
    这个方法效率很高,因为取 max(id) 和 min(id) 都是不需要扫描索引的,而第三步的 select 也可以用索引快速定位,可以认为就只扫描了 3 行。但实际上,这个算法本身并不严格满足题目的随机要求,因为 ID 中间可能有空洞,因此选择不同行的概率不一样,不是真正的随机

随机排序方法-2

  1. 取得整个表的行数,并记为 C。
  2. 取得 Y = floor(C * rand())。 floor 函数在这里的作用,就是取整数部分。
  3. 再用 limit Y,1 取得一行。

MySQL 处理 limit Y,1 的做法就是按顺序一个一个地读出来,丢掉前 Y 个,然后把下一个记录作为返回结果,因此这一步需要扫描 Y+1 行。再加上,第一步扫描的 C 行,总共需要扫描 C+Y+1 行,执行代价比随机算法 1 的代价要高

@git-zjx git-zjx added this to MySQL实战45讲 in MySQL Aug 1, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
1 participant
You can’t perform that action at this time.