Forum Discussion

2020HB59567's avatar
2020HB59567
Frequent Visitor
2 years ago

Recursive function goes in never ending loop

Hello everybody I am working on a recursive function to build a hierarchy from Active Directory. Execution does not halt. I am not able to understand the mistake that I am committing. Please help  ...
Need Help
spinfuzer's avatar
spinfuzer
Solution Sage
2 years ago

Are you sure this hierarchy does not have any weird issues such as a circular relationship?

Could 1 report to 2, 2 report to 3, and 3 report to 1?  Build that as a condition to end your loop just in case.  If you find any person that is already on the list, end your loop.  You could also just stop it at n equal to a little over the max number of levels you think you should have and see if there may be some issues.

 

See example.

 

 

 

 

 

 

let
    Source = Binary.FromText("W3siRW1wbG95ZWUgSUQiOjEsIk1hbmFnZXIgSUQiOjJ9LHsiRW1wbG95ZWUgSUQiOjIsIk1hbmFnZXIgSUQiOjN9LHsiRW1wbG95ZWUgSUQiOjMsIk1hbmFnZXIgSUQiOjR9LHsiRW1wbG95ZWUgSUQiOjQsIk1hbmFnZXIgSUQiOjV9LHsiRW1wbG95ZWUgSUQiOjUsIk1hbmFnZXIgSUQiOjF9LHsiRW1wbG95ZWUgSUQiOjYsIk1hbmFnZXIgSUQiOjEwfSx7IkVtcGxveWVlIElEIjo3LCJNYW5hZ2VyIElEIjoxMH0seyJFbXBsb3llZSBJRCI6OCwiTWFuYWdlciBJRCI6MTB9LHsiRW1wbG95ZWUgSUQiOjksIk1hbmFnZXIgSUQiOjEwfSx7IkVtcGxveWVlIElEIjoxMCwiTWFuYWdlciBJRCI6bnVsbH1d"),
    #"Imported JSON" = Json.Document(Source,1252),
    #"Converted to Table" = Table.FromList(#"Imported JSON", Splitter.SplitByNothing(), null, null, ExtraValues.Error),
    Expand = Table.ExpandRecordColumn(#"Converted to Table", "Column1", {"Employee ID", "Manager ID"}, {"Employee ID", "Manager ID"}),
    priorStep = Table.AddColumn(Expand, "tree", each {[Employee ID]}),
    build_tree = (tbl as table) =>
        let
            update_tree = 
                Table.TransformColumns(
                    tbl, 
                    {
                        "tree", 
                        each _ & Table.SelectRows(tbl, (T) => T[Employee ID] = List.Last(_))[Manager ID]}),
            loop =
                if update_tree = tbl or List.Transform(update_tree[tree], each List.Distinct(_)) = tbl[tree] 
                then update_tree
                else @build_tree(update_tree)
        in
            loop,
    final = build_tree(priorStep),
    #"Extracted Values" = Table.TransformColumns(final, {"tree", each Text.Combine(List.Transform(_, Text.From), ","), type text})
    
in
    #"Extracted Values"

 

 

 

 

 

 

 

 

2020HB59567's avatar
2020HB59567
Frequent Visitor
2 years ago

Hello spinfuzer

I used your code(modified the source to AD as input). Your code works fine. Unfortunately the AD implementation in my org is convoluted and the response is unacceptable. I was able to part about 2000 records in 2 hours. Hence I will not be able to use your code.

Thank you for the code though. I learnt something new!

  • spinfuzer's avatar
    spinfuzer
    Solution Sage
    2 years ago

    Table.Join with the LeftHash algorithm seems to work a lot faster.

     

    Actually NestedJoin works faster, had to correct the query.

     

     

    (c_list as list, p_list as list) =>
let
    Source = 
    Table.AddIndexColumn(
        Table.TransformColumnTypes(
            Table.FromRows(
                List.Zip({c_list,p_list}), 
                {"c", "p"}
            ),
            {
                {"c", type text},
                {"p", type text}
            }
        )
        , "path_index_column"
    ),
    parent_table = Table.AddKey(Table.Buffer(Table.SelectRows(Source, each [p] <> null)), {"c"},true),
    add_path_col = Table.RemoveColumns(Table.AddColumn(Source,"path",each {[c]}), "p"),
    fnPath = 
        (tbl as table) => 
        let
            //join = Table.Join(tbl,"c",Table.PrefixColumns(parent_table,"n"),"n.c", JoinKind.LeftOuter, 3),
            //remove_c = Table.RemoveColumns(join, {"c","n.c", "n.path_index_column"}),
            //before_update_path = Table.RenameColumns(remove_c, {{"n.p", "c"}, {"path","old_path"}}),
            join = Table.NestedJoin(tbl,"c",parent_table,"c", "merged", JoinKind.LeftOuter),
            remove_c = Table.RemoveColumns(join, {"c"}),
            before_update_path = Table.RenameColumns(Table.ExpandTableColumn(remove_c, "merged", {"p"}, {"c"}),{"path","old_path"}),
            update_path = Table.Buffer(Table.AddColumn(before_update_path, "path", each if [c] <> null then [old_path] & {[c]} else [old_path])),
            //update_path = Table.ReplaceValue(before_update_path, each [path], each if [c] <> null then [path] & {[c]} else [path], Replacer.ReplaceValue, {"path"}),
            new_child = update_path[c],
            old_child = join[c],
            final = 
                if List.NonNullCount(new_child) < List.NonNullCount(old_child)
                    then @ fnPath(Table.RemoveColumns(update_path, "old_path"))
                else if List.NonNullCount(new_child) = 0
                    then                     
                        Table.SelectColumns(
                            Table.TransformColumns(
                                Table.AddColumn(
                                    Table.SelectColumns(update_path,{"path_index_column","path"}),
                                    "child",
                                    each [path]{0}
                                ), 
                                {"path", each Text.Combine(_, ",")}
                            ),
                            {"path_index_column","child","path"}
                        )
                else if 
                    List.Transform(
                        Table.SelectRows(update_path, each [c] <> null)[path], 
                        List.Distinct
                    ) 
                    <> 
                    List.Transform(
                        Table.SelectRows(update_path, each [c] <> null)[old_path],
                        List.Distinct
                    )
                // the condition above checks for circular relationships 
                    then @ fnPath(Table.RemoveColumns(update_path, "old_path"))
                else 
                    Table.SelectColumns(
                        Table.TransformColumns(
                            Table.AddColumn(
                                Table.SelectColumns(update_path,{"path_index_column","path"}),
                                "child",
                                each [path]{0}
                            ), 
                            {"path", each Text.Combine(_, ",")}
                        ),
                        {"path_index_column","child","path"}
                    )
                    
        in
            final,
    output = fnPath(add_path_col)
//        Table.FromRows(
 //           List.Zip({c_list,fnPath(add_path_col)}),
  //          {"child_column","path_column"}
  //      )
in
    output

     

     

     

     

     

     

     

    • lbendlin's avatar
      lbendlin
      Super User
      2 years ago

      cannot confirm.  Left Join performs worse than Nested Join

       

      I also tried Chris Webb's suggestion on the inner join with sort merge (mode 2) but that is underwhelming as well

       

       

      • spinfuzer's avatar
        spinfuzer
        Solution Sage
        2 years ago

        Testing with 123K+ rows with up to 5 levels on a customer account hierarchy.  I am joining up to 5 times maximum instead of doing selectrows 123x5 times.