求助: xjoin 多条件叉乘如何优化
这个优化求助源于论坛中的这个帖子: 病人手术后 6 月内咨询标记
最近常碰到类似的多条件叉乘写法,比如先进先出核算成本等,写着写着就卡住不想写了,因为是叉乘,时间复杂度几乎是 O(n×n),想请大佬们指导一下。
论坛中的这个题用 SQL 很好描述,而且像 =、>=、<= 这种比较谓词在 SQL 里通常是比较友好的:

如果用集算器按照上述 SQL 思路实现,最接近的写法就是用 xjoin,因为 xjoin 里的参数也支持 >=、<= 这样的写法,如以下 A3 代码格中所示(splx 文件在附件中)
问题是这个叉乘虽然剪枝了,但复杂度仍然很高,稍大点数据量就会很慢。观察 A3 代码格中的 A2:s@b,这里用了二分法查找,但效果不是很明显,主要的计算量是在 A2:o 这里,但是这里的条件是一个复合条件,既有等于又有不等于,没办法用上二分法查找,很可惜,这么简洁的写法废了。
心有不甘,为了在叉乘中用上二分法,只能把等于这部分条件先 join,然后在每一组 Id 里用 xjoin 的二分法,如下所示(splx 文件在附件中):

先筛选出 Office 和 Surgery 各自的记录,用 Id 分组后进行 full join 如 A5 代码格中所示,然后 xjoin 里对>=、<= 可以用二分法了。这个写法效率是可以的,测试了 20 万个 Id,每个 Id 最多 10 条左右的记录,总共两百万条左右的数据,这个写法不算读取文件 (读取耗时 5 秒左右) 的时间耗时 2 秒左右。相较于 3 万多条记录直接叉乘耗时 1 分钟左右,这个写法两百万条记录总耗时 8 秒左右,算是提升很大了。
这个题的统计有点特殊,只要找到一条配对记录就行,所以像这种不等值条件查找想到了时间键,如下(splx 文件在附件中):

代码格 A3 和 A4 是做一些基础排序并设定主键和时间键,A5 格用了 fjoin,时间键的查找逻辑是本次 Office 咨询的最近一次 Surgery,也就是 Surgery 之后发生的咨询。这个写法效率也行,跟上面的 xjoin 二分法差不多,主要消耗还是在读取文件上的耗时。但是实际助益的似乎不是时间键,而是 su.find@b 这里的二分法查找,如果 find 不用二分,一样很慢。
以上写法就是最近半个月瞎琢磨的,之前还有一个先进先出计算成本的实现也是用了上述第二种写法,但总感觉不够酣畅淋漓,不爽。
1、直接 xjoin,复杂度高:
2、先等值 join,再用 xjoin 里的二分法,这样效率还可以:

而这种又有等于又有不等于的复合条件叉乘平时碰到的还挺多,那么要如何实现才会简洁高效,恳请大佬们得空时指导一下。
附件如下:

这个是否可以用时间键先关连,分组汇总的时候再来判断日期是否是 6 个月内。
时间键关连只需要给右侧维表用 keys@t 建立索引,join 的时候和正常关连没有区别
👍 多谢大佬指导。你写的比我折腾的那个时间键简洁不少,我写的感觉像血脂粘稠,你写的感觉非常轻快😂
想确认一下:时间键是不需要有序的对吧?或者说是否有序对时间键没影响?
另外,xjoin 只能这样了?这种既有 =、又有 >=、<=,需要返回多个结果的,spl 有最佳实践方法吗?
时间键不需要实现排序,xjoin 只能这样了,不能用时间键解决的只能用 xjoin 或者 fjoin 来做连接,或者像 sql 那样在 groups 中的聚合运算中写 select。
了然,了然…多谢大佬指导🙏