如何在DolphinDB中实现路径生成与循环检测的递归查询？

需求背景 #

我正在使用DolphinDB处理层级树数据，需要解决两个核心问题：

• 生成所有节点（含无限层级叶子节点）的完整路径（拼接ID与名称）；
• 检测循环引用（如A→B→A）。

现有实现（MySQL递归CTE） #

已在MySQL中通过递归CTE成功实现该功能：

with recursive at as(
SELECT id, name,json_array(id) as path_id,json_array(name) as path_name,false as cycle
FROM table1
where pid is null and dir_group = 4
union ALL
SELECT t1.id, t1.name,JSON_MERGE_PRESERVE(at.path_id,json_array(t1.id)) as path_id ,
JSON_MERGE_PRESERVE(at.path_name,json_array(t1.name)) as path_name ,
json_contains(at.path_id,json_array(t1.id)) as cycle
FROM table1 t1 join at on t1.pid=at.id
where t1.pid is not null and not at.cycle)
select * from at

DolphinDB尝试方案及问题 #

在DolphinDB中尝试了循环与临时表的迭代方法，小数据集有效，但面对100万行的深层级数据存在性能问题：

// Sample table structure (adjust columns as needed)
nodes = table(1:0, `id`name`pid, [INT,STRING,INT])

// Initialize result table
result = table(1:0, `id`name`path`isCycle, [INT,STRING,STRING,BOOL])

// Initialize stack (using table)
stack = select id, name, string(id) as path from nodes where pid = NULL

while(size(stack) > 0) {
    // Pop last entry (stack behavior)
    current = select * from stack limit -1
    stack = select * from stack limit size(stack)-1

    // Detect cycles
    pathParts = split(current.path, ",")
    isCycle = sum(pathParts == string(current.id)) > 1

    // Store result
    result.append!(select id, name, path, isCycle from current)

    // Push children (reverse order for DFS)
    children = lj(nodes, current, `pid == `id)
    children = select * from children order by id desc  // Reverse for DFS
    stack.append!(select id, name, path + "," + string(id) from children)
}

同时探索了ploop、each、accumulate等内置函数，但它们不原生支持递归状态传递。

疑问 #

DolphinDB中有推荐的递归层级查询模式吗？或者有没有专门用于层级数据遍历的内置函数？

环境信息：

• DolphinDB版本：3.00.2
• 数据集规模：约100万行

1. 使用DolphinDB递归CTE（3.0版本原生支持） #

DolphinDB 3.0及以上版本支持递归CTE，语法与MySQL接近，性能远优于迭代方法，可直接实现层级遍历与循环检测。

实现代码 #

// 递归CTE实现路径生成与循环检测
with recursive at as (
    select 
        id, 
        name, 
        array(id) as path_id, 
        array(name) as path_name, 
        false as cycle
    from nodes 
    where pid is null and dir_group = 4  // 根节点条件，根据实际场景调整
    union all
    select 
        t1.id, 
        t1.name, 
        at.path_id append! t1.id, 
        at.path_name append! t1.name, 
        exists(at.path_id, x -> x == t1.id) as cycle
    from nodes t1 
    join at on t1.pid = at.id
    where not at.cycle  // 终止已检测到循环的分支遍历
)
select 
    id, 
    name, 
    str_join(path_id, ",") as path_id_str,  // 拼接ID路径为字符串
    str_join(path_name, " -> ") as path_name_str,  // 拼接名称路径为字符串
    cycle
from at

关键说明 #

• 用array类型存储路径，比字符串拼接更高效，最后通过str_join转换为所需格式；
• exists函数快速检测当前节点ID是否已在路径中，实现循环判断；
• 通过not at.cycle跳过循环分支，避免无效递归。

2. 优化迭代方法（针对特殊场景） #

若无法使用递归CTE，可通过以下优化提升迭代逻辑的性能：

优化点 #

• 使用内存表作为栈和结果表，大幅提升append!操作效率；
• 改用数组存储路径，避免每次循环重复split字符串；
• 预建pid到子节点的映射表，减少关联查询开销。

优化后代码 #

// 预建映射表：pid -> 子节点列表
childMap = groupby(nodes, pid, [id, name])

// 初始化内存栈表
stack = mt(id:INT, name:STRING, path_id:ARRAY(INT), path_name:ARRAY(STRING))
rootNodes = select id, name from nodes where pid is null and dir_group = 4
insert into stack values(rootNodes.id, rootNodes.name, array(rootNodes.id), array(rootNodes.name))

// 初始化内存结果表
result = mt(id:INT, name:STRING, path_id_str:STRING, path_name_str:STRING, isCycle:BOOL)

while(size(stack) > 0) {
    // 弹出栈顶元素
    current = select * from stack limit -1
    stack = delete from stack where rowNo() == size(stack)

    // 检测循环
    isCycle = exists(current.path_id[0], x -> x == current.id)

    // 存入结果
    insert into result values(
        current.id, 
        current.name, 
        str_join(current.path_id, ","), 
        str_join(current.path_name, " -> "), 
        isCycle
    )

    // 已检测到循环则跳过子节点遍历
    if(isCycle) continue

    // 压入子节点（逆序保持DFS顺序）
    if(current.id in keys(childMap)) {
        children = childMap[current.id]
        children = select * from children order by id desc
        insert into stack values(
            children.id, 
            children.name, 
            each(append!, current.path_id, children.id), 
            each(append!, current.path_name, children.name)
        )
    }
}

3. 内置函数辅助：treeTraverse（3.0+） #

DolphinDB 3.0及以上版本提供treeTraverse函数，专门用于层级树遍历，支持DFS/BFS模式，可简化代码逻辑。

代码示例 #

// 自定义遍历函数：生成路径并检测循环
def traverseFunc(node, parentInfo) {
    path_id = parentInfo.path_id append! node.id
    path_name = parentInfo.path_name append! node.name
    isCycle = exists(path_id, x -> x == node.id)
    return dict(
        "id": node.id,
        "name": node.name,
        "path_id_str": str_join(path_id, ","),
        "path_name_str": str_join(path_name, " -> "),
        "isCycle": isCycle,
        "path_id": path_id,
        "path_name": path_name
    )
}

// 初始化根节点的路径信息
rootInfo = dict("path_id": array(INT), "path_name": array(STRING))

// 执行树遍历（DFS模式）
result = treeTraverse(
    nodes, 
    `id`pid,  // 指定节点ID列、父ID列
    traverseFunc, 
    rootInfo, 
    isRoot = (node) -> node.pid is null and node.dir_group == 4,  // 根节点判断条件
    mode = "DFS"  // 可选"BFS"模式
)

// 转换为表格式
resultTable = table(result.values() as id, name, path_id_str, path_name_str, isCycle, path_id, path_name)

关键说明 #

• treeTraverse自动处理层级遍历，无需手动维护栈/队列；
• 自定义traverseFunc实现路径生成与循环检测的核心逻辑；
• 支持DFS和BFS两种遍历模式，适配不同业务场景。

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