KDB+/Q中高效遍历表查找可交叉订单的优化方案问询

需求说明 #

现有两张存储订单信息的表t1和t2，需高效判断t1中每个订单是否与t2中订单存在交叉潜力：

• 判断条件：订单方向相反、时间范围（AckTime到EndTime）存在重叠
• 输出要求：满足条件时给出交叉规模，否则输出0；同时关联对应反向订单的信息

预期结果：RIC a可交叉90股，RIC b可交叉全部1000股，RIC c无法交叉。

示例表 #

t1:([]date: 2025.04.08 2025.04.08 2025.04.08 ;RIC:`a`b`c;Side:`buy`sell`buy;StartQty:100 1000 400; LimitPx: 100.00 20.00 15.00 ;AckTime:09:31 09:40 09:40; EndTime:09:33 09:45 09:41);

t2:([]date: 2025.04.08 2025.04.08 2025.04.08 ;RIC:`a`b`c;Side:`sell`buy`buy;StartQty:90 1000 400; LimitPx: 100.00 20.00 15.00 ;AckTime:09:30 09:40 09:41; EndTime:09:32 09:45 09:42);

当前实现及问题 #

当前通过遍历t1每条记录并查询t2的方式实现，代码如下：

func:{[row] 
    t:select from t2 where date=(row[`date][0]), RIC=(row[`RIC][0]), not Side=(row[`Side][0]), ((AckTime within ((row[`AckTime][0]);(row[`EndTime][0])))|(EndTime within ((row[`AckTime][0]);(row[`EndTime][0]))));
    crossedNotional:?[(count t)>0;(min((exec max StartQty from t);row[`StartQty][0]))*row[`LimitPx][0];0];
    contra:select from t where StartQty=max StartQty;
    res:select date, RIC, AckTime, EndTime, StartQty, crossedNotional:crossedNotional from row;
    res:lj[res;`date xkey select date, contraSide:Side,  contraAckTime:AckTime, contraEndTime:EndTime, contraStartQty:StartQty from contra];
    :res
    };
func2:{[table;x] func[enlist table[x]]};
test: ((,/) func2[t1;] peach (0+til (count t1)));

该方法在小数据量下可行，但扩展到大数据集时时间复杂度极高（O(n*m)），性能瓶颈明显。

优化方案及解答 #

1. 基于aj的高效实现 #

可以利用aj（as-of join）结合时间范围过滤实现批量关联，避免逐行遍历：

• 先预处理t2，按date、RIC、Side生成键表，用于快速匹配反向订单
• 为t1生成反向Side字段，关联t2中对应方向的订单
• 用aj基于AckTime对齐关联，再筛选时间范围重叠的记录
• 批量计算交叉规模，取符合条件的t2订单最大StartQty与t1订单StartQty的较小值，乘以LimitPx

示例代码：

// 预处理t2：按date、RIC、Side创建键表
t2Keyed: `date`RIC`Side xkey t2;

// 为t1生成反向Side，用于匹配t2的反向订单
t1WithContra: update contraSide:?[Side=`buy;`sell;`buy] from t1;

// 使用aj关联，按date、RIC、contraSide匹配，基于AckTime对齐
joined: aj[`date`RIC`contraSide`AckTime; t1WithContra; t2Keyed];

// 筛选时间范围重叠的记录：两个订单的时间区间有交集
filtered: select from joined where 
    (AckTime_t2 within (AckTime; EndTime)) or 
    (EndTime_t2 within (AckTime; EndTime)) or 
    (AckTime within (AckTime_t2; EndTime_t2));

// 按t1的唯一标识分组，取最大的反向订单StartQty
aggregated: select max StartQty_t2 as maxContraQty by date, RIC, AckTime, EndTime, StartQty, LimitPx from filtered;

// 计算交叉规模，关联回t1所有记录（无匹配则crossedNotional为0）
result: lj[`date`RIC`AckTime`EndTime xkey t1; 
           update crossedNotional:min(maxContraQty; StartQty)*LimitPx from aggregated];

// 补充反向订单的详细信息
result: lj[result; `date`RIC`Side`StartQty xkey select date, RIC, contraSide:Side, contraAckTime:AckTime, contraEndTime:EndTime, contraStartQty:StartQty from t2];

2. 内存表的分组优化 #

内存表不支持物理分区，但可以通过分组或键表优化查询效率：

• 使用xkey将t2按date、RIC、Side创建键表，关联时可快速定位匹配分组，避免全表扫描
• 对t2按date、RIC进行group，生成分组字典，查询时直接按键取出对应分组，减少扫描范围：

  t2Grouped: group[t2; `date`RIC];
  

3. 当前实现的低效点 #

• 逐行遍历：peach循环对t1每条记录单独查询t2，时间复杂度为O(n*m)，大数据集下性能急剧下降
• 重复全表扫描：每次循环都全表扫描t2，未利用索引或分组缩小查询范围
• 多次子表扫描：func中多次对临时表t进行扫描（取最大StartQty、筛选对应订单），增加不必要开销
• 低效关联：使用lj时未指定高效关联键，导致关联时全表匹配，效率低下

内容的提问来源于stack exchange，提问作者Cole