盘点那些自带高级算法的SQL

Ne0inhk

— 17 min read
盘点那些自带高级算法的SQL
在这里插入图片描述


文章目录

引言：SQL是算法的宝库

SQL（Structured Query Language）是一种声明式语言。用户只需指定“想要什么”（What），而无需关心“如何实现”（How）。这个“How”就是数据库管理系统（DBMS）如 PostgreSQL、MySQL、Oracle 等需要解决的问题。数十年来，数据库领域的专家们将无数经典的算法和数据结构优化后融入DBMS的核心引擎中，使得一条简单的SQL语句背后可能是数个诺贝尔奖级别算法的高效协作。

理解这些算法，不仅能让我们写出更高效的SQL，更能将这些思想应用于其他的编程和系统设计场景中。

第一章：排序算法（ORDER BY）

SQL语句：SELECT * FROM users ORDER BY age DESC, name ASC;

原理与实现

DBMS不会在所有场景下都使用一种排序算法。它会根据数据量、内存大小、是否涉及索引等因素智能选择最优策略。

  1. 内存排序（当数据可完全放入内存）：
    • 快速排序（Quicksort）：是内排序中最常见的算法。它是一种分治算法，通过选择一个“基准”元素将数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。平均时间复杂度为O(n log n)。
    • 内省排序（Introsort）：是C++ STL sort() 的实现，也可能是现代DBMS的选择。它结合了快速排序、堆排序和插入排序的优点：
      • 开始使用快速排序。
      • 当递归深度超过一定 level（如 log(n)）时，转为堆排序（Heapsort）以避免快排的最坏情况O(n²)。
      • 当数据量很小（如 < 16）时，转为插入排序（Insertion Sort），因为插入排序在小数组上常数因子极小，非常快。
  2. 外部排序（当数据量巨大，无法放入内存）：
    • 归并排序（Merge Sort）：是外部排序的基石。其核心是“分而治之”和“归并”。
    • 实现步骤（以两路归并为例）：
      • 阶段一：排序阶段 (Run Generation)：
        • 数据库每次读取一定数量的数据页（Page）到内存中。
        • 用内排序算法（如快排）对这些数据进行排序。
        • 将排序好的数据作为一个“有序段”（Sorted Run）写回磁盘。重复此过程，直到处理完所有数据，生成多个有序段。
      • 阶段二：合并阶段 (Merge Phase)：
        • 打开所有有序段文件。
        • 每次从每个有序段中读取一部分数据到内存的“输入缓冲区”。
        • 使用一个“最小堆”或简单的比较，从所有缓冲区当前元素中选出最小的（或最大的，取决于ORDER BY）输出到“输出缓冲区”。
        • 输出缓冲区满则写回磁盘，并清空。
        • 当一个输入缓冲区为空时，从对应的有序段文件中读取下一批数据。
        • 重复直到所有有序段的数据都被处理完毕，最终生成一个完全有序的大文件。

代码文字实现（外部排序简化版）：

defexternal_sort(data_iterator, chunk_size, key_func):"""外部排序生成器"""# 阶段一：生成有序段 runs =[]whileTrue: chunk =[]try:for _ inrange(chunk_size): chunk.append(next(data_iterator))except StopIteration:passifnot chunk:break chunk.sort(key=key_func)# 内存排序 run_file = write_chunk_to_disk(chunk) runs.append(run_file)# 阶段二：K路归并# 打开所有有序段文件，创建文件对象迭代器 iterators =[iter(read_chunk_from_disk(run))for run in runs]# 使用堆进行归并。堆元素为 (value, run_index, iterator) heap =[]for i, it inenumerate(iterators):try: value =next(it) heapq.heappush(heap,(key_func(value), i, value, it))except StopIteration:passwhile heap: key, idx, value, it = heapq.heappop(heap)yield value try: next_value =next(it) heapq.heappush(heap,(key_func(next_value), idx, next_value, it))except StopIteration:pass# 清理临时文件for run in runs: os.remove(run)
扩展应用
  • 大数据处理：Hadoop/Spark中的排序是分布式外部排序的典范。Map阶段在各自节点上生成有序段，Reduce阶段进行归并。
  • 文件合并：合并多个已排序的日志文件、数据文件。
  • 内存受限环境：在嵌入式系统或移动设备上处理大型数据集。

第二章：聚合与哈希算法（GROUP BY, COUNT(DISTINCT)）

SQL语句：SELECT department, COUNT(*), AVG(salary) FROM employees GROUP BY department;
SQL语句：SELECT COUNT(DISTINCT product_id) FROM orders;

原理与实现
  1. 哈希聚合（Hash Aggregation）：
    • 原理：使用一个哈希表，键是GROUP BY的列的组合（department），值是聚合函数的中间状态（如count、sum、min等）。
    • 实现步骤：
      • 初始化一个空哈希表。
      • 扫描表employees的每一行。
      • 对每一行，计算GROUP BY键的哈希值。
      • 在哈希表中查找该键。
        • 如果找到，则更新该键对应的聚合状态（例如，count++, sum += salary）。
        • 如果未找到，则插入该键，并初始化其聚合状态（例如，count=1, sum=salary）。
      • 扫描完成后，遍历哈希表，计算最终值（如 AVG = sum / count）并输出结果。
    • 优势：通常只需要单次表扫描，效率极高，时间复杂度近似O(n)。
  2. 排序聚合（Sort Aggregation）：
    • 原理：先对数据按照GROUP BY的列进行排序。排序后，相同的键会紧挨在一起。然后只需按顺序扫描排序后的数据，每当键发生变化时，就输出上一个组的聚合结果。
    • 实现步骤：
      • 对employees表按department排序（使用上文的外部排序）。
      • 初始化一个变量来保存当前组的键和聚合状态。
      • 遍历排序后的数据流：
        • 如果当前行的department与当前组的键相同，则更新聚合状态。
        • 如果不同，则输出当前组的结果，然后重置聚合状态为新的键。
    • 应用场景：当需要有序的输出结果时，或者当哈希表所需内存超过可用内存时（因为排序可以使用磁盘）。
  3. COUNT(DISTINCT) 与 HyperLogLog：
    • 朴素算法：使用哈希集（HashSet）。维护一个包含所有不同值的集合，最后返回集合的大小。内存使用为O(n)，对于海量数据不可行。
    • 超级算法：HyperLogLog (HLL)：
      • 原理：一种概率算法，用于估算巨大集合的基数（不同元素的个数）。它基于一个巧妙的观察：在一个随机比特流中，连续出现0的最大次数k与基数的关系大约是2^k。
      • 实现简述：
        • 使用一个哈希函数h(x)，将每个元素x映射为一个比特串。
        • 将比特串分桶（例如，前4位用于确定桶索引m，后60位用于计算前导0的个数ρ）。
        • 每个桶m只记录所有映射到该桶的元素中，最大的前导0的个数max_ρ[m]。
        • 估算所有桶的调和平均数：E = α_m * m^2 / (2^{-max_ρ[0]} + 2^{-max_ρ[1]} + ... + 2^{-max_ρ[m-1]})。
        • 应用一些修正公式来纠正误差。
      • 优势：内存占用极小（通常只需要KB级别），就能以约1%的误差估算十亿级别数据的基数。

代码文字实现（哈希聚合简化版）：

defhash_aggregate(data_iterator, group_by_keys, aggregate_funcs):"""哈希聚合实现GROUP BY""" hash_table ={}# Key: tuple of group_by values, Value: list of aggregate statesfor row in data_iterator:# 提取分组键 key =tuple(getattr(row, k)for k in group_by_keys)# 查找或初始化聚合状态if key notin hash_table:# 初始化每个聚合函数的初始状态# 例如：COUNT->0, SUM->0, AVG->(sum, count) states =[func.init()for func in aggregate_funcs] hash_table[key]= states else: states = hash_table[key]# 更新每个聚合函数的状态for i, func inenumerate(aggregate_funcs): states[i]= func.accumulate(states[i], row)# 计算最终结果并产出for key, states in hash_table.items(): result =list(key)for state, func inzip(states, aggregate_funcs): result.append(func.finalize(state))yield result # 定义聚合函数接口classCount:definit(self):return0defaccumulate(self, state, row):return state +1deffinalize(self, state):return state classAvg:definit(self):return(0,0)# (sum, count)defaccumulate(self, state, row): s, c = state return(s + row.salary, c +1)deffinalize(self, state): s, c = state return s / c if c !=0else0
扩展应用
  • 哈希表：无处不在。Python的dict、Java的HashMap、Redis的Hashes、负载均衡中的会话保持。
  • HyperLogLog：
    • 网站UV统计：统计每天访问网站的不同用户数，内存消耗极低。
    • 数据库查询优化：用于提前估算Join操作的结果集大小，帮助优化器选择执行计划。
    • 网络流量分析：统计网络中不同源IP的数量。

第三章：连接算法（JOIN）

SQL语句：SELECT * FROM orders JOIN customers ON orders.customer_id = customers.id;

原理与实现

JOIN是关系数据库最核心的操作，算法选择极其复杂，取决于表大小、索引、内存等因素。

  1. 嵌套循环连接（Nested Loop Join）：
    • 原理：最简单的连接算法。双重循环，外层循环遍历外表（通常是小表），内层循环遍历内表，检查连接条件。
    • 适用场景：当其中一张表非常小的时候。性能极差，复杂度O(n*m)。
  2. 哈希连接（Hash Join）：
    • 原理：与哈希聚合类似，是等值连接（=）最常用的算法。
    • 实现步骤：
      • 构建阶段：扫描较小的表（构建表），将其连接键作为键，整行数据（或所需列）作为值，构建一个内存哈希表。
      • 探测阶段：扫描较大的表（探测表），对其每一行，计算连接键的哈希值，并在构建的哈希表中查找。如果找到，则将两行合并输出。
    • 优势：平均复杂度接近O(m + n)，非常高效。
    • 溢出处理：如果构建表太大，内存放不下，DBMS会使用混合哈希连接，将其分区到磁盘上，然后对每个分区分别进行哈希连接。
  3. 排序归并连接（Sort-Merge Join）：
    • 原理：先对两个表按连接键进行排序，然后使用两个指针，像归并排序的合并步骤一样，遍历两个有序表，找到匹配的行。
    • 实现步骤：
      • 将表A和表B按连接键排序。
      • 初始化两个指针，分别指向表A和表B的第一行。
      • 比较两个指针所指行的连接键：
        • 如果 A.key < B.key，则移动A的指针。
        • 如果 A.key > B.key，则移动B的指针。
        • 如果 A.key == B.key，这是一个匹配！ 但需要注意，因为可能有多个相同键的行（重复键）。此时需要找出A和B中所有拥有相同键的行集，输出它们的笛卡尔积，然后继续移动指针。
    • 适用场景：当输入数据已经有序，或者需要有序的输出时。对于非等值连接（如<, BETWEEN）也有效。

实现：

for outer_row in outer_table:for inner_row in inner_table:if join_condition(outer_row, inner_row):yield combine(outer_row, inner_row)

代码文字实现（哈希连接简化版）：

defhash_join(outer_table, inner_table, outer_key, inner_key):"""哈希连接实现"""# 构建阶段：假设inner_table可以放入内存 hash_map ={}for inner_row in inner_table: key =getattr(inner_row, inner_key)if key notin hash_map: hash_map[key]=[] hash_map[key].append(inner_row)# 处理重复键的情况# 探测阶段for outer_row in outer_table: key =getattr(outer_row, outer_key)if key in hash_map:for inner_row in hash_map[key]:yield combine_rows(outer_row, inner_row)
扩展应用
  • 哈希连接：是Spark SQL、Pandas Merge等大数据工具中Join操作的默认选择之一。
  • 排序归并连接：是MapReduce范式中的核心操作（Shuffle和Reduce阶段本质上就是一个巨大的排序归并连接）。
  • 思想通用性：“构建-探测”模式广泛应用于缓存、编译器符号表、DNS解析等场景。

第四章：窗口函数（OVER, RANK, ROW_NUMBER）

SQL语句：SELECT name, department, salary, RANK() OVER (PARTITION BY department ORDER BY salary DESC) as dept_rank FROM employees;

原理与实现

窗口函数在不聚合数据的情况下，对数据的“窗口”进行计算。它需要数据分区和分区内排序。

  1. 基本实现：
    • 首先，根据PARTITION BY子句对数据进行分区（类似GROUP BY，使用哈希或排序）。
    • 然后，在每个分区内，根据ORDER BY子句进行排序。
    • 最后，按顺序遍历每个分区的每一行，计算窗口函数。
  2. 特定函数的实现：
    • ROW_NUMBER()：只需在分区内维护一个简单的计数器。
    • RANK()：需要跟踪当前值和上一个值。如果当前值与上一个值相同，则排名不变，否则排名等于当前的行号。
    • LAG()/LEAD()：需要在分区内维护一个大小为N（偏移量）的滑动窗口或队列，以便访问前面或后面的行。

代码文字实现（RANK()简化版）：

defcalculate_rank(data, partition_by, order_by):"""计算RANK()窗口函数"""# 1. 分区：使用哈希表进行分区 partitions ={}for row in data: key =tuple(getattr(row, col)for col in partition_by)if key notin partitions: partitions[key]=[] partitions[key].append(row)# 2. 对每个分区排序for key, rows in partitions.items(): rows.sort(key=lambda x:[getattr(x, col)for col in order_by], reverse=True)# 3. 计算排名 current_rank =1 prev_value =Nonefor i, row inenumerate(rows): current_value =tuple(getattr(row, col)for col in order_by)if prev_value isNoneor current_value != prev_value: current_rank = i +1# 排名等于行号setattr(row,'dept_rank', current_rank)# 将排名赋给row的新属性 prev_value = current_value # 4. 将数据重新拼装回原始顺序（如果需要的话）并返回return data
扩展应用
  • 时间序列分析：计算移动平均、环比、同比。
  • Top-N 查询：获取每个类别中排名前N的记录。
  • 会话切割：在用户行为日志中，根据超时时间判断是否属于同一个会话。

第五章：索引与搜索算法（WHERE，B-Tree）

SQL语句：SELECT * FROM products WHERE price > 100 AND category_id = 5; （假设在category_id和price上有索引）

原理与实现
  1. B-Tree / B+Tree 索引：
    • 原理：一种自平衡的多路搜索树，能够保持数据有序。B+Tree是B-Tree的变种，所有数据都存储在叶子节点，且叶子节点之间通过指针相连，非常适合范围查询和磁盘读写。
    • 结构：
      • 节点包含多个键和指针。
      • 一个m阶的B+Tree，根节点至少有2个子节点，内部节点至少有ceil(m/2)个子节点。
      • 所有键在树中有序排列，左子树的键都小于当前键，右子树的键都大于等于当前键。
    • 查询过程（等值查询category_id=5）：从根节点开始，利用二分查找决定下一步应该走向哪个子节点，直到找到包含该键的叶子节点，然后在该叶子节点中二分查找找到具体的数据位置（或指针）。
    • 查询过程（范围查询price > 100）：先找到price=100的位置，然后利用叶子节点间的链表指针，向后顺序扫描即可，效率极高。
  2. 位图索引（Bitmap Index）：
    • 原理：适用于低基数（不同值少）的列，如性别、状态等。为每个不同的值创建一个位图（bit array），数组长度等于表的总行数。如果某行的值等于该值，则对应位为1，否则为0。
    • 高效之处：多个条件的查询可以通过位图的逻辑运算（AND, OR, NOT）快速完成。
      • WHERE category_id = 5 AND price > 100 等价于 bitmap(category_id=5) AND bitmap(price>100)。位图的与操作非常快。

代码文字实现（B+Tree查询简化伪代码）：

classBPlusTreeNode:def__init__(self, is_leaf=False): self.keys =[] self.children =[]# 对于非叶子节点，是子节点指针；对于叶子节点，是数据指针或数据本身 self.is_leaf = is_leaf self.next=None# 用于叶子节点之间的链表defbplus_tree_search(node, key):"""在B+Tree中查找一个键"""while node isnotNone:# 在当前节点的keys中找到第一个 >= key 的索引 idx = bisect.bisect_left(node.keys, key)if node.is_leaf:# 如果是叶子节点，检查找到的索引对应的key是否就是要找的keyif idx <len(node.keys)and node.keys[idx]== key:return node.children[idx]# 返回对应的数据else:returnNone# 未找到else:# 如果不是叶子节点，则递归搜索相应的子节点 node = node.children[idx]
扩展应用
  • B+Tree：不仅是数据库索引的标准，也是文件系统（如NTFS, Ext4）、Key-Value存储（如InnoDB的聚簇索引）的基石。
  • 位图索引：广泛应用于数据仓库、OLAP系统（如Apache Kylin）和科学计算中，用于快速筛选和聚合数据。
  • 跳表（Skip List）：Redis的Sorted Set使用跳表实现，它是一种概率性的平衡树替代结构，实现简单且高效。

总结

SQL是一门真正的“炼金术”，它将复杂的算法封装成简单易用的声明式语句。从排序归并到哈希聚合，从B+Tree索引到HyperLogLog概率估算，这些“超级算法”是数据库领域数十年智慧的结晶。

理解它们，意味着：

  1. 能写出更好的SQL：你知道WHERE条件如何利用索引，JOIN的选择会影响执行计划。
  2. 能进行高效的数据库调优：你知道为什么需要索引，为什么内存配置如此重要。
  3. 能将数据库思想应用于他处：当你需要处理大数据、设计系统、编写高性能代码时，这些算法和数据结构是你的强大武器库。

数据库的世界远不止于此，还有基于规则的优化器（RBO）与基于成本的优化器（CBO）、物化视图、WAL（Write-Ahead Logging）、MVCC（多版本并发控制）等更多精妙的设计等待探索。

在这里插入图片描述

Read more

Vivado完整license文件获取与配置指南

本文还有配套的精品资源，点击获取 简介：Vivado是由Xilinx开发的FPGA和SoC设计综合工具，支持Verilog、VHDL等硬件描述语言，提供高级综合、仿真、IP集成等功能。本资源包“Vivado_的license文件.zip”包含用于解锁Vivado完整功能的许可证文件。介绍了许可证服务器配置、.lic文件管理、浮动与固定许可证区别、激活流程、更新与诊断等核心内容。适用于FPGA开发者、嵌入式系统工程师及学习者，帮助其合法配置Vivado环境，提升开发效率和项目执行能力。 1. Vivado工具与FPGA开发环境概述 Xilinx Vivado设计套件是面向FPGA和SoC开发的集成化软件平台，广泛应用于通信、工业控制、人工智能、嵌入式视觉等多个高科技领域。其核心功能包括项目创建、综合、实现、仿真、调试及系统级集成，支持从设计输入到硬件验证的全流程开发。 Vivado不仅提供了图形化界面（GUI）便于初学者快速上手，还支持Tcl脚本自动化操作，满足高级用户的大规模工程管理需求。其模块化架构设计使得开发者可以灵活选择所需功能组件，如HLS（高层次综合）、IP In

By Ne0inhk
【讨论】VR + 具身智能 + 人形机器人：通往现实世界的智能接口

【讨论】VR + 具身智能 + 人形机器人：通往现实世界的智能接口

摘要：本文探讨了“VR + 具身智能 + 人形机器人”作为通往现实世界的智能接口的前沿趋势。文章从技术融合、应用场景、商业潜力三个维度分析其价值，涵盖工业协作、教育培训、医疗康复、服务陪护等领域，并展望VR赋能下的人机共生未来，揭示具身智能如何推动机器人真正理解、感知并参与现实世界。 VR + 具身智能 + 人形机器人：通往现实世界的智能接口 文章目录 * VR + 具身智能 + 人形机器人：通往现实世界的智能接口 * 一、引言：三股力量的融合，正在重塑现实世界 * 二、具身智能：让AI拥有“身体”的智慧 * 1. 什么是具身智能（Embodied Intelligence） * 2. 为什么VR是具身智能的“孵化器” * 三、VR + 具身智能 + 人形机器人：协同结构与原理 * 1. 系统组成 * 2. 人类的“

By Ne0inhk
Flutter 组件 bip340 适配鸿蒙 HarmonyOS 实战：次世代 Schnorr 签名，为鸿蒙 Web3 与隐私计算筑牢加密防线

Flutter 组件 bip340 适配鸿蒙 HarmonyOS 实战：次世代 Schnorr 签名，为鸿蒙 Web3 与隐私计算筑牢加密防线

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 组件 bip340 适配鸿蒙 HarmonyOS 实战：次世代 Schnorr 签名，为鸿蒙 Web3 与隐私计算筑牢加密防线 前言 在鸿蒙（OpenHarmony）生态迈向去中心化金融（DeFi）、隐私通讯及安全资产管理等高阶安全场景的背景下，如何实现更高性能、更具扩展性且抗攻击能力的数字签名架构，已成为决定应用闭环安全性的“压舱石”。在鸿蒙设备这类强调分布式鉴权与芯片级安全（TEE/SE）的移动终端上，如果依然沿用传统的 ECDSA 签名算法，由于由于其固有的可延展性风险与高昂的聚合验证成本，极易由于由于在大规模节点验证时的 CPU 负载过高导致交互滞后。 我们需要一种能够实现签名线性聚合、计算逻辑极简且具备原生抗延展性的密码学方案。 bip340 为 Flutter 开发者引入了比特币 Taproot 升级的核心——Schnorr 签名算法。它不仅在安全性上超越了传统标准，更通过其线性的数学特性，

By Ne0inhk
《MySQL 表基础语法：从入门到熟练的核心技巧》

《MySQL 表基础语法：从入门到熟练的核心技巧》

前引：MySQL 表的增删查是数据库操作的基础，也是日常开发、数据分析中最高频的需求。很多初学者会卡在语法细节、场景适配或效率优化上，明明掌握了基础命令，实际应用中却频频出错。本文聚焦 “实用 + 避坑”，从核心语法到高频场景，再到优化技巧，帮你彻底吃透 MySQL 表增删查，告别 “只会用不会用对” 的尴尬 SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having > select > distinct > order by > limit 目录 【一】增 （1）基本创建 （2）

By Ne0inhk