diff options
Diffstat (limited to 'lib/private/Files/Search/QueryOptimizer')
9 files changed, 329 insertions, 63 deletions
diff --git a/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php new file mode 100644 index 00000000000..bb7bef2ed63 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php @@ -0,0 +1,33 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2023 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OC\Files\Search\SearchBinaryOperator; +use OCP\Files\Search\ISearchBinaryOperator; +use OCP\Files\Search\ISearchOperator; + +class FlattenNestedBool extends QueryOptimizerStep { + public function processOperator(ISearchOperator &$operator) { + if ( + $operator instanceof SearchBinaryOperator && ( + $operator->getType() === ISearchBinaryOperator::OPERATOR_OR + || $operator->getType() === ISearchBinaryOperator::OPERATOR_AND + ) + ) { + $newArguments = []; + foreach ($operator->getArguments() as $oldArgument) { + if ($oldArgument instanceof SearchBinaryOperator && $oldArgument->getType() === $operator->getType()) { + $newArguments = array_merge($newArguments, $oldArgument->getArguments()); + } else { + $newArguments[] = $oldArgument; + } + } + $operator->setArguments($newArguments); + } + parent::processOperator($operator); + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php b/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php new file mode 100644 index 00000000000..7e99c04f197 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php @@ -0,0 +1,31 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2023 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OCP\Files\Search\ISearchBinaryOperator; +use OCP\Files\Search\ISearchOperator; + +/** + * replace single argument AND and OR operations with their single argument + */ +class FlattenSingleArgumentBinaryOperation extends ReplacingOptimizerStep { + public function processOperator(ISearchOperator &$operator): bool { + parent::processOperator($operator); + if ( + $operator instanceof ISearchBinaryOperator + && count($operator->getArguments()) === 1 + && ( + $operator->getType() === ISearchBinaryOperator::OPERATOR_OR + || $operator->getType() === ISearchBinaryOperator::OPERATOR_AND + ) + ) { + $operator = $operator->getArguments()[0]; + return true; + } + return false; + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php new file mode 100644 index 00000000000..4949ca7396b --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php @@ -0,0 +1,99 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2023 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OC\Files\Search\SearchBinaryOperator; +use OC\Files\Search\SearchComparison; +use OCP\Files\Search\ISearchBinaryOperator; +use OCP\Files\Search\ISearchOperator; + +/** + * Attempt to transform + * + * (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 { + if ($operator instanceof SearchBinaryOperator) { + // either 'AND' or 'OR' + $topLevelType = $operator->getType(); + + // split the arguments into groups that share a first argument + $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]; + } + + // for groups with size >1 we know they are binary operators with at least 1 child + /** @var ISearchBinaryOperator $firstArgument */ + $firstArgument = $operators[0]; + + // 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(); + array_shift($arguments); + if (count($arguments) === 1) { + return $arguments[0]; + } + 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( + $innerType, + [$extractedLeftHand, $extractedRightHand] + ); + }, $groups); + + // combine all groups again + $operator = new SearchBinaryOperator($topLevelType, $outerOperations); + parent::processOperator($operator); + return true; + } + return parent::processOperator($operator); + } + + /** + * Group a list of binary search operators that have a common argument + * + * Non-binary operators, or empty binary operators will each get their own 1-sized group + * + * @param ISearchOperator[] $operators + * @return ISearchOperator[][] + */ + private function groupBinaryOperatorsByChild(array $operators, int $index = 0): array { + $result = []; + foreach ($operators as $operator) { + if ($operator instanceof ISearchBinaryOperator && count($operator->getArguments()) > 0) { + /** @var SearchBinaryOperator|SearchComparison $child */ + $child = $operator->getArguments()[$index]; + $childKey = (string)$child; + $result[$childKey][] = $operator; + } else { + $result[] = [$operator]; + } + } + return array_values($result); + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php b/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php new file mode 100644 index 00000000000..6df35c9c9a2 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php @@ -0,0 +1,74 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2023 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OC\Files\Search\SearchBinaryOperator; +use OC\Files\Search\SearchComparison; +use OCP\Files\Search\ISearchBinaryOperator; +use OCP\Files\Search\ISearchComparison; +use OCP\Files\Search\ISearchOperator; + +/** + * transform (field == A OR field == B ...) into field IN (A, B, ...) + */ +class OrEqualsToIn extends ReplacingOptimizerStep { + public function processOperator(ISearchOperator &$operator): bool { + if ( + $operator instanceof ISearchBinaryOperator + && $operator->getType() === ISearchBinaryOperator::OPERATOR_OR + ) { + $groups = $this->groupEqualsComparisonsByField($operator->getArguments()); + $newParts = array_map(function (array $group) { + if (count($group) > 1) { + // because of the logic from `groupEqualsComparisonsByField` we now that group is all comparisons on the same field + /** @var ISearchComparison[] $group */ + $field = $group[0]->getField(); + $values = array_map(function (ISearchComparison $comparison) { + /** @var string|integer|bool|\DateTime $value */ + $value = $comparison->getValue(); + return $value; + }, $group); + $in = new SearchComparison(ISearchComparison::COMPARE_IN, $field, $values, $group[0]->getExtra()); + $pathEqHash = array_reduce($group, function ($pathEqHash, ISearchComparison $comparison) { + return $comparison->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true) && $pathEqHash; + }, true); + $in->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, $pathEqHash); + return $in; + } else { + return $group[0]; + } + }, $groups); + if (count($newParts) === 1) { + $operator = $newParts[0]; + } else { + $operator = new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, $newParts); + } + parent::processOperator($operator); + return true; + } + parent::processOperator($operator); + return false; + } + + /** + * Non-equals operators are put in a separate group for each + * + * @param ISearchOperator[] $operators + * @return ISearchOperator[][] + */ + private function groupEqualsComparisonsByField(array $operators): array { + $result = []; + foreach ($operators as $operator) { + if ($operator instanceof ISearchComparison && $operator->getType() === ISearchComparison::COMPARE_EQUAL) { + $result[$operator->getField()][] = $operator; + } else { + $result[] = [$operator]; + } + } + return array_values($result); + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php b/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php index 664402f1238..2994a9365a7 100644 --- a/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php +++ b/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php @@ -2,28 +2,9 @@ declare(strict_types=1); /** - * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl> - * - * @author Maxence Lange <maxence@artificial-owl.com> - * @author Robin Appelman <robin@icewind.nl> - * - * @license GNU AGPL version 3 or any later version - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU Affero General Public License as - * published by the Free Software Foundation, either version 3 of the - * License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Affero General Public License for more details. - * - * You should have received a copy of the GNU Affero General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - * + * SPDX-FileCopyrightText: 2021 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later */ - namespace OC\Files\Search\QueryOptimizer; use OC\Files\Search\SearchComparison; @@ -71,9 +52,9 @@ class PathPrefixOptimizer extends QueryOptimizerStep { private function operatorPairIsPathPrefix(ISearchOperator $like, ISearchOperator $equal): bool { return ( - $like instanceof ISearchComparison && $equal instanceof ISearchComparison && - !$like->getExtra() && !$equal->getExtra() && $like->getField() === 'path' && $equal->getField() === 'path' && - $like->getType() === ISearchComparison::COMPARE_LIKE_CASE_SENSITIVE && $equal->getType() === ISearchComparison::COMPARE_EQUAL + $like instanceof ISearchComparison && $equal instanceof ISearchComparison + && !$like->getExtra() && !$equal->getExtra() && $like->getField() === 'path' && $equal->getField() === 'path' + && $like->getType() === ISearchComparison::COMPARE_LIKE_CASE_SENSITIVE && $equal->getType() === ISearchComparison::COMPARE_EQUAL && $like->getValue() === SearchComparison::escapeLikeParameter($equal->getValue()) . '/%' ); } diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php index 160b27b7f11..5259ca25ad3 100644 --- a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php +++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php @@ -2,23 +2,8 @@ declare(strict_types=1); /** - * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl> - * - * @license GNU AGPL version 3 or any later version - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU Affero General Public License as - * published by the Free Software Foundation, either version 3 of the - * License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Affero General Public License for more details. - * - * You should have received a copy of the GNU Affero General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - * + * SPDX-FileCopyrightText: 2021 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later */ namespace OC\Files\Search\QueryOptimizer; @@ -29,15 +14,20 @@ class QueryOptimizer { /** @var QueryOptimizerStep[] */ private $steps = []; - public function __construct( - PathPrefixOptimizer $pathPrefixOptimizer - ) { + public function __construct() { + // note that the order here is relevant $this->steps = [ - $pathPrefixOptimizer + new PathPrefixOptimizer(), + new MergeDistributiveOperations(), + new FlattenSingleArgumentBinaryOperation(), + new FlattenNestedBool(), + new OrEqualsToIn(), + new FlattenNestedBool(), + new SplitLargeIn(), ]; } - public function processOperator(ISearchOperator $operator) { + public function processOperator(ISearchOperator &$operator) { foreach ($this->steps as $step) { $step->inspectOperator($operator); } diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php index b16898e9087..15b5b580ec1 100644 --- a/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php +++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php @@ -2,23 +2,8 @@ declare(strict_types=1); /** - * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl> - * - * @license GNU AGPL version 3 or any later version - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU Affero General Public License as - * published by the Free Software Foundation, either version 3 of the - * License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Affero General Public License for more details. - * - * You should have received a copy of the GNU Affero General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - * + * SPDX-FileCopyrightText: 2021 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later */ namespace OC\Files\Search\QueryOptimizer; diff --git a/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php new file mode 100644 index 00000000000..a9c9ba876bc --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php @@ -0,0 +1,37 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2023 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OC\Files\Search\SearchBinaryOperator; +use OCP\Files\Search\ISearchOperator; + +/** + * Optimizer step that can replace the $operator altogether instead of just modifying it + * These steps need some extra logic to properly replace the arguments of binary operators + */ +class ReplacingOptimizerStep extends QueryOptimizerStep { + /** + * Allow optimizer steps to modify query operators + * + * Returns true if the reference $operator points to a new value + */ + public function processOperator(ISearchOperator &$operator): bool { + if ($operator instanceof SearchBinaryOperator) { + $modified = false; + $arguments = $operator->getArguments(); + foreach ($arguments as &$argument) { + if ($this->processOperator($argument)) { + $modified = true; + } + } + if ($modified) { + $operator->setArguments($arguments); + } + } + return false; + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/SplitLargeIn.php b/lib/private/Files/Search/QueryOptimizer/SplitLargeIn.php new file mode 100644 index 00000000000..8aee1975708 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/SplitLargeIn.php @@ -0,0 +1,36 @@ +<?php + +/** + * SPDX-FileCopyrightText: 2024 Nextcloud GmbH and Nextcloud contributors + * SPDX-License-Identifier: AGPL-3.0-or-later + */ +namespace OC\Files\Search\QueryOptimizer; + +use OC\Files\Search\SearchBinaryOperator; +use OC\Files\Search\SearchComparison; +use OCP\Files\Search\ISearchBinaryOperator; +use OCP\Files\Search\ISearchComparison; +use OCP\Files\Search\ISearchOperator; + +/** + * transform IN (1000+ element) into (IN (1000 elements) OR IN(...)) + */ +class SplitLargeIn extends ReplacingOptimizerStep { + public function processOperator(ISearchOperator &$operator): bool { + if ( + $operator instanceof ISearchComparison + && $operator->getType() === ISearchComparison::COMPARE_IN + && count($operator->getValue()) > 1000 + ) { + $chunks = array_chunk($operator->getValue(), 1000); + $chunkComparisons = array_map(function (array $values) use ($operator) { + return new SearchComparison(ISearchComparison::COMPARE_IN, $operator->getField(), $values, $operator->getExtra()); + }, $chunks); + + $operator = new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, $chunkComparisons); + return true; + } + parent::processOperator($operator); + return false; + } +} |