总结自chatgpt

一些sql的谓词底层逻辑

一条sql需要经历以下几个过程

DB的一些名词

1.DML(Data Manipulation Language):数据操作语言，主要用于操作数据库中的数据，例如增、删、改、查等操作。DML的作用是对数据库中的数据进行操作和维护。DML代表”神”，因为它是数据库中最基本也是最重要的操作之一，没有DML就没有数据库的实际意义。

2.DDL（Data Definition Language）：数据定义语言，主要用于定义数据库中的结构，例如创建、删除、修改表、索引等操作。DDL的作用是对数据库中的结构进行管理和维护。DDL代表”恶魔”，因为它可以直接修改数据库的结构，如果使用不当会导致数据库的完整性和稳定性出现问题。

3.Multi-statement：多语句操作，主要用于同时执行多个语句，例如创建存储过程、触发器、批量插入数据等。Multi-statement的作用是简化数据库操作，提高数据库的效率。Multi-statement代表”魔”，因为它可以在短时间内执行多个语句，但是如果语句之间存在依赖关系或错误，会导致数据不一致或者出现其他问题。

bison+flex

Bison 是一个生成器工具，用于生成解析器（parser）代码。解析器可以解析和分析输入的文本，并将其转换为更高级别的结构，例如语法树或抽象语法树。Bison 基于 LALR（Look-Ahead Left-to-Right）语法分析算法，可以处理上下文无关语法（Context-Free Grammar）。

Flex 是另一个生成器工具，用于生成词法分析器（lexical analyzer）代码。词法分析器可以将输入的文本分割成一个个的词法单元（tokens），例如关键字、标识符、操作符等等。Flex 基于正则表达式匹配算法，可以处理大量的词法单元。

Bison 和 Flex 通常一起使用，用于构建编译器、解释器、语言处理工具等等。使用这两个工具，我们可以将输入的文本转换为更易于处理的结构，以便进行后续的分析和处理。例如，我们可以使用 Bison 和 Flex 构建一个 SQL 查询语句解析器，将用户输入的 SQL 查询语句转换为语法树或抽象语法树，然后进行优化、执行等操作。

需要注意的是，Bison 和 Flex 可以独立使用，也可以一起使用。如果只需要进行词法分析，可以使用 Flex 单独生成词法分析器。如果需要进行语法分析，可以使用 Bison 单独生成解析器。如果需要进行完整的文本解析，可以使用两者配合使用。

使用也很简单

    flex *.l
    bison

bison和pegtl的区别

bison生成的代码可重用的含义

Bison 生成的代码是可重用的，是指在一次语法分析的过程中，Bison 可以生成语法分析树，这棵语法分析树可以被重复利用。也就是说，一旦生成了语法分析树，就可以在该树的基础上进行多次语法分析，而不必每次都重新解析源代码。

这种可重用性是由于Bison 的生成代码使用了状态机的思想。Bison 将语法规则转换成了状态机，生成的代码会跟踪状态机的当前状态，并根据当前状态来决定下一步的操作，最终构建出语法分析树。这种状态机的思想使得生成的代码具有可重用性，因为只要输入的源代码不变，状态机就不会变化，也就不需要重新解析一次源代码。

因此，Bison 可以重复使用已经构建好的语法分析树来处理不同的输入，这种方式比每次都重新解析源代码更加高效，尤其是对于大型项目和长时间运行的程序来说，可以显著提高程序的性能和效率。

bison的特点的原因

bison的具体优化

具体包含以下四种优化

1.自动机优化

2.Lookahead优化

3.GLR解析

具体做法:

1.自动机优化：Bison在自动机构建过程中会尝试进行状态合并。例如，当两个状态具有相同的属性时，Bison会将这两个状态合并为一个状态，从而减少状态数。这样可以大幅提高自动机分析的效率。举例来说，对于如下的状态转换图：

4和5会合并

state 1:
  on input 'a' go to state 2
  on input 'b' go to state 3

state 2:
  on input 'c' go to state 4

state 3:
  on input 'c' go to state 5

state 4:
  on input 'd' go to state 6

state 5:
  on input 'd' go to state 6

2.Lookahead优化：Bison的Lookahead优化主要包括计算follow集合等技术。例如，在进行语法分析时，Bison需要通过Lookahead来确定最佳的动作。为了提高Lookahead的效率，Bison会计算每个非终结符的follow集合，即在每个非终结符后面可能出现的终结符集合。然后，Bison会使用这些follow集合来缩小Lookahead的范围，从而提高分析器的效率。举例来说，对于如下的文法：

expr : term '+' term
     | term '-' term
     | term

term : factor '*' factor
     | factor '/' factor
     | factor

factor : '(' expr ')'
       | NUM

3.GLR解析：Bison的GLR解析主要包括冲突处理等技术。例如，在解析含有二义性的语法时，Bison会使用GLR解析器。为了提高GLR解析的效率，Bison会尝试优化冲突处理。其中一种优化方式是延迟冲突处理，即将可能发生冲突的动作推迟到后面再处理，从而避免不必要的冲突检测。举例来说，对于如下的文法：

expr : expr '+' expr
     | expr '-' expr
     | NUM

在解析1 + 2 - 3时，Bison会遇到一个移进-规约冲突(又可以移进-又可以规约2)。为了避免不必要的冲突检测，Bison会推迟决定如何处理这个冲突

SQL优化器

现实常见的sql优化器包括

Oracle 的 Cost-Based Optimizer (CBO)、Microsoft SQL Server 的 Query Optimizer、MySQL 的 Optimizer、PostgreSQL 的 Query Planner 等

常见的SQL优化方式

1.查询重写

例如多关联表的时候，优化器会将其转化为更高效的查询方式
比如如果是between…and 会转化为对应的<和>
优化前

SELECT books.book_id, books.book_title, authors.author_name
FROM books
INNER JOIN books_authors ON books.book_id = books_authors.book_id
INNER JOIN authors ON books_authors.author_id = authors.author_id
WHERE books.book_title LIKE '%Python%';

优化后

SELECT books.book_id, books.book_title, authors.author_name
FROM books
INNER JOIN books_authors ON books.book_id = books_authors.book_id
INNER JOIN authors ON books_authors.author_id = authors.author_id
WHERE books.book_id IN (
    SELECT book_id FROM books
    WHERE book_title LIKE '%Python%'
);

这里把like优化成了in，完成了一个查询重写的过程

2.谓词下推

首先明确什么是sql的谓词

SELECT、WHERE、JOIN、HAVING、GROUP BY 这些操作都是sql的谓词

那么是怎么做下推操作的呢？

看这个例子

SELECT SUM(quantity), SUM(quantity*unit_price)
FROM orders
JOIN order_details ON orders.order_id = order_details.order_id
WHERE orders.customer_id = 123
AND order_details.product_id = 456
AND orders.order_date >= '2019-01-01'

不进行谓词下推的话，会先join两张表，然后对join的所有数据进行过滤

但是如果进行谓词下推的话。首先，将orders.customer_id = 123下推，过滤出顾客ID为123的订单；然后将order_details.product_id = 456下推，进一步过滤出购买商品ID为456的订单；最后将orders.order_date >= ‘2019-01-01’下推，过滤出2019年1月1日之后的订单。这样，只有符合这三个条件的行才会被传递给查询引擎进行进一步的处理，减少了查询引擎需要处理的数据量，提高了查询性能。

3.关联重组

关联重组一般用于left join和right join，比如你左表比较大，右表比较小，那么需要把左表换成右表

4.分区裁剪

分区裁剪是一种SQL优化技术，它可以显著提高查询效率，特别是对于大型分区表查询。分区裁剪通过识别查询语句中的谓词条件并确定哪些分区不包含需要查询的数据，从而排除这些不需要扫描的分区，减少了查询所需的IO和CPU资源。

例如下面的表和分区

CREATE TABLE sales (
  id INT PRIMARY KEY,
  date DATE,
  amount DECIMAL(10, 2),
  country VARCHAR(50)
)
PARTITION BY RANGE (YEAR(date))
(
  PARTITION sales_2018 VALUES LESS THAN (2019),
  PARTITION sales_2019 VALUES LESS THAN (2020),
  PARTITION sales_2020 VALUES LESS THAN (2021),
  PARTITION sales_2021 VALUES LESS THAN (2022)
);

对于我们这样一条查询语句来说

SELECT SUM(amount)
FROM sales
WHERE country = 'USA' AND date BETWEEN '2020-10-01' AND '2021-03-31';

在执行查询之前，分区裁剪会检查查询条件中的date和country两个字段是否与分区键相关。由于分区键是YEAR(date)，因此查询条件中的date字段与分区键相关。分区裁剪会使用查询条件中的日期范围来确定需要扫描的分区。在这个例子中，需要扫描的分区包括sales_2020和sales_2021。

但是要记住，如果要使用分区裁剪，那么你的查询条件一定要和分区键有关

5.索引优化

这个不用多说了

6.子查询优化

例子：
假设有两张表，一张是“员工表”，包含员工的ID、姓名、部门等信息，另一张是“工资表”，包含员工的ID、工资等信息。现在需要查询部门为“销售部”的员工的平均工资，并按照工资从高到低排序。

首先，我们可以写出一个子查询的SQL语句：

SELECT AVG(salary) FROM salary_table WHERE employee_id IN (SELECT employee_id FROM employee_table WHERE department = 'Sales')

这个时候，子查询优化会把这个sql修改为join

SELECT AVG(salary) FROM salary_table t1 JOIN employee_table t2 ON t1.employee_id = t2.employee_id WHERE t2.department = 'Sales'

这样，因为子查询的信息需要存储在内存，但是你join出来的信息占用内存比较少，所以修改为join之后更加优化了

7.统计信息优化

假设有一个订单表(order)，其中包含了订单的id、顾客id(customer_id)、订单时间(order_time)等信息。现在需要查询顾客id为12345的顾客在2022年1月份的订单数量。可以使用以下SQL语句进行查询：

SELECT COUNT(*) FROM order WHERE customer_id = 12345 AND order_time >= '2022-01-01' AND order_time < '2022-02-01';

为了优化这个查询，需要考虑对表order的统计信息进行优化。具体来说，需要收集和更新表order中的customer_id和order_time两个列的统计信息，包括数据分布、数据密度、唯一值的数量等信息。可以使用以下SQL语句进行统计信息收集和更新：

SQL执行引擎

物理执行计划的生成

考虑以下这个SQL查询语句：

SELECT a.*, b.*
FROM table_a a
JOIN table_b b ON a.id = b.id
WHERE a.name = 'John' AND b.age > 20;

对于这个查询语句，可能生成的执行计划如下：

┌─Hash Join (inner join, id=1)───
│  ├─Table Scan on table_a a (id=2)───
│  └─Hash Join (inner join, id=3)───
│     ├─Table Scan on table_b b (id=4)───
│     └─Hash Probe on table_a a (id=5)───
└─Filter: a.name = 'John' and b.age > 20

该执行计划由三个操作符组成：两个Hash Join操作符和一个Filter操作符。其中第一个Hash Join操作符使用表a的id和表b的id进行连接，生成一个新的中间结果；第二个Hash Join操作符则使用该中间结果和表a进行连接，生成最终结果；最后的Filter操作符根据查询条件过滤掉不符合要求的记录。

不同的JOIN算法

HASH JOIN的底层实现逻辑

1.对于连接操作的两个表，先选取其中一个表（通常是小表）的连接键列作为哈希表的键，对该表进行哈希操作，生成哈希表，将每行数据映射到哈希表中的一个桶。

2.对于另一个表（通常是大表），对其连接键列进行哈希操作，并将哈希值映射到哈希表中的一个桶中。如果哈希表中该桶中有数据，则在该桶中查找匹配的数据，进行连接操作。

3.如果哈希表中该桶中没有数据，则表示该桶中没有与该行数据匹配的数据，继续对下一行数据进行哈希操作，直到所有数据都处理完毕。

4.如果需要连接的两个表中有多个连接键列，则需要先将这些列组合成一个联合键，然后再进行哈希操作。

FILTER 算法

FILTER算法的基本思路是，通过过滤掉那些不可能匹配的数据来减少需要进行HASH JOIN操作的数据量。具体来说，FILTER算法可以通过以下步骤来实现：

1.将大表按照HASH JOIN的连接列进行分组，生成多个小表。

2.对于小表中的每一行数据，在另一个表中查找是否有匹配的数据。

3.如果另一个表中没有匹配的数据，就不将该行数据加入到结果集中，从而减少需要进行HASH JOIN操作的数据量。

4.如果另一个表中有匹配的数据，就将该行数据加入到结果集中，并继续处理下一行数据。