CMU_15445_P3_Part4

Sort + Limit Executors + Window Functions + Top-N Optimization

这里的实现比较简单, 就不赘述了, 后续补充一下这部分的优先队列的使用, 以及选择的方式

Window Functions

窗口函数的实现才是这部分的重点

窗口函数介绍

MySQL 窗口函数是一类特殊的 SQL 函数, 用于在查询结果中对数据进行分组和排序的基础上执行计算, 而无需将结果分组到单独的行中. 与聚合函数(如 SUM、AVG 等)相同, 窗口函数会新增通过聚合函数计算新增的列. 与聚合函数(如 SUM、AVG 等)不同, 窗口函数不会减少结果集的行数, 而是为每一行生成一个计算值.

窗口函数的特点

1. 保留行数：窗口函数计算后的结果不会减少数据行, 而是为每一行添加计算结果.
2. 支持分组和排序：通过 PARTITION BY 和 ORDER BY 子句, 可以按组或按顺序计算结果.
3. 与聚合函数结合使用：窗口函数通常与聚合函数结合使用, 为每行提供基于“窗口”的聚合结果.

窗口函数语法

窗口函数在使用时, 通用语法如下:

function_name ( [参数] )
OVER (
    [PARTITION BY column_name]
    [ORDER BY column_name]
    [ROWS | RANGE BETWEEN frame_start AND frame_end]
)

语法说明：

上述语法说明了窗口函数主要由四部分组成, 分别是, 聚合函数, 分组, 排序, 以及窗口帧

• function_name：窗口函数名, 如 ROW_NUMBER、RANK、SUM 等, 通常是聚合函数, 用来生成新的 column 的函数
• PARTITION BY：将数据分组为窗口, 根据 column value 将表中的数据进行分组.
• ORDER BY：定义窗口内的排序方式.
• 窗口帧：定义了窗口的范围, 即对于每一行计算的上下文数据行的范围, ROWS: 基于行的物理位置定义窗口帧, RANGE: 基于排序列的值范围定义窗口帧.

常见的窗口函数

1. 排名函数

• ROW_NUMBER()：为每组数据的每行生成唯一的连续编号.
• RANK()：为每组数据生成排名, 具有相同值的行具有相同排名, 后续排名会跳过.
• DENSE_RANK()：为每组数据生成排名, 具有相同值的行具有相同排名, 后续排名不会跳过.

示例：

sqlCopyEditSELECT
    employee_id,
    department_id,
    salary,
    ROW_NUMBER() OVER (PARTITION BY department_id ORDER BY salary DESC) AS row_number,
    RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rank,
    DENSE_RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS dense_rank
FROM employees;

2. 聚合函数

• SUM()、AVG()、COUNT() 等支持窗口计算.

示例：

sqlCopyEditSELECT
    department_id,
    employee_id,
    salary,
    SUM(salary) OVER (PARTITION BY department_id) AS total_salary,
    AVG(salary) OVER (PARTITION BY department_id) AS avg_salary
FROM employees;

3. 平均值计算

例如计算每个销售员的滑动平均销售额, 范围是当前行前一行到当前行后一行, 使用 ｀ROWS BETWEEN AND｀　限定范围.

示例：

SELECT 
    salesman,
    department,
    sales_amount,
    AVG(sales_amount) OVER (
        PARTITION BY department
        ORDER BY id
        ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
    ) AS moving_avg
FROM sales;

当没有显示的使用窗口帧时, 默认的窗口帧的定义以及范围如下：
１. 对于带 ORDER BY 的窗口函数, 默认帧是 RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW. 表示从分区的开头到当前行.
２. 对于不带 ORDER BY 的窗口函数, 默认帧是整个分区(等价于 RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) 表示整个分区的正题.

BUSTUB 中的窗口函数

BUSTUB 中为了实现起来更加简单, 对窗口函数进行了下面的限制:

1. 省略了窗口帧, 无需处理窗口帧, 只需要处理 PARTITION BY 以及 ORDER BY 两种条件.
2. 在同一个使用窗口函数的 SQL 语句中, 多个窗口函数的 ORDER BY 语句一定完全一致. 例如, 下面的 SQL 查询语句不支持

-- ORDER BY 的条件不一致
SELECT SUM(v1) OVER (ORDER BY v1), SUM(v1) OVER (ORDER BY v2) FROM t1;
-- 一个存在 ORDER BY, 一个不存在 ORDER BY
SELECT SUM(v1) OVER (ORDER BY v1), SUM(v2) OVER () FROM t1;