一文理解 Presto 两种 JOIN 算法实现_过往记忆的博客-程序员宝宝

技术标签: 算法  python  java  mysql  数据库  

我们在 《Presto 中支持的七种 Join 类型》 这篇文章中介绍了 Presto 可用的 JOIN 操作的基础知识,以及如何在 SQL 查询中使用它们。有了这些知识,我们现在可以了解 Presto 的内部结构以及它如何在内部执行 JOIN 操作。本文将介绍 Presto 如何执行 JOIN 操作以及用于 JOIN 的算法。

JOIN 的实现

几乎所有的数据库引擎一次只 JOIN 两个表。即使在 SQL 查询中有两个以上的表要联接,数据库也会联接前两个表并将输出与第三个表联接起来,然后对其余表继续这样做。数据库工程师将连接操作中涉及的这两个表称为构建表(Build Table)和探测表(Probe Table)。

Build Table

构建表是用于创建内存索引的表。通常,在读取探测表之前必须完整读取构建表。

Probe Table

一旦构建表被读取并存储在内存中,探测表就会被逐行读取。从探测表读取的每一行都将根据 join criteria 与构建表进行连接。

929c685a5667cc5a8f74bc71d1b902db.png

如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

Presto 使用优化后的逻辑计划中的右表作为构建表,将逻辑计划中的左表作为探测表。请注意,逻辑计划中的表不必与它们在 SQL 查询中的顺序相同。Presto 有一些基于成本的优化器,它们可以重新排序连接以将最小的表(即构建表)保留在右侧,以便它可以放入内存中。如果连接重新排序优化器被禁用或连接器特定的统计信息(例如 Hive 统计信息)被禁用,则 Presto 将不会对连接查询重新排序。在这种情况下,建议将最小的表保留在连接的右侧,以便 Presto 可以将其用作构建表。

JOIN 算法

数据库根据数据类型和连接类型使用不同的算法来连接两个表。例如,SQL Server 使用 Nested Loop 算法、Merge Join 算法、Hash Join 算法和 Adaptive Join 算法。在撰写本文时,开源的 Presto SQL 引擎采用 Nested Loop 算法和 Hash Join 算法来支持 Presto 中所有不同联接类型。本节简要说明Nested Loop 算法和 Hash Join 算法,并讨论其他算法在 Presto 中的适用性以提高性能。

Nested Loop Algorithm

顾名思义,嵌套循环算法使用嵌套循环连接两个表。下面使用一个数组连接示例来解释嵌套循环连接算法。假设你有两个整数数组,并要求你打印这些数组的笛卡尔积,你会如何解决这个问题?下面给出了一种简单的方法来打印两个数组的笛卡尔积。

public class IteblogNestedLoop {
    public static void main(String[] args) {
        // Construct two arrays
        int[] tableA = {1, 2, 3, 4, 5, 6};
        int[] tableB = {10, 20, 30, 40};
        // Nested loop to print the Cartesian product of two arrays
        for (int x : tableA) {
            for (int y : tableB) {
                System.out.println(x + ", " + y);
            }
        }
    }
}

上面的代码使用两个循环来打印两个数组的笛卡尔积。嵌套循环算法的时间复杂度为 O(n²),因为它必须将探测表中的每一行与构建表中的每一行连接起来。由于需要每个组合,交叉连接操作的执行时间复杂度不能超过 O(n²)。Presto 使用嵌套循环算法来执行 cross join 操作,这就是为什么如果连接表非常大,cross join 需要很长时间。由于 O(n²) 时间复杂度,不建议在没有连接条件的情况下连接两个大表。

Hash Join Algorithm

哈希连接算法为构建表中的列生成哈希键,这些列是用于 JOIN 条件中的,比如 left.x = right.y AND left.z = right.w。每个这样的相等条件称为连接相等条件(join equi criteria)。尽管 equi criteria 术语在数据库领域被广泛使用,但它们也被称为相等条件。为了使用哈希算法,让我们考虑一个打印所有客户及其订单信息的问题。这个问题中使用的 Customer 和 Order 类定义如下。请注意,这两个类都有一个共同的属性:custKey。

class Order {
    String orderKey;
    String custKey;
    double totalPrice;
    public Order(String orderKey, String custKey, double totalPrice) {
        this.orderKey = orderKey;
        this.custKey = custKey;
        this.totalPrice = totalPrice;
    }
    @Override
    public String toString() {
        return "Order: " + orderKey + ", " + custKey + ", " + totalPrice;
    }
}
class Customer {
    String custKey;
    String name;
    public Customer(String custKey, String name) {
        this.custKey = custKey;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Customer: " + name + ", " + custKey;
    }
}

回到问题:我们如何打印所有客户及其订单?了解嵌套循环算法后,可以简单地在循环内应用带有 if 条件的嵌套循环算法,如下所示:

import java.util.*;
public class IteblogHashJoin {
    public static void main(String[] args) {
        List<Customer> probe = List.of(new Customer("c_001", "Alice"),
                                        new Customer("c_002", "Bob"),
                                        new Customer("c_003", "David"));
        List<Order> build = List.of(new Order("o_01", "c_001", 100.0),
                                        new Order("o_01", "c_001", 100.0),
                                        new Order("o_02", "c_001", 150.0),
                                        new Order("o_03", "c_002", 90.0),
                                        new Order("o_04", "c_003", 120.0));
        // Nested loop join
        for (Customer customer : probe) {
            for (Order order : build) {
                if (Objects.equals(customer.custKey, order.custKey)) {
                    System.out.println(customer + " -> " + order);
                }
            }
        }
    }
}

尽管嵌套循环连接可以达到我们的要求,但它的效率很低,因为它在给定 n 个客户和 n 个订单的情况下迭代 n² 次。一个有效的解决方案可以使用一个 Hashtable 来存储所有订单,使用相同的连接条件:custKey 作为哈希键。然后在遍历 Customer 列表时,可以生成 Customer 的散列值。获取具有相同custKey 的订单列表,如下所示:

import java.util.*;
public class IteblogHashJoin {
    public static void main(String[] args) {
        List<Customer> probe = List.of(new Customer("c_001", "Alice"),
                                        new Customer("c_002", "Bob"),
                                        new Customer("c_003", "David"));
        List<Order> build = List.of(new Order("o_01", "c_001", 100.0),
                                        new Order("o_01", "c_001", 100.0),
                                        new Order("o_02", "c_001", 150.0),
                                        new Order("o_03", "c_002", 90.0),
                                        new Order("o_04", "c_003", 120.0));
        // Build the hash map index
        Map<Integer, List<Order>> index = new Hashtable<>();
        for (Order order : build) {
            int hash = Objects.hash(order.custKey);
            index.putIfAbsent(hash, new LinkedList<>());
            index.get(hash).add(order);
        }
        // Hash Join algorithm
        for (Customer customer : probe) {
            int hash = Objects.hash(customer.custKey);
            List<Order> orders = index.get(hash);
            if (orders != null) {
                for (Order order : orders) {
                    if (Objects.equals(customer.custKey, order.custKey)) {
                        System.out.println(customer + " -> " + order);
                    }
                }
            }
        }
    }
}

在上述算法中,使用单独的 LinkedList 来避免哈希冲突,因为同一客户下多个订单的可能性很高。使用 equijoin criteria 里面列的哈希值用于将构建表存储在存储桶中。然后将相同的散列算法应用于探测表的 equijoin criteria 列以查找包含匹配项的桶。尽管 Hash Join 算法的最坏情况时间复杂度是 O(n²),但平均情况下预计为 O(n)。

上述问题可以定义为下面给出的 SQL 查询,以将 Customer 表与 Orders 表连接起来。

SELECT * 
FROM iteblog.customer c 
LEFT JOIN iteblog.orders o 
ON c.custkey=o.orderkey;

具有等连接条件的所有连接操作都使用Presto中的哈希连接算法执行。然而,连接操作并不局限于等效连接标准。例如,如果列值大于或小于另一列的值,则可以连接两个表,如下查询所示:

所有具有 equijoin criteria 的连接操作都使用 Presto 中的哈希连接算法执行。但是,连接操作不限于 equijoin criteria。例如,如果列值大于或小于另一列的值,则可以连接两个表,如下面的查询:

SELECT o.orderkey, l.linenumber 
FROM iteblog.orderkey o 
LEFT JOIN iteblog.lineitem l 
ON o.orderdate < l.shipdate;

Hash Join 算法不适用于具有不等式约束的 join 条件。首先,很难提出一个完美的散列算法来保持输入的不等式属性(即给定 x > b 并不能保证 hash(a) > hash(b))。其次,即使我们提出了一个满足不等式要求的散列函数,我们也不能简单地连接一个桶中的所有值。要加入不相等的行,应该匹配大于/小于给定列的每一行。因此,Presto 使用带 filter 的嵌套循环算法而不是散列连接算法来执行具有非等连接条件的连接。

尽管开源的 Presto SQL 仅使用 Nested Loop 算法和 Hash Join 算法进行连接操作,但 Merge Join 是关系数据库中使用的另一种众所周知的算法,有一些大数据计算引擎也支持 Merge Join ,比如 Spark。以下部分介绍了 Merge Join 算法,并解释了 Presto 社区为何不考虑添加对 Merge Join 算法的支持。

Merge Join

Merge Join 算法来自著名的 Merge-Sort 算法。归并排序算法有两个阶段:排序和合并。假设两个数组已经排序,它们可以以 O(n) 的时间复杂度合并。Presto 可以通过使用 equijoin criteria 中使用的列对构建表和探测表进行排序,然后通过执行合并操作来实现该算法。忽略排序部分,merge join 算法的性能有望优于上述算法,但 Presto 社区发现它需要在内存中对两个表进行排序,这在大数据世界中很耗时,考虑到有限的内存,甚至可能是不可行的。但是,如果有机会在底层数据源中对数据进行排序,则合并连接算法可能是一个更好的候选算法。

在我看来,如果构建表足够小可以容纳在内存中,那么对它进行排序并使用二分搜索算法将探测表行与构建表进行比较不会是一个糟糕的选择。它可以改进具有不等式条件(例如大于或小于)的连接操作。Presto 还支持关系数据库,与大数据存储相比,这些数据库的数据量通常较少。如果连接来自关系数据库的两个表,或者来自关系数据库的表与来自 Hadoop 文件存储的表连接,则有机会要求底层关系数据库返回排序结果。因此,我觉得即使在大数据领域,Merge Join 仍然是一个值得考虑的候选。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/w397090770/article/details/121463526

智能推荐

嵌入式C语言高手炼成之内存操作篇_chooseboy的博客-程序员宝宝

数据指针在嵌入式系统的编程中,常常要求在特定的内存单元读写内容,汇编有对应的MOV指令,而除C/C++以外的其它编程语言基本没有直接访问绝对地址的能力。在嵌入式系统的实际调试中,多借助C语言指针所具有的对绝对地址单元内容的读写能力。以指针直接操作内存多发生在如下几种情况:  (1)某I/O芯片被定位在CPU的存储空间而非I/O空间,而且寄存器对应于某特定地址;  (2)两...

春江花月夜_congbian2159的博客-程序员宝宝

春江潮水连海平,海上明月共潮生。 滟滟随波千万里,何处春江无月明? 江流宛转绕芳甸,月照花林皆似霰。 空里流霜不觉飞,汀上白沙看不见。 江天一色无纤尘,皎皎空中孤月轮。 江畔何人初见月?江月何年初照人? 人生代代无穷已,江月年年...

WordPress不使用插件实现分页_寂寞的烟客的博客-程序员宝宝

WordPress默认的分页只有 “下一页”和 “上一页”. 如果你博客里面文章比较多,想让分页更好看一些的话那我建议你不要使用博客的默认链接,而是使用更漂亮点的分页导航.我的博客中使用的分页就是Habitat . 向下拉就可以在下面看见文章的分页按钮.为啥需要使用它们呢? 因为它们可以让你很简单的就知道文章的导航地址,很容易就知道有多少文章,有多少页.

Oracle MFT 12c 快速、灵活的企业文件传输方案_Steel Ren的博客-程序员宝宝

已有文件传输方案的问题因为丢失或者更糟的情况,暴露了合作伙伴的敏感文件,对企业的业务造成影响?大文件阻塞了系统,使关键业务流程运行缓慢?现有的文件传输解决方案经常会造成文件的丢失或损坏?能否追踪到哪一个部门、合作伙伴或者员工使用了最多的资源?现有的工具是否难于诊断文件传输的问题?在构建、监控和维护文件传输时,是否受制于现有的资源?产品概览即使在当今动态的、面向事件的业务环境当中,对

BIO、NIO和AIO的Java实现与研究_zzuli_xiaomingke的博客-程序员宝宝_bio,nio,aio 代码实现

基于Reactor的网络通信模型的相关研究名词解释还是先从最简单的两个内容说起:同步和异步、阻塞和非阻塞。这两个概念在网络上可以说是千人千面,每人都能说出来个自己的理解,然后在评论区开始各种撕,在这里就简单说一下我自己的理解,如果我说的不对,那我有罪,我先说了。同步与异步同步和异步描述的是通信双方通信方式的差异。如果调用方发起调用后被调用方都直接返回,而在真正完成后,再通过回调函数等模式告知调用者结果,这种方式就是异步通信。反之,如果调用方发起请求后被调用方在处理完毕后再带着结果返回,这种方式称之

算法基础_heart荼毒的博客-程序员宝宝

算法,一直觉得是一个很抽象的东西。大三上算法课,从空间复杂度到时间复杂度,从自然语言到伪代码,再到后面的Java代码,老师讲台上讲的激情澎湃,然而,算法丝毫没引起我的兴趣。刚工作第一年,有段时间跟主管做一款图像编辑类的应用,很羡慕他用C++写图像处理算法,于是,买了很多本算法书,基本都是翻完前面几章基础的排序算法和查找算法。工作三年,说句实在的,设计模式还经常用到,什么乱七八糟的或...

随便推点

python+mitmdump爬虫实战(1/3)(附源码)_你们卷的我睡不着QAQ的博客-程序员宝宝

总体步骤:(一)首先下载夜神模拟器(二)模拟器配置(三)下载mitmproxy与mitmdump并安装证书(四)试验一下(五)正式爬取数据我们接下来用三篇文章来简要说下爬取步骤:(一)首先下载夜神模拟器自己去官网下载就行然后点击新建一个安卓5的系统点那个播放键就可以启动模拟器了在那里面下载个抖音app为了以后方便控制,可以在上面的设置(齿轮状那里)(1)看看是否开启root(2)在齿轮左面这里点第一个,设置置顶(二)模拟器配置在应用中心下载xposed框架,这是

Unity编辑器游戏,打地鼠(鸡你太美)_OnClick9927的博客-程序员宝宝

Unity编辑器游戏,打地鼠(鸡你太美)纯属娱乐,守护最好的坤坤具体操作,查看 视频地址具体游戏内容参见 游戏内容

javascript通用工具_九星丶宵河的博客-程序员宝宝

$(function() { /** * 自动生成分页 * * @data 为分页实体 * @suffix 分页标签后缀 * @pageTargetId 分页打印的目标ID * @statisticsTargetId 统计数据的目标ID * */ function printPage(data, suffix, pageTargetId, statisti

今天开始正式使用csdn的博客_jakelong的博客-程序员宝宝

很久没有使用CSDN的博客了。今天开始正式的使用这个博客,也希望大家关注我。我会把我对于设计与教学的一些想法与经验发布上来的。

计算机组成原理实验J1接J2,计算机组成原理实验指导书.doc_庄黑胖-伍拾万的博客-程序员宝宝

计算机组成原理实验指导书《计算机组成原理》实 验 指 导 书唐山学院计算科学与技术实验教学中心2011年12月前 言一.计算机组成原理实验的任务计算机组成原理实验是计算机组成原理课程的一部分,它的任务是:1.通过实验进一步了解和掌握计算机原理的基本概念,对CPU内部的运算功能、控制功能、总线结构、指令系统的设计和微指令的实现及CPU内部如何工作有直观、深刻的认识。2.培养学生分析问题...

推荐文章

热门文章

相关标签