DBMS 如何实现自己的排序算法？或者他们呢？
How does a DBMS implement their own sorting algorithm? Or do they?
当 YACC 或 BISON 等解析器将 SQL 翻译成 C 时，那段翻译的 C 代码是否包含排序算法数学？我不明白排序是如何在 DBMS（例如 MySQL 或 Microsoft SQL 服务器）中实现的 - 算法是语法分析器的一部分吗？或者，该算法是否仅在从 SQL 查询中获取数据后才应用于结果数据组，而不是直接应用于计算机内存？还是排序算法是ISO标准，要求所有的DBMS都使用相同的算法？
我进行了研究和谷歌搜索，但没有找到明确的答案。没有不必要地阅读数据库内部的书，有人可以清楚地解释这个概念吗？
SQL 标准不包含任何关于如何进行排序的规范。当您使用 order by 发出查询时，数据库有责任按指定的顺序 return 结果，但是每个数据库都可以自由地实现它认为合适的结果。
排序算法肯定不是语法分析器的一部分，它在技术上是 'implementation detail'。不过，这是一个相当重要的问题，因为它可以从根本上影响复杂查询的性能。然而，术语 'implementation detail' 表示由 DBMS 供应商决定做什么以及如何做。
它甚至可以部分委托给查询优化器，因为像堆排序、合并排序、快速排序等常见的排序算法都有不同的 'best case scenarios'。有些在 'mostly sorted data' 上表现明显更好，而另一些在 'extremely unsorted data' 上表现极慢。由于索引可能包含非常智能的 DBMS 甚至可以根据手头的数据选择不同的排序算法的提示，see this Wikipedia writeup for a comparison。据我所知 none 目前的供应商这样做。
所以说到底，什么时候使用什么排序算法，只是程序员视角的一个黑盒子。您（应该）关心的只是输出排序 正确 .
就像很多事情一样，这取决于。
ISO 标准定义的是，当请求排序顺序时，它会以特定方式得到满足。满足该标准的机制取决于实施。话虽如此，近半个世纪以来，排序一直是计算的一个重要研究分支，并且已知有少量算法运行良好，再加上相当于微调的微小变化。
LEXX、YACC 和 BISON 除了提取他提供的代码的意图之外没有做太多事情。您可以在提供的代码中识别名词、谓词和动词，但在将输出传递给某种解释器之前，输出实际上不会执行任何操作。
在 RDBMS 中，隐藏在解析器和词法分析器下的解释器获取这些名词、谓词和动词，并计算理想化的数据访问路径，同时考虑平台的优化（专有或非专有）。访问路径作为动词列表执行。
但是，解释器不必是 RBMS。它可能是用于管理元数据的工具，在这种情况下，结果可能是实体关系的图形图像（作为示例）。
大多数数据库使用几种不同的排序算法，具体取决于它们要排序的内容，以及它们在信息生命周期的哪个阶段应用排序。
从批量数据创建有序索引时，他们可能会使用树排序或堆排序。
选择数据时，首选是选择允许遍历索引的访问路径，该索引自然地returns数据按您请求的顺序（即避免排序）。
如果必须在检索后对数据集进行排序，并且它足够小以适合内存，他们通常会使用某种风格的 QuickSort。
如果数据集在检索后必须排序，而且它太大而无法放入内存，他们可能会创建一个临时的 table 并使用堆排序或树排序。
希望对您有所帮助。
当 YACC 或 BISON 等解析器将 SQL 翻译成 C 时，那段翻译的 C 代码是否包含排序算法数学？我不明白排序是如何在 DBMS（例如 MySQL 或 Microsoft SQL 服务器）中实现的 - 算法是语法分析器的一部分吗？或者，该算法是否仅在从 SQL 查询中获取数据后才应用于结果数据组，而不是直接应用于计算机内存？还是排序算法是ISO标准，要求所有的DBMS都使用相同的算法？
我进行了研究和谷歌搜索，但没有找到明确的答案。没有不必要地阅读数据库内部的书，有人可以清楚地解释这个概念吗？
SQL 标准不包含任何关于如何进行排序的规范。当您使用 order by 发出查询时，数据库有责任按指定的顺序 return 结果，但是每个数据库都可以自由地实现它认为合适的结果。
排序算法肯定不是语法分析器的一部分，它在技术上是 'implementation detail'。不过，这是一个相当重要的问题，因为它可以从根本上影响复杂查询的性能。然而，术语 'implementation detail' 表示由 DBMS 供应商决定做什么以及如何做。
它甚至可以部分委托给查询优化器，因为像堆排序、合并排序、快速排序等常见的排序算法都有不同的 'best case scenarios'。有些在 'mostly sorted data' 上表现明显更好，而另一些在 'extremely unsorted data' 上表现极慢。由于索引可能包含非常智能的 DBMS 甚至可以根据手头的数据选择不同的排序算法的提示，see this Wikipedia writeup for a comparison。据我所知 none 目前的供应商这样做。
所以说到底，什么时候使用什么排序算法，只是程序员视角的一个黑盒子。您（应该）关心的只是输出排序 正确 .
就像很多事情一样，这取决于。
ISO 标准定义的是，当请求排序顺序时，它会以特定方式得到满足。满足该标准的机制取决于实施。话虽如此，近半个世纪以来，排序一直是计算的一个重要研究分支，并且已知有少量算法运行良好，再加上相当于微调的微小变化。
LEXX、YACC 和 BISON 除了提取他提供的代码的意图之外没有做太多事情。您可以在提供的代码中识别名词、谓词和动词，但在将输出传递给某种解释器之前，输出实际上不会执行任何操作。
在 RDBMS 中，隐藏在解析器和词法分析器下的解释器获取这些名词、谓词和动词，并计算理想化的数据访问路径，同时考虑平台的优化（专有或非专有）。访问路径作为动词列表执行。
但是，解释器不必是 RBMS。它可能是用于管理元数据的工具，在这种情况下，结果可能是实体关系的图形图像（作为示例）。
大多数数据库使用几种不同的排序算法，具体取决于它们要排序的内容，以及它们在信息生命周期的哪个阶段应用排序。
从批量数据创建有序索引时，他们可能会使用树排序或堆排序。
选择数据时，首选是选择允许遍历索引的访问路径，该索引自然地returns数据按您请求的顺序（即避免排序）。
如果必须在检索后对数据集进行排序，并且它足够小以适合内存，他们通常会使用某种风格的 QuickSort。
如果数据集在检索后必须排序，而且它太大而无法放入内存，他们可能会创建一个临时的 table 并使用堆排序或树排序。
希望对您有所帮助。