基于LIMIT语义的数据排序方法和数据排序装置

技术领域

本发明涉及数据库技术领域，具体而言，涉及一种基于LIMIT语义的数据排序方法和一种基于LIMIT语义的数据排序装置。

背景技术

在数据库管理系统中，查询语句经常需要对数据进行排序，而一个常见的查询方式是查询语句中带有LIMIT关键字的子句，即要从有序的数据中找出前N个元组中的row_num个元组。在数据量非常大的情况下，排序操作通常需要采用外部排序的技术对数据进行排序处理；然后利用归并算法，进行数据的合并；之后，在迭代器的上层，再统计返回的元组数目，实现LIMIT的语义。

但是，在现有技术的数据排序方案中，往往对大量的数据全部进行排序，这样会占用大量的内存，消耗了大量的计算机的系统资源。而且，在因内存有限从而使用外部排序的技术进行排序时，会产生大量的IO操作，降低了数据库管理系统的效率。另外，在迭代器上层而非排序操作中实现LIMIT语义，使得迭代器还需要对返回的元组进行计数操作，增加了计算的工作量，从而导致最耗时的排序过程没有得到优化。

因此，如何对查询语句中带有LIMIT子句的数据排序进行优化，以节约计算机系统资源并提高排序操作的速度和效率成为亟待解决的技术问题。

发明内容

本发明旨在至少解决现有技术或相关技术中存在的技术问题之一。

为此，本发明的一个目的在于提出了一种基于LIMIT语义的数据排序方法。

本发明的另一个目的在于提出了一种基于LIMIT语义的数据排序装置。

为实现上述至少一个目的，根据本发明的第一方面的实施例，提出了一种基于LIMIT语义的数据排序方法，包括：在将LIMIT语义下推到排序操作时，为目标数据分配第一排序缓存区和第二排序缓存区；将所述目标数据分多次读入到所述第一排序缓存区中，直到所述目标数据读取完为止，其中，每次将所述目标数据读入到所述第一排序缓存区中时，均执行以下步骤：对所述第一排序缓存区中的数据排序，判断是否首次对所述第一排序缓存区中的数据排序，若判定为首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的符合所述LIMIT语义限定的前N条元组存放到所述第二排序缓存区中，若判定为非首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的前N条元组与所述第二排序缓存区中的元组归并，将归并后的前N条元组存放到所述第二排序缓存区中；以及根据所述第二排序缓存区中的数据，确定符合所述LIMIT语义所限定的数据。

在上述技术方案中，优选地，所述将LIMIT语义下推到排序操作的步骤之前，所述数据排序方法还包括：确定所述LIMIT语义所限定的元组个数N；若N小于或等于预设阈值，则执行所述将LIMIT语义下推到排序操作的步骤。

在上述任一技术方案中，优选地，若不是最后一次将所述目标数据读入到所述第一排序缓存区中，则将所述目标数据读满到所述第一排序缓存区中。

在上述任一技术方案中，优选地，所述第二排序缓存区的空间大于或等于用于存储2N条元组数据的空间。

在上述任一技术方案中，优选地，所述第一排序缓存区的个数为一个或多个，在所述第一排序缓存区的个数为多个的情况下，将所述目标数据并行读入到多个所述第一排序缓存区中。

根据本发明的第二方面的实施例，提出了一种基于LIMIT语义的数据排序装置，包括：分配单元，用于在将LIMIT语义下推到排序操作时，为目标数据分配第一排序缓存区和第二排序缓存区；处理单元，用于将所述目标数据分多次读入到所述第一排序缓存区中，直到所述目标数据读取完为止，其中，每次将所述目标数据读入到所述第一排序缓存区中时，所述处理单元对所述第一排序缓存区中的数据排序，并判断是否为首次对所述第一排序缓存区中的数据排序，若判定为首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的符合所述LIMIT语义限定的前N条元组存放到所述第二排序缓存区中，若判定为非首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的前N条元组与所述第二排序缓存区中的元组归并，再将归并后的前N条元组存放到所述第二排序缓存区中；以及第一确定单元，用于根据所述第二排序缓存区中的数据，确定符合所述LIMIT语义所限定的数据。

在上述技术方案中，优选地，所述数据排序装置还包括：第二确定单元，用于确定所述LIMIT语义所限定的元组个数N；其中，当N小于或等于预设阈值时，所述分配单元将所述LIMIT语义下推到排序操作。

在上述任一技术方案中，优选地，所述处理单元具体用于，若不是最后一次将所述目标数据读入到所述第一排序缓存区中，则将所述目标数据读满到所述第一排序缓存区中。

在上述任一技术方案中，优选地，所述第二排序缓存区的空间大于或等于用于存储2N条元组数据的空间。

在上述任一技术方案中，优选地，所述第一排序缓存区的个数为一个或多个，在所述第一排序缓存区的个数为多个的情况下，所述处理单元将所述目标数据并行读入到多个所述第一排序缓存区中。

通过本发明的基于LIMIT语义的数据排序方法和数据排序装置，可以在数据库管理系统中对带有LIMIT子句的数据排序进行优化，从而提高排序操作的速度和效率。

附图说明

图1示出了根据本发明的一个实施例的基于LIMIT语义的数据排序方法的流程示意图；

图2示出了根据本发明的另一个实施例的基于LIMIT语义的数据排序方法的流程示意图；以及

图3示出了根据本发明的一个实施例的基于LIMIT语义的数据排序装置的结构示意图。

具体实施方式

为了可以更清楚地理解本发明的上述目的、特征和优点，下面结合附图和具体实施方式对本发明进行进一步的详细描述。需要说明的是，在不冲突的情况下，本申请的实施例及实施例中的特征可以相互组合。

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是，本发明还可以采用其他不同于在此描述的其他方式来实施，因此，本发明的保护范围并不受下面公开的具体实施例的限制。

图1示出了根据本发明的一个实施例的基于LIMIT语义的数据排序方法的流程示意图。

如图1所示，根据本发明的一个实施例的基于LIMIT语义的数据排序方法，包括：

步骤102，在将LIMIT语义下推到排序操作时，为目标数据分配第一排序缓存区和第二排序缓存区。

步骤104，将所述目标数据分多次读入到所述第一排序缓存区中，直到所述目标数据读取完为止，其中，每次将所述目标数据读入到所述第一排序缓存区中时，均执行以下步骤：对所述第一排序缓存区中的数据排序，判断是否为首次对所述第一排序缓存区中的数据排序，若判定为首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的符合所述LIMIT语义限定的前N条元组存放到所述第二排序缓存区中，若判定为非首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的前N条元组与所述第二排序缓存区中的元组归并，将归并后的前N条元组存放到所述第二排序缓存区中。

例如，在判定为非首次对第一排序缓存区中的数据排序时，第一排序缓存区中的前N个元组为：元组A、元组B和元组D(即N＝3)，第二排序缓存区中有元组B、元组C和元组E，那么将第一排序缓存区中的前N个元组和第二排序缓存区中的元组进行归并后为：元组A、元组B、元组B、元组C、元组D和元组E，取前3个元组(即元组A、元组B、元组B)存放在第二排序缓存区中。

再例如，在判定为非首次对第一排序缓存区中的数据排序时，第一排序缓存区中的前N个元组为：元组D、元组B和元组A(即N＝3)，第二排序缓存区中有元组E、元组B和元组C，那么将第一排序缓存区中的前N个元组和第二排序缓存区中的元组进行归并后为：元组E、元组D、元组C、元组B、元组B和元组A，取前3个元组(即元组E、元组D、元组C)存放在第二排序缓存区中。

步骤106，根据所述第二排序缓存区中的数据，确定符合所述LIMIT语义所限定的数据。

在该技术方案中，通过在内存中配置两种排序缓存区(第一排序缓存区和第二排序缓存区)，在对排序后的元组进行归并操作时，利用该两种排序缓存区可以减少参与归并操作的元组个数，从而节省了对元组的IO(In Out)操作和避免占用CPU(CentralProcessing Unit，中央处理器)过多的资源。而且本方案不需要执行基于外存的多路归并算法，也可以大大减少读文件和写文件的IO操作，简化了数据排序的步骤，从而有效地提高了数据排序的速度和效率。另外，在对目标数据都处理完之后，将第二排序缓存区中的元组发给迭代器进行下一步的处理即可，避免了相关技术中的迭代器对返回的元组个数进行统计，从而实现将外排序操作转化为内排序操作。

在上述技术方案中，优选地，所述将LIMIT语义下推到排序操作的步骤之前，所述数据排序方法还包括：确定所述LIMIT语义所限定的元组个数N；若N小于或等于预设阈值，则执行所述将LIMIT语义下推到排序操作的步骤。

在该技术方案中，由于LIMIT语义所限定的元组个数N过大，会影响数据排序的效果，因此，在N小于或等于预设阈值才执行以上的方案，从而保证了数据排序时的可靠性。在一个优选实施例中，预设阈值为100(此值为参数，可根据实际情况灵活设置)。

在一个实施例中，LIMIT子句的格式为“LIMIT{offset，row_num}”，其中，offset表示偏移量，row_num表示从偏移量起往后的元组个数，根据offset和row_num能够计算出LIMIT语义所限定的元组个数N＝offset+row_num。例如offset＝3，row_num＝7，则N＝10。在另一个实施例中，LIMIT子句的格式为“LIMIT{row_num}”，其中默认offset＝0，同样能够计算出LIMIT语义所限定的元组个数N＝offset+row_num，例如row_num＝5，则N＝5。

在上述任一技术方案中，优选地，若不是最后一次将所述目标数据读入到所述第一排序缓存区中，则将所述目标数据读满到所述第一排序缓存区中。

在该技术方案中，由于最后一次读取目标数据时，最后一次读取的目标数据未必能将第一排序缓存区读满，而当不是最后一次将目标数据读入到第一排序缓存区中时，读入目标数据至第一排序缓存区为满的状态，可以充分利用第一排序缓存区，从而提高了数据排序的效率。

在上述任一技术方案中，优选地，所述第二排序缓存区的空间大于或等于用于存储2N条元组数据的空间。

在该技术方案中，第二排序缓存区的空间大于或等于用于存储2N条元组的数据的空间，从而使得第二排序缓存区中有足够的空间来存放数据，从而有效地提高了数据排序的速度和效率。

在上述任一技术方案中，优选地，所述第一排序缓存区的个数为一个或多个，在所述第一排序缓存区的个数为多个的情况下，所述处理单元将所述目标数据并行读入到多个所述第一排序缓存区中。

在该技术方案中，通过将目标数据并行读入到多个第一排序缓存区中，进一步地提高了数据排序的速度和效率。

当然，除了可以将目标数据并行读入到多个第一排序缓存区中，还可以将目标数据串行读入到多个第一排序缓存区中。

另外，第一排序缓存区和第二排序缓存区的个数可以相同，也可以不相同。若第一排序缓存区和第二排序缓存区的个数相同，且第一排序缓存区和第二排序缓存区的个数为多个，则第一排序缓存区和第二排序缓存区一一对应，即将多个第一排序缓存区和多个第二排序缓存区分成了多个组，每一组均有一个第一排序缓存区和一个第二排序缓存区，每一组中的第一排序缓存区和第二排序缓存区中的数据均执行上述步骤104中的排序操作和归并操作，在对目标数据处理完毕之后，对所有的第二排序缓存区中的数据再执行多次归并操作，直到只保留一个第二排序缓存区的数据为止，将最后这次归并操作中的前N个元组作为符合LIMIT语义所限定的数据。

在该技术方案中，通过多个第一排序缓存区和多个第二排序缓存区同时处理目标数据，进一步地提高了数据排序的速度和效率。

在上述任一技术方案中，优选地，使用quicksort算法(快速排序算法)对所述第一排序缓存区中数据排序。

图2示出了根据本发明的另一个实施例的基于LIMIT语义的数据排序方法的流程示意图。

如图2所示，根据本发明的另一个实施例的基于LIMIT语义的数据排序方法，包括：

步骤202，优化器进行LIMIT语义下推。

步骤204，判断是否含ORDER BY子句，在判断结果为是时，进入步骤206，在判断结果为否时，进入步骤234，即使用现有技术中的方案对数据进行排序。

步骤206，判断是否含LIMIT子句，在判断结果为是时，进入步骤208，在判断结果为否时，进入步骤234，即使用现有技术中的方案对数据进行排序。

步骤208，判断LIMIT子句的格式是否为LIMIT{offset，row_num}或LIMIT{row_num}，在判断结果为是时，进入步骤210，在判断结果为否时，进入步骤234，即使用现有技术中的方案对数据进行排序。其中，offset表示偏移量，row_num表示从偏移量起往后的元组个数。

例如，若LIMIT子句的格式为LIMIT{3，4}，即offset＝3，row_num＝4。另外，若LIMIT子句的格式为LIMIT{row_num}，则默认偏移量offset＝0，例如LIMIT{4}，即offset＝0，row_num＝4。

步骤210，判断LIMIT语义所限定的元组个数N是否小于或等于Kmax(即预设阈值)，若N小于或等于Kmax，则进入步骤212，若N大于Kmax，则进入步骤234，即使用现有技术中的方案对数据进行排序。其中，如图1实施例的上文所述，根据offset和row_num能够计算出LIMIT语义所限定的元组个数N(N＝offset+row_num)，在此不再赘述。

步骤212，下推offset和row_num两个值到排序操作。

步骤214，迭代器进行排序操作优化。

步骤216，分配排序缓存区B1(即第一排序缓存区)。

步骤218，分配排序缓存区B2(即第二排序缓存区)。

步骤220，将目标数据读入到B1中，直到排序缓存区B1满或者最后一部分目标数据全部读入。

步骤222，每次将目标数据读入到排序缓存区B1中时，对排序缓存区B1中的数据进行排序。优选地，可对排序缓存区B1中的数据执行quicksort算法来进行排序。

步骤224，判断是否为首次执行对排序缓存区B1中的数据排序，在判定是首次执行时，进入步骤226，在判定不是首次执行时，进入步骤228。

步骤226，排序缓存区B1中的前N条元组放入排序缓存区B2。

步骤228，排序缓存区B1中的前N条元组直接与排序缓存区B2中的元组执行归并操作，归并后，保留前N条到排序缓存区B2，其他丢弃。

步骤230，判断全部目标数据是否完成，在判断结果为是时，进入步骤232，在判断结果为否时，进入步骤220。

步骤232，发送排序缓存区B2中的数据给迭代器。在以上实施例中，排序缓存区B1和排序缓存区B2的个数均为一个，因此，排序缓存区B2中的数据即为符合LIMIT语义所限定的数据，将排序缓存区B2中的数据发送给迭代器即可。

当然排序缓存区B1的个数还可以为多个，这样就能将目标数据并行读入到多个排序缓存区B1中。而且排序缓存区B1的个数为多个的情况下，排序缓存区B2的个数可以为一个或多个。若排序缓存区B2的个数为多个，则目标数据读取完之后，最终多个排序缓存区B2中均有数据(各保留N条元组)，最后将多个排序缓存区B2中的数据进行多次归并操作，并将最后一次归并操作中的前N条元组作为符合LIMIT语义所限定的数据。

步骤234，原有流程，即执行现有技术方案。

在以上技术方案中，分配有两种排序缓存区B1和B2，在对排序后的元组进行归并操作时，利用该两种排序缓存区可以减少参与归并操作的元组个数，从而节省了对元组的IO操作和避免占用CPU过多的资源。而且本方案不需要执行基于外存的多路归并算法，也可以大大减少了读文件和写文件的IO操作，简化了数据排序的步骤，从而有效地提高了数据排序的速度和效率。另外，在对目标数据都处理完之后，将第二排序缓存区中的元组发给迭代器进行下一步地处理即可，避免了相关技术中的迭代器对返回的元组个数进行统计，从而实现将外排序操作转化为内排序操作。

图3示出了根据本发明的一个实施例的基于LIMIT语义的数据排序装置的结构示意图。

如图3所示，根据本发明的一个实施例的基于LIMIT语义的数据排序装置300，包括：分配单元302、处理单元304和第一确定单元306。

分配单元302，用于在将LIMIT语义下推到排序操作时，为目标数据分配第一排序缓存区和第二排序缓存区；处理单元304，用于将所述目标数据分多次读入到所述第一排序缓存区中，直到所述目标数据读取完为止，其中，每次将所述目标数据读入到所述第一排序缓存区中时，所述处理单元304对所述第一排序缓存区中的数据排序，并判断是否为首次对所述第一排序缓存区中的数据排序，若判定为首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的符合所述LIMIT语义限定的前N条元组存放到所述第二排序缓存区中，若判定为非首次对所述第一排序缓存区中的数据排序，则将所述第一排序缓存区中的前N条元组与所述第二排序缓存区中的元组归并，再将归并后的前N条元组存放到所述第二排序缓存区中；以及第一确定单元306，用于根据所述第二排序缓存区中的数据，确定符合所述LIMIT语义所限定的数据。

在该技术方案中，通过在内存中配置两种排序缓存区，在对排序后的元组进行归并操作时，利用该两种排序缓存区可以减少参与归并操作的元组个数，从而节省了对元组的IO(In Out)操作和避免占用CPU(Central Processing Unit，中央处理器)过多的资源。而且本方案不需要执行基于外存的多路归并算法，也可以大大减少了读文件和写文件的IO操作，简化了数据排序的步骤，从而有效地提高了数据排序的速度和效率。另外，在对目标数据都处理完之后，将第二排序缓存区中的元组发给迭代器进行下一步地处理即可，避免了相关技术中的迭代器对返回的元组个数进行统计，从而实现将外排序操作转化为内排序操作。

在上述技术方案中，优选地，数据排序装置300还包括：第二确定单元308，用于确定所述LIMIT语义所限定的元组个数N；其中，当N小于或等于预设阈值时，分配单元302将所述LIMIT语义下推到排序操作。

如果LIMIT语义所限定的元组个数N过大，会影响数据排序的效果，因此，在该技术方案中，在N小于或等于预设阈值才执行以上的方案，从而保证了数据排序时的可靠性。在一个优选的实施例中，预设阈值为100。

在上述任一技术方案中，优选地，若不是最后一次将所述目标数据读入到所述第一排序缓存区中，处理单元304将所述目标数据读满到所述第一排序缓存区中。

在该技术方案中，由于最后一次读取目标数据时，最后一次读取的目标数据未必能将第一排序缓存区读满，而当不是最后一次将目标数据读入到第一排序缓存区中时，第一排序缓存区为满的状态，可以充分利用第一排序缓存区，从而提高了数据排序的效率。

在上述任一技术方案中，优选地，所述第二排序缓存区的空间大于或等于用于存储2N条元组数据的空间。

在该技术方案中，第二排序缓存区的空间大于或等于用于存储2N条元组的数据的空间，从而使得第二排序缓存区中有足够的空间来存放数据，从而有效地提高了数据排序的速度和效率。

在上述任一技术方案中，优选地，所述第一排序缓存区的个数为一个或多个，在所述第一排序缓存区的个数为多个的情况下，处理单元304将所述目标数据并行读入到多个所述第一排序缓存区中。

在该技术方案中，通过将目标数据并行读入到多个第一排序缓存区中，进一步地提高了数据排序的速度和效率。

当然，处理单元304可以将目标数据并行读入到多个第一排序缓存区中，还可以将目标数据串行读入到多个第一排序缓存区中。

另外，第一排序缓存区和第二排序缓存区的个数可以相同，也可以不相同。若第一排序缓存区和第二排序缓存区的个数相同，且第一排序缓存区和第二排序缓存区的个数为多个，则第一排序缓存区和第二排序缓存区一一对应，即将多个第一排序缓存区和多个第二排序缓存区分成了多个组，每一组均有一个第一排序缓存区和一个第二排序缓存区，处理单元304对每一组中的第一排序缓存区和第二排序缓存区中的数据均执行上述的排序操作和归并操作，在对目标数据处理完毕之后，处理单元304对所有的第二排序缓存区中的数据再执行多次归并操作，直到只保留一个第二排序缓存区的数据为止，并将最后这次归并操作中的前N个元组作为符合LIMIT语义所限定的数据。

以上结合附图详细说明了本发明的技术方案，通过本发明的基于LIMIT语义的数据排序方法和数据排序装置，可以在数据库管理系统中对带有LIMIT子句的数据排序进行优化，从而提高排序操作的速度和效率。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。