expand logic expression for index scan #465

bright-starry-sky · 2020-12-09T13:38:49Z

Analyze complex expression and expand the expression for index scan. for example :
(t1.c1 == 1 or t1.c2 == 2) and (t1.c3 == 3 or t1.c4 == 4)
Will be converted to:
(t1.c1==1 AND t1.c3==3) OR (t1.c1==1 AND t1.c4==4) OR (t1.c2==2 AND t1.c3==3) OR (t1.c2==2 AND t1.c4==4)

critical27 · 2020-12-10T03:52:14Z

Interesting, this really looks like math.... (A + B)(C + D) = AC + AD + BC + BD...

Shylock-Hg · 2020-12-10T03:58:19Z

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

bright-starry-sky · 2020-12-10T03:59:22Z

Interesting, this really looks like math.... (A + B)(C + D) = AC + AD + BC + BD...

yeah, you are right . used for index scan in storage layer. An OR logic corresponds to an IndexQueryContext.

bright-starry-sky · 2020-12-10T04:07:50Z

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

You mean how do make sure correct of sub expressions after expanded?

critical27 · 2020-12-10T04:11:27Z

src/util/ExpressionUtils.cpp

+            if (ops[0]->kind() == Expression::Kind::kLogicalOr ||
+                ops[1]->kind() == Expression::Kind::kLogicalOr) {
+                return expandExpr(target[0].get());


Would you give an example when do we hit this path? I suppose all expression of op has been expanded in expandImplAnd.

Would you give an example when do we hit this path? I suppose all expression of op has been expanded in expandImplAnd.

t1.c1 == 1 and t1.c2 == 2 and (t1.c4 == 4 or t1.c5 == 5)

nebula::graph::ExpressionUtils::expandExpr ExpressionUtils.cpp:135 nebula::graph::ExpressionUtils::expandImplAnd ExpressionUtils.cpp:156 nebula::graph::ExpressionUtils::expandExpr ExpressionUtils.cpp:121 nebula::graph::ExpressionUtilsTest_expandExpression_Test::TestBody ExpressionUtilsTest.cpp:507 void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) 0x0000000002f58ce3 void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) 0x0000000002f5340c testing::Test::Run() 0x0000000002f38e9c testing::TestInfo::Run() 0x0000000002f39718 testing::TestCase::Run() 0x0000000002f39d69 testing::internal::UnitTestImpl::RunAllTests() 0x0000000002f4089a bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) 0x0000000002f59dea bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) 0x0000000002f541f0 testing::UnitTest::Run() 0x0000000002f3f5a0 RUN_ALL_TESTS() 0x0000000002f65fdc main 0x0000000002f65f6a __libc_start_main 0x00007ffff7c86f43 _start 0x0000000001e0142e

Got it. Convert AB(C + D) to ABC + ABD)

Shylock-Hg · 2020-12-10T04:22:16Z

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

You mean how do make sure correct of sub expressions after expanded?

Yes In your example t1.c1 will expand from one to two (evaluate twice).

bright-starry-sky · 2020-12-10T06:10:35Z

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

You mean how do make sure correct of sub expressions after expanded?

Yes In your example t1.c1 will expand from one to two (evaluate twice).

I understand your question，don't need to evaluate it twice，for example :
(t1.c1 == 1 or t1.c1== 2) and t1.c2 == 3
expanded:
(t1.c1 == 1 and t1. c2 == 3) or (t1.c1 == 2 and t1.c2 == 3)

for index scan, will be executed twice, don't need to expression.eval()
prefix(12) union prefix(13)

Shylock-Hg · 2020-12-10T06:12:20Z

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

You mean how do make sure correct of sub expressions after expanded?

Yes In your example t1.c1 will expand from one to two (evaluate twice).

Well done. After expand some expression maybe evaluate multiple times, so how do you treat the expression with side affection (or which expression not pure).

You mean how do make sure correct of sub expressions after expanded?

Yes In your example t1.c1 will expand from one to two (evaluate twice).

I understand your question，don't need to evaluate it twice，for example :
(t1.c1 == 1 or t1.c1== 2) and t1.c2 == 3
expanded:
(t1.c1 == 1 and t1. c2 == 3) or (t1.c1 == 2 and t1.c2 == 3)

for index scan, will be executed twice, don't need to expression.eval()
prefix(12) union prefix(13)

Yes, if you check the t1.c1 is just a attribute expression.

yixinglu · 2020-12-10T06:57:19Z

Actually, I am really confused about the logical expression unfolding implementation. I think you can implement the logic recursively like following pseudo codes:

Expression *expandAnd(Expression *root) {
  if (root->kind() != Expression::Kind::kAnd) {
    return root->clone();
  }
  auto operands = root->operands();
  // (A OR B) AND C => (A AND C) OR (B AND C)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[0]->operands[0];
    auto orRightChild = operands[0]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[1]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[1]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }
  // A AND (B OR C) => (A AND B) OR (A AND C)
  if (operands[1]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[1]->operands[0];
    auto orRightChild = operands[1]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[0]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[0]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }

  return root->expr();
}

bright-starry-sky · 2020-12-10T07:02:53Z

Actually, I am really confused about the logical expression unfolding implementation. I think you can implement the logic recursively like following pseudo codes:

Expression *expandAnd(Expression *root) {
  if (root->kind() != Expression::Kind::kAnd) {
    return root->clone();
  }
  auto operands = root->operands();
  // (A OR B) AND C => (A AND C) OR (B AND C)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[0]->operands[0];
    auto orRightChild = operands[0]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[1]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[1]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }
  // A AND (B OR C) => (A AND B) OR (A AND C)
  if (operands[1]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[1]->operands[0];
    auto orRightChild = operands[1]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[0]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[0]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }

  return root->expr();
}

Interesting logic, How to deal with the following logic?
(A OR B OR C OR D) AND E

yixinglu · 2020-12-10T07:27:45Z

Actually, I am really confused about the logical expression unfolding implementation. I think you can implement the logic recursively like following pseudo codes:

Expression *expandAnd(Expression *root) {
  if (root->kind() != Expression::Kind::kAnd) {
    return root->clone();
  }
  auto operands = root->operands();
  // (A OR B) AND C => (A AND C) OR (B AND C)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[0]->operands[0];
    auto orRightChild = operands[0]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[1]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[1]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }
  // A AND (B OR C) => (A AND B) OR (A AND C)
  if (operands[1]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[1]->operands[0];
    auto orRightChild = operands[1]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[0]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[0]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }

  return root->expr();
}

Interesting logic, How to deal with the following logic?
(A OR B OR C OR D) AND E

Similar logic, only change the or Logical expression construction like this:

  // (A OR B OR C OR D) AND E => (A AND E) OR (B AND E) OR (C AND E) OR (D AND E)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto leftChildOperands = operands[0]->operands();
    auto newRoot = new LogicalExpression(Kind::kOr);
    for (auto& left : leftChildOperands) {
      auto operand = new LogicalExpression(Kind::kAnd, left, operands[1]);
      newRoot->addOperand(expandAnd(operand));
    }
    return newRoot;
  }

continue to talk about implementation

bright-starry-sky · 2020-12-10T07:44:50Z

Actually, I am really confused about the logical expression unfolding implementation. I think you can implement the logic recursively like following pseudo codes:

Expression *expandAnd(Expression *root) {
  if (root->kind() != Expression::Kind::kAnd) {
    return root->clone();
  }
  auto operands = root->operands();
  // (A OR B) AND C => (A AND C) OR (B AND C)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[0]->operands[0];
    auto orRightChild = operands[0]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[1]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[1]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }
  // A AND (B OR C) => (A AND B) OR (A AND C)
  if (operands[1]->kind() == Expression::Kind::kOr) {
    auto orLeftChild = operands[1]->operands[0];
    auto orRightChild = operands[1]->operands[1];
    auto left = new LogicalExpression(Kind::kAnd, orLeftChild, operands[0]);
    auto right = new LogicalExpression(Kind::kAnd, orRightChild, operands[0]);
    return new LogicalExpression(Kind::kOr, expandAnd(left), expandAnd(right));
  }

  return root->expr();
}

Interesting logic, How to deal with the following logic?
(A OR B OR C OR D) AND E

Similar logic, only change the or Logical expression construction like this:

  // (A OR B OR C OR D) AND E => (A AND E) OR (B AND E) OR (C AND E) OR (D AND E)
  if (operands[0]->kind() == Expression::Kind::kOr) {
    auto leftChildOperands = operands[0]->operands();
    auto newRoot = new LogicalExpression(Kind::kOr);
    for (auto& left : leftChildOperands) {
      auto operand = new LogicalExpression(Kind::kAnd, left, operands[1]);
      newRoot->addOperand(expandAnd(operand));
    }
    return newRoot;
  }

Actually, I don't quite understand the logic of this pseudo code， According to this pseudo code logic, the output should be：
((A OR B OR C) AND E ) OR (D AND E)
not is : (A AND E) OR (B AND E) OR (C AND E) OR (D AND E)

critical27 · 2020-12-10T09:28:21Z

I have no doubt for the implementation, LGTM.

I believe the problem comes from the expression may have more than two operands, this would make code not so elegant.
Maybe we can try function style later, for example std::reduce(expr->operands.begin(), expr->operands.end(), Cartesian Product) for and, and std::reduce(expr->operands.begin(), expr->operands.end(), MergeIntoOne) for or.

yixinglu · 2020-12-10T10:51:22Z

I rethink the expr traversal logic from top to bottom, there's some errors for the case a && (b || c) && d. we should access the expr tree node and find the pattern A && (B || C) or (A || B) && C in the expr tree recursively from bottom to top.

I have no problems about this PR. LGTM.

expand expression for index

69c7218

bright-starry-sky requested review from a team December 9, 2020 13:38

Merge branch 'master' into index_expression

0828b17

bright-starry-sky added the ready-for-testing PR: ready for the CI test label Dec 10, 2020

critical27 reviewed Dec 10, 2020

View reviewed changes

yixinglu previously approved these changes Dec 10, 2020

View reviewed changes

yixinglu self-requested a review December 10, 2020 06:57

yixinglu approved these changes Dec 10, 2020

View reviewed changes

critical27 approved these changes Dec 11, 2020

View reviewed changes

yixinglu added 2 commits December 11, 2020 19:57

Merge branch 'master' into index_expression

bf449e8

Merge branch 'master' into index_expression

7514f79

yixinglu merged commit 11da663 into vesoft-inc:master Dec 15, 2020

bright-starry-sky deleted the index_expression branch December 15, 2020 01:09

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

expand logic expression for index scan #465

expand logic expression for index scan #465

bright-starry-sky commented Dec 9, 2020

critical27 commented Dec 10, 2020 •

edited

Loading

Shylock-Hg commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

critical27 Dec 10, 2020

bright-starry-sky Dec 10, 2020

critical27 Dec 10, 2020

Shylock-Hg commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

Shylock-Hg commented Dec 10, 2020

yixinglu commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

yixinglu commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

critical27 commented Dec 10, 2020 •

edited

Loading

yixinglu commented Dec 10, 2020

expand logic expression for index scan #465

expand logic expression for index scan #465

Conversation

bright-starry-sky commented Dec 9, 2020

critical27 commented Dec 10, 2020 • edited Loading

Shylock-Hg commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

critical27 Dec 10, 2020

Choose a reason for hiding this comment

bright-starry-sky Dec 10, 2020

Choose a reason for hiding this comment

critical27 Dec 10, 2020

Choose a reason for hiding this comment

Shylock-Hg commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

Shylock-Hg commented Dec 10, 2020

yixinglu commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

yixinglu commented Dec 10, 2020

bright-starry-sky commented Dec 10, 2020

critical27 commented Dec 10, 2020 • edited Loading

yixinglu commented Dec 10, 2020

critical27 commented Dec 10, 2020 •

edited

Loading

critical27 commented Dec 10, 2020 •

edited

Loading