YQL-16823 Add optimization of single epsilon transitions in match_recognize NFA

2 files changed, 35 insertions, 0 deletions

diff --git a/ydb/library/yql/minikql/comp_nodes/mkql_match_recognize_nfa.h b/ydb/library/yql/minikql/comp_nodes/mkql_match_recognize_nfa.h
index a5918f17b4..540b9d005e 100644
--- a/ydb/library/yql/minikql/comp_nodes/mkql_match_recognize_nfa.h
+++ b/ydb/library/yql/minikql/comp_nodes/mkql_match_recognize_nfa.h
@@ -75,6 +75,7 @@ public:
 
     void DoOptimizations() {
         EliminateEpsilonChains();
+        EliminateSingleEpsilons();
         CollectGarbage();
     }
 private:
@@ -98,6 +99,21 @@ private:
             }
         }
     }
+    void EliminateSingleEpsilons() {
+        for (size_t node = 0; node != Graph->Transitions.size(); node++) {
+            if (std::holds_alternative<TEpsilonTransitions>(Graph->Transitions[node])) {
+                continue;
+            }
+            Graph->Transitions[node] = std::visit(TNfaTransitionDestinationVisitor([&](size_t toNode) -> size_t {
+                if (auto *tr = std::get_if<TEpsilonTransitions>(&Graph->Transitions[toNode])) {
+                    if (tr->size() == 1) {
+                        return (*tr)[0];
+                    }
+                }
+                return toNode;
+            }), Graph->Transitions[node]);
+        }
+    }
     void CollectGarbage() {
         auto oldInput = Graph->Input;
         auto oldOutput = Graph->Output;
diff --git a/ydb/library/yql/minikql/comp_nodes/ut/mkql_match_recognize_nfa_ut.cpp b/ydb/library/yql/minikql/comp_nodes/ut/mkql_match_recognize_nfa_ut.cpp
index 897a973f64..7d116d6563 100644
--- a/ydb/library/yql/minikql/comp_nodes/ut/mkql_match_recognize_nfa_ut.cpp
+++ b/ydb/library/yql/minikql/comp_nodes/ut/mkql_match_recognize_nfa_ut.cpp
@@ -169,6 +169,25 @@ Y_UNIT_TEST_SUITE(MatchRecognizeNfa) {
             UNIT_ASSERT_GT(nonEpsIns[node] + nonEpsOuts[node], 0);
         }
     }
+    Y_UNIT_TEST(SingleEpsilonsEliminated) {
+        TScopedAlloc alloc(__LOCATION__);
+        const TRowPattern pattern{{
+            TRowPatternFactor{"A", 1, 1, false, false},
+            TRowPatternFactor{"B", 1, 1, false, false},
+        }};
+        const auto graph = TNfaTransitionGraphBuilder::Create(pattern, TNfaSetup::BuildVarLookup(pattern));
+        for (size_t node = 0; node != graph->Transitions.size(); node++) {
+            if (std::holds_alternative<TEpsilonTransitions>(graph->Transitions[node])) {
+                continue;
+            }
+            std::visit(TNfaTransitionDestinationVisitor([&](size_t toNode) -> size_t {
+                if (auto *tr = std::get_if<TEpsilonTransitions>(&graph->Transitions[toNode])) {
+                    UNIT_ASSERT_UNEQUAL(tr->size(), 1);
+                }
+                return toNode;
+            }), graph->Transitions[node]);
+        }
+    }
 
 
     //Tests for NFA-based engine for MATCH_RECOGNIZE