【程序设计】11.4 [大数据] 大游标

11.1 大游标

我们还不会做大数据的排序。

排序运算很不一样,它的计算结果和源数据一样大,如果源数据在内存中装不下,结果必然也装不下,但它又不像 select、new 这些,可以一边遍历一边计算。

大数据的排序,必须利用外存来做缓冲才能解决,大体步骤是这样:读入一部分数据,在内存中排序,把结果写出去;然后再去下一部分,排序,再写出;…;最后会得到一批排过序的中间结果,然后再使用归并算法把这些中间结果串起来。这个过程比较复杂,超出了本书的设计范围,这里就不再讲详细原理了。

SPL 提供了 sortx 函数用来执行大数据排序,这个函数把上述一系列过程都实现了。因为排序结果仍然是个大数据,所以 sortx 也会返回一个游标,但是它却不是延迟游标。sortx 将会立即计算,返回的游标是基于上述那些中间结果的。

比如我们要把订单数据按平均单价从大到小排列,然后写到另一个文件中:


A

1

=file("data.txt").cursor@t()

2

=A1.sortx(-amount/quantity)

3

=file("data.csv").export@ct(A2)

因为是从大到小排序,所以 sortx 用了负数作为参数。计算完之后的 A2 是个游标,它不能直接查看,可以用 fetch 取出数据,也可以像 A3 这样写入另一个文件。

sortx 是立即计算的,它执行完返回时,游标 A1 已经被遍历完了,这时候即使把 data.txt 删掉,也不会影响 A3 的动作。这和 select 那些函数是完全不同的,select 这些函数返回的延迟游标,将来会和其基础游标同步遍历。

要提醒一下,sortx 可能速度比较慢,运行后需要稍等一些时间。它还会占用一些硬盘空间(用于存储中间结果),集算器缺省会使用操作系统临时目录,也可以在选项中自行设置临时目录。

imagepng

其实,针对大数据的排序本身并不常用,我们通常不会关心很多数据的全排序结果,而只会关心前 N 名。但是,排序却常常是其它大数据运算的基础,没有一个有序的结果,其它运算就很难做。

比如大分组。

我们之前用的 groups,返回结果都是一个序表,也就是小数据。但是,还存在某种分组汇总运算,它的返回结果也会很巨大,以至于内存装不下了。这种时候就没办法用 groups 来做就会导致机器的内存溢出。

但是,像我们前面说过的,如果数据针对分组键值有序,那就可以用 group 函数的办法,在遍历过程中同时汇总,就不会发生溢出现象了,无论返回的分组结果有多大都可以正常计算出来。

比如我们想针对订单和金额和数量这两个字段分组,看看每组不同的金额和数量情况下有多少个订单。这个分组结果可能会有 100 万行(其实也不算大,但姑且认为大,假定用 groups 做不了)。

现在的数据对这两个字段组合并没有序,排了序之后就可以用 group 函数了。


A

1

=file("data.txt").cursor@t()

2

=A1.sortx(amount,quantity)

3

=A2.group(amount,quantity)

4

=A3.new(amount,quantity,~.count(1):C)

5

=A3.fetch(100)

这样就可以计算出大分组了,不过因为结果是大的,也只能 fetch 出一部分来查看,或者再写入另一个文件。

还可以基于它再计算,比如我们想针对同样金额和数量的订单数超过 5 的分组(也就是 A3 中那个汇总字段 C>5)再统计出总金额和数量来。


A

1

=file("data.txt").cursor@t()

2

=A1.sortx(amount,quantity)

3

=A2.group(amount,quantity)

4

=A3.new(amount,quantity,~.count(1):C)

5

=A4.select(C>5).total(sum(C*amount),sum(C*quantity))

group 函数返回的是延迟游标,可以再附加 select 运算,最后再用 total 去遍历它。

因为大分组还比较常用,所以 SPL 提供了一个 groupx 函数,同时把排序和分组一起做了。上面的代码可以简化写成:


A

1

=file("data.txt").cursor@t()

2

=A1.groupx(amount,quantity;count(1):C)

3

=A2.select(C>5).total(sum(C*amount),sum(C*quantity))

groupx 的参数规则和 groups 一样,但它会假定返回结果集很大,从而会先做排序(实际上会更复杂)再做有序分组,最后返回的也是个游标。和 sortx 类似,这也不是延迟游标。两个动作一起执行,不仅写法更简单,执行速度也更好,不过和 sortx 一样,也会临时占用硬盘空间。

除了大分组,还有大归并计算。

类似前面讲归并计算时的例子,如果我们手头有两个这样的订单大文件,需要做合并(或者求交集),也要求数据必须事先有序才可以做到。


A

B

1

=T@c("data1.txt")

=T@c("data2.txt")

2

=[A1,B1].mergex@u(id)

>T@c("all.csv",A2)

我们假定数据是按 id 有序的,就可以直接使用 mergex 来计算并集,这里的参数和 merge 解释相同,但一般我们不会在游标上建立主键,所以要把归并运算用到的关联键写上。

因为结果集可能很大,mergex 也是返回一个游标,但它是一个延迟游标,不会主动遍历。与 select 这些函数不同,mergex 可能针对多个基础游标生成延迟游标,把它遍历完之后也会把这多个基础游标都遍历完。而前面讲过的 select 等函数只会有一个基础游标。

T 函数用 @c 选项表示生成一个游标,它会根据文件的扩展名自动选择打开方式。也可以用于写出,@c 表示写出游标,同样会根据文件扩展名选择写出的方式。

和内存的 merge 函数不同,mergex 要求游标数据必须有序才能工作,没有 @o 选项。

排序之后,就能把本来要随机访问才能实现的运算变成只要顺序访问就可以了。类似的情况还有连接运算,用关联键值去找关联记录,本来是需要随机访问的(在数据表中寻找),但如果数据都对关联键有序,那么只要顺序访问也就能实现了。

SPL 同样提供了一个带 x 的 joinx 函数用来解决大连接。


A

B

1

=T@c("data1.txt")

=T@c("data2.txt")

2

=joinx(A1:a,id;B1:b,id)

=A2.fetch(100)

joinx 可以支持同维关联和主子关联的情况,它返回的也是延迟游标,从中 fetch 出来的序表和内存中 join 的形式类似,每个字段的取值分别是关联的每个游标中的记录,然后也可以继续用 new 函数来实现进一步的引用计算。

同样地,joinx 也支持用 @1 和 @f 实现左连接和全连接。我们这里就不再举详细例子,有兴趣的读者可以自己生成两个不同结构的数据表来尝试做一下大连接运算,要确保关联键有序,不然要先用 sortx 排序。

细心的读者可能会发现,还有一种情况我们没有讲到。就是外键关联时如果维表也很巨大而不能装入内存的情况,前面举例讲游标上外键相关的 switch 和 join 时,事实表数据来自游标,但维表仍然是个内存的序表。

这种情况,目前只能把外键也理解为连接运算再用 joinx 来实现,如果数据事先对事实表外键和维表主键无序,则需要先排序。而且每次 joinx 只能解析一个外键关联,有多个外键还要做多次 joinx,而针对内存维表的 switch 和 join 可以在一次遍历过程中解析多个外键。

和 select,groupx 等函数只针对一个游标的情况不同,mergex 和 joinx 都会针对多个游标工作。那么,是不是存在可能大数据和小数据一起做归并和连接的情况呢?

确实是存在的,大数据和小数据的归并、连接运算也是大数据的,要使用大数据的办法。这时候要把内存小数据,也就是序表,转换成游标,然后使用游标的方法来运算。SPL 提供了 cursor() 函数把序表、排列转换成游标,这样就可以把内存小数据模拟成大数据和文件游标一起运算了。这里也不再举例了,需要用到时再去查阅相关帮助材料就可以了。

我们现在学会了使用游标实现大数据运算,但仅仅是会做、能做对。大数据运算还有个重要目标是要做得快,这也是非常复杂的任务,甚至可以说是更复杂的任务,象前面提到的遍历复用技术一样,这些内容远远超出了本书的设计范围。在这里只给读者留一个印象即可,如何提高大数据运算性能的内容,足够再写一本同样厚度的书,许多计算方法都要重新设计,特别是要想办法避免实质性的排序,因为排序是非常慢的动作。

用于结构化数据处理的常规程序语言中,SQL 是可以应对大数据的。SQL 甚至做到了大小数据透明,就是使用者不需要关心数据的大小,这显然让人省了很多事,这是 SQL 的一个巨大优势。不过使用 SQL 通常要把数据装入数据库,这一步又太复杂了,超出了大部分非专业程序员的能力。

集算器提供了针对文件使用基本 SQL 的功能,能够支持大部分大数据运算,这样可以避免把数据装入数据库的麻烦。

Python 也经常会用来做结构化数据计算,但它没有游标对象,处理大数据时非常麻烦,相当于要自己实现游标的动作,对于非专业人员来讲基本上是个不可能完成的任务。

【程序设计】 前言及目录
【程序设计】11.3 [大数据] 有序游标
【程序设计】12.1 [图画师] 画布与图元