diff options
3 files changed, 54 insertions, 4 deletions
diff --git a/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php index 62ef2cb2e8e..922b0ccb17c 100644 --- a/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php +++ b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php @@ -10,7 +10,11 @@ use OCP\Files\Search\ISearchOperator; /** * Attempt to transform * - * (A AND B) OR (A AND C) into A AND (B OR C) + * (A AND B) OR (A AND C) OR (A AND D AND E) into A AND (B OR C OR (D AND E)) + * + * This is always valid because logical 'AND' and 'OR' are distributive[1]. + * + * [1]: https://en.wikipedia.org/wiki/Distributive_property */ class MergeDistributiveOperations extends ReplacingOptimizerStep { public function processOperator(ISearchOperator &$operator): bool { @@ -18,18 +22,29 @@ class MergeDistributiveOperations extends ReplacingOptimizerStep { $operator instanceof SearchBinaryOperator && $this->isAllSameBinaryOperation($operator->getArguments()) ) { + // either 'AND' or 'OR' $topLevelType = $operator->getType(); + // split the arguments into groups that share a first argument + // (we already know that all arguments are binary operators with at least 1 child) $groups = $this->groupBinaryOperatorsByChild($operator->getArguments(), 0); $outerOperations = array_map(function (array $operators) use ($topLevelType) { + // no common operations, no need to change anything if (count($operators) === 1) { return $operators[0]; } /** @var ISearchBinaryOperator $firstArgument */ $firstArgument = $operators[0]; - $outerType = $firstArgument->getType(); + + // we already checked that all arguments have the same type, so this type applies for all, either 'AND' or 'OR' + $innerType = $firstArgument->getType(); + + // the common operation we move out ('A' from the example) $extractedLeftHand = $firstArgument->getArguments()[0]; + // for each argument we remove the extracted operation to get the leftovers ('B', 'C' and '(D AND E)' in the example) + // note that we leave them inside the "inner" binary operation for when the "inner" operation contained more than two parts + // in the (common) case where the "inner" operation only has 1 item left it will be cleaned up in a follow up step $rightHandArguments = array_map(function (ISearchOperator $inner) { /** @var ISearchBinaryOperator $inner */ $arguments = $inner->getArguments(); @@ -39,12 +54,17 @@ class MergeDistributiveOperations extends ReplacingOptimizerStep { } return new SearchBinaryOperator($inner->getType(), $arguments); }, $operators); + + // combine the extracted operation ('A') with the remaining bit ('(B OR C OR (D AND E))') + // note that because of how distribution work, we use the "outer" type "inside" and the "inside" type "outside". $extractedRightHand = new SearchBinaryOperator($topLevelType, $rightHandArguments); return new SearchBinaryOperator( - $outerType, + $innerType, [$extractedLeftHand, $extractedRightHand] ); }, $groups); + + // combine all groups again $operator = new SearchBinaryOperator($topLevelType, $outerOperations); parent::processOperator($operator); return true; @@ -90,7 +110,6 @@ class MergeDistributiveOperations extends ReplacingOptimizerStep { foreach ($operators as $operator) { /** @var SearchBinaryOperator|SearchComparison $child */ $child = $operator->getArguments()[$index]; - ; $childKey = (string) $child; $result[$childKey][] = $operator; } diff --git a/lib/public/Files/Search/ISearchComparison.php b/lib/public/Files/Search/ISearchComparison.php index a3842ffaec6..eb93ef70bf6 100644 --- a/lib/public/Files/Search/ISearchComparison.php +++ b/lib/public/Files/Search/ISearchComparison.php @@ -70,6 +70,10 @@ interface ISearchComparison extends ISearchOperator { * @since 28.0.0 */ public const COMPARE_DEFINED = 'is-defined'; + + /** + * @since 29.0.0 + */ public const COMPARE_IN = 'in'; /** diff --git a/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php b/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php index 49a241a41af..4c7ecc9d46f 100644 --- a/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php +++ b/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php @@ -130,4 +130,31 @@ class MergeDistributiveOperationsTest extends TestCase { $this->assertEquals('((storage eq 1 and (path eq "foo" or path eq "bar" or path eq "asd")) and mimetype eq "text")', $operator->__toString()); } + + public function testMoveInnerOperations() { + $operator = new SearchBinaryOperator( + ISearchBinaryOperator::OPERATOR_OR, + [ + new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [ + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1), + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"), + ]), + new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [ + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1), + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"), + ]), + new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [ + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1), + new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"), + new SearchComparison(ISearchComparison::COMPARE_GREATER_THAN, "size", "100"), + ]) + ] + ); + $this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 1 and path eq "bar") or (storage eq 1 and path eq "asd" and size gt "100"))', $operator->__toString()); + + $this->optimizer->processOperator($operator); + $this->simplifier->processOperator($operator); + + $this->assertEquals('(storage eq 1 and (path eq "foo" or path eq "bar" or (path eq "asd" and size gt "100")))', $operator->__toString()); + } } |