diff options
author | Robin Appelman <robin@icewind.nl> | 2023-09-21 13:49:16 +0200 |
---|---|---|
committer | Robin Appelman <robin@icewind.nl> | 2024-02-15 17:55:40 +0100 |
commit | 2e14a7a4a6efb5444fb65e0c2368e3420d024d90 (patch) | |
tree | 6f68533daa5fb6ef10261bdc0034e7de910378b5 /lib/private | |
parent | 1f0cba5f991a3c12d230284b3d96f91fb50312fd (diff) | |
download | nextcloud-server-2e14a7a4a6efb5444fb65e0c2368e3420d024d90.tar.gz nextcloud-server-2e14a7a4a6efb5444fb65e0c2368e3420d024d90.zip |
optimize query pattern used by storage filter
Signed-off-by: Robin Appelman <robin@icewind.nl>
Diffstat (limited to 'lib/private')
9 files changed, 377 insertions, 48 deletions
diff --git a/lib/private/Files/Cache/SearchBuilder.php b/lib/private/Files/Cache/SearchBuilder.php index 38161ec9cc6..fe021a62e9e 100644 --- a/lib/private/Files/Cache/SearchBuilder.php +++ b/lib/private/Files/Cache/SearchBuilder.php @@ -48,6 +48,7 @@ class SearchBuilder { ISearchComparison::COMPARE_LESS_THAN => 'lt', ISearchComparison::COMPARE_LESS_THAN_EQUAL => 'lte', ISearchComparison::COMPARE_DEFINED => 'isNotNull', + ISearchComparison::COMPARE_IN => 'in', ]; protected static $searchOperatorNegativeMap = [ @@ -59,6 +60,34 @@ class SearchBuilder { ISearchComparison::COMPARE_LESS_THAN => 'gte', ISearchComparison::COMPARE_LESS_THAN_EQUAL => 'gt', ISearchComparison::COMPARE_DEFINED => 'isNull', + ISearchComparison::COMPARE_IN => 'notIn', + ]; + + protected static $fieldTypes = [ + 'mimetype' => 'string', + 'mtime' => 'integer', + 'name' => 'string', + 'path' => 'string', + 'size' => 'integer', + 'tagname' => 'string', + 'systemtag' => 'string', + 'favorite' => 'boolean', + 'fileid' => 'integer', + 'storage' => 'integer', + 'share_with' => 'string', + 'share_type' => 'integer', + 'owner' => 'string', + ]; + + protected static $paramTypeMap = [ + 'string' => IQueryBuilder::PARAM_STR, + 'integer' => IQueryBuilder::PARAM_INT, + 'boolean' => IQueryBuilder::PARAM_BOOL, + ]; + protected static $paramArrayTypeMap = [ + 'string' => IQueryBuilder::PARAM_STR_ARRAY, + 'integer' => IQueryBuilder::PARAM_INT_ARRAY, + 'boolean' => IQueryBuilder::PARAM_INT_ARRAY, ]; public const TAG_FAVORITE = '_$!<Favorite>!$_'; @@ -142,31 +171,56 @@ class SearchBuilder { ?IMetadataQuery $metadataQuery = null ) { if ($comparison->getExtra()) { - [$field, $value, $type] = $this->getExtraOperatorField($comparison, $metadataQuery); + [$field, $value, $type, $paramType] = $this->getExtraOperatorField($comparison, $metadataQuery); } else { - [$field, $value, $type] = $this->getOperatorFieldAndValue($comparison); + [$field, $value, $type, $paramType] = $this->getOperatorFieldAndValue($comparison); } if (isset($operatorMap[$type])) { $queryOperator = $operatorMap[$type]; - return $builder->expr()->$queryOperator($field, $this->getParameterForValue($builder, $value)); + return $builder->expr()->$queryOperator($field, $this->getParameterForValue($builder, $value, $paramType)); } else { throw new \InvalidArgumentException('Invalid operator type: ' . $comparison->getType()); } } - private function getOperatorFieldAndValue(ISearchComparison $operator) { + /** + * @param ISearchComparison $operator + * @return list{string, string|integer|\DateTime|(\DateTime|int|string)[], string, string} + */ + private function getOperatorFieldAndValue(ISearchComparison $operator): array { $this->validateComparison($operator); - $field = $operator->getField(); $value = $operator->getValue(); $type = $operator->getType(); + $pathEqHash = $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true); + return $this->getOperatorFieldAndValueInner($field, $value, $type, $pathEqHash); + } + /** + * @param string $field + * @param string|integer|\DateTime|(\DateTime|int|string)[] $value + * @param string $type + * @return list{string, string|integer|\DateTime|(\DateTime|int|string)[], string, string} + */ + private function getOperatorFieldAndValueInner(string $field, mixed $value, string $type, bool $pathEqHash): array { + $paramType = self::$fieldTypes[$field]; + if ($type === ISearchComparison::COMPARE_IN) { + $resultField = $field; + $values = []; + foreach ($value as $arrayValue) { + /** @var string|integer|\DateTime $arrayValue */ + [$arrayField, $arrayValue] = $this->getOperatorFieldAndValueInner($field, $arrayValue, ISearchComparison::COMPARE_EQUAL, $pathEqHash); + $resultField = $arrayField; + $values[] = $arrayValue; + } + return [$resultField, $values, ISearchComparison::COMPARE_IN, $paramType]; + } if ($field === 'mimetype') { $value = (string)$value; - if ($operator->getType() === ISearchComparison::COMPARE_EQUAL) { + if ($type === ISearchComparison::COMPARE_EQUAL) { $value = (int)$this->mimetypeLoader->getId($value); - } elseif ($operator->getType() === ISearchComparison::COMPARE_LIKE) { + } elseif ($type === ISearchComparison::COMPARE_LIKE) { // transform "mimetype='foo/%'" to "mimepart='foo'" if (preg_match('|(.+)/%|', $value, $matches)) { $field = 'mimepart'; @@ -183,6 +237,7 @@ class SearchBuilder { } elseif ($field === 'favorite') { $field = 'tag.category'; $value = self::TAG_FAVORITE; + $paramType = 'string'; } elseif ($field === 'name') { $field = 'file.name'; } elseif ($field === 'tagname') { @@ -191,53 +246,49 @@ class SearchBuilder { $field = 'systemtag.name'; } elseif ($field === 'fileid') { $field = 'file.fileid'; - } elseif ($field === 'path' && $type === ISearchComparison::COMPARE_EQUAL && $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true)) { + } elseif ($field === 'path' && $type === ISearchComparison::COMPARE_EQUAL && $pathEqHash) { $field = 'path_hash'; $value = md5((string)$value); } elseif ($field === 'owner') { $field = 'uid_owner'; } - return [$field, $value, $type]; + return [$field, $value, $type, $paramType]; } private function validateComparison(ISearchComparison $operator) { - $types = [ - 'mimetype' => 'string', - 'mtime' => 'integer', - 'name' => 'string', - 'path' => 'string', - 'size' => 'integer', - 'tagname' => 'string', - 'systemtag' => 'string', - 'favorite' => 'boolean', - 'fileid' => 'integer', - 'storage' => 'integer', - 'share_with' => 'string', - 'share_type' => 'integer', - 'owner' => 'string', - ]; $comparisons = [ - 'mimetype' => ['eq', 'like'], + 'mimetype' => ['eq', 'like', 'in'], 'mtime' => ['eq', 'gt', 'lt', 'gte', 'lte'], - 'name' => ['eq', 'like', 'clike'], - 'path' => ['eq', 'like', 'clike'], + 'name' => ['eq', 'like', 'clike', 'in'], + 'path' => ['eq', 'like', 'clike', 'in'], 'size' => ['eq', 'gt', 'lt', 'gte', 'lte'], 'tagname' => ['eq', 'like'], 'systemtag' => ['eq', 'like'], 'favorite' => ['eq'], - 'fileid' => ['eq'], - 'storage' => ['eq'], + 'fileid' => ['eq', 'in'], + 'storage' => ['eq', 'in'], 'share_with' => ['eq'], 'share_type' => ['eq'], 'owner' => ['eq'], ]; - if (!isset($types[$operator->getField()])) { + if (!isset(self::$fieldTypes[$operator->getField()])) { throw new \InvalidArgumentException('Unsupported comparison field ' . $operator->getField()); } - $type = $types[$operator->getField()]; - if (gettype($operator->getValue()) !== $type) { - throw new \InvalidArgumentException('Invalid type for field ' . $operator->getField()); + $type = self::$fieldTypes[$operator->getField()]; + if ($operator->getType() === ISearchComparison::COMPARE_IN) { + if (!is_array($operator->getValue())) { + throw new \InvalidArgumentException('Invalid type for field ' . $operator->getField()); + } + foreach ($operator->getValue() as $arrayValue) { + if (gettype($arrayValue) !== $type) { + throw new \InvalidArgumentException('Invalid type in array for field ' . $operator->getField()); + } + } + } else { + if (gettype($operator->getValue()) !== $type) { + throw new \InvalidArgumentException('Invalid type for field ' . $operator->getField()); + } } if (!in_array($operator->getType(), $comparisons[$operator->getField()])) { throw new \InvalidArgumentException('Unsupported comparison for field ' . $operator->getField() . ': ' . $operator->getType()); @@ -246,6 +297,7 @@ class SearchBuilder { private function getExtraOperatorField(ISearchComparison $operator, IMetadataQuery $metadataQuery): array { + $paramType = self::$fieldTypes[$field]; $field = $operator->getField(); $value = $operator->getValue(); $type = $operator->getType(); @@ -259,17 +311,17 @@ class SearchBuilder { throw new \InvalidArgumentException('Invalid extra type: ' . $operator->getExtra()); } - return [$field, $value, $type]; + return [$field, $value, $type, $paramType]; } - private function getParameterForValue(IQueryBuilder $builder, $value) { + private function getParameterForValue(IQueryBuilder $builder, $value, string $paramType) { if ($value instanceof \DateTime) { $value = $value->getTimestamp(); } - if (is_numeric($value)) { - $type = IQueryBuilder::PARAM_INT; + if (is_array($value)) { + $type = self::$paramArrayTypeMap[$paramType]; } else { - $type = IQueryBuilder::PARAM_STR; + $type = self::$paramTypeMap[$paramType]; } return $builder->createNamedParameter($value, $type); } diff --git a/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php new file mode 100644 index 00000000000..7f75731fe94 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php @@ -0,0 +1,30 @@ +<?php + +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..2c32f2e0174 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php @@ -0,0 +1,27 @@ +<?php + +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..62ef2cb2e8e --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php @@ -0,0 +1,99 @@ +<?php + +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) into A AND (B OR C) + */ +class MergeDistributiveOperations extends ReplacingOptimizerStep { + public function processOperator(ISearchOperator &$operator): bool { + if ( + $operator instanceof SearchBinaryOperator && + $this->isAllSameBinaryOperation($operator->getArguments()) + ) { + $topLevelType = $operator->getType(); + + $groups = $this->groupBinaryOperatorsByChild($operator->getArguments(), 0); + $outerOperations = array_map(function (array $operators) use ($topLevelType) { + if (count($operators) === 1) { + return $operators[0]; + } + /** @var ISearchBinaryOperator $firstArgument */ + $firstArgument = $operators[0]; + $outerType = $firstArgument->getType(); + $extractedLeftHand = $firstArgument->getArguments()[0]; + + $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); + $extractedRightHand = new SearchBinaryOperator($topLevelType, $rightHandArguments); + return new SearchBinaryOperator( + $outerType, + [$extractedLeftHand, $extractedRightHand] + ); + }, $groups); + $operator = new SearchBinaryOperator($topLevelType, $outerOperations); + parent::processOperator($operator); + return true; + } + return parent::processOperator($operator); + } + + /** + * Check that a list of operators is all the same type of (non-empty) binary operators + * + * @param ISearchOperator[] $operators + * @return bool + * @psalm-assert-if-true SearchBinaryOperator[] $operators + */ + private function isAllSameBinaryOperation(array $operators): bool { + $operation = null; + foreach ($operators as $operator) { + if (!$operator instanceof SearchBinaryOperator) { + return false; + } + if (!$operator->getArguments()) { + return false; + } + if ($operation === null) { + $operation = $operator->getType(); + } else { + if ($operation !== $operator->getType()) { + return false; + } + } + } + return true; + } + + /** + * Group a list of binary search operators that have a common argument + * + * @param SearchBinaryOperator[] $operators + * @return SearchBinaryOperator[][] + */ + private function groupBinaryOperatorsByChild(array $operators, int $index = 0): array { + $result = []; + foreach ($operators as $operator) { + /** @var SearchBinaryOperator|SearchComparison $child */ + $child = $operator->getArguments()[$index]; + ; + $childKey = (string) $child; + $result[$childKey][] = $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..550d85fbda0 --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php @@ -0,0 +1,68 @@ +<?php + +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); + $in->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, $group[0]->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true)); + 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) { + $key = $operator->getField() . $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true); + $result[$key][] = $operator; + } else { + $result[] = [$operator]; + } + } + return array_values($result); + } +} diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php index 160b27b7f11..6240ef3367e 100644 --- a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php +++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php @@ -29,15 +29,18 @@ 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 OrEqualsToIn(), + new FlattenNestedBool(), ]; } - 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/ReplacingOptimizerStep.php b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php new file mode 100644 index 00000000000..546061522bc --- /dev/null +++ b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php @@ -0,0 +1,31 @@ +<?php + +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) { + $modified = $modified || $this->processOperator($argument); + } + if ($modified) { + $operator->setArguments($arguments); + } + } + return false; + } +} diff --git a/lib/private/Files/Search/SearchBinaryOperator.php b/lib/private/Files/Search/SearchBinaryOperator.php index d7bba8f1b4e..2b01ad58e5f 100644 --- a/lib/private/Files/Search/SearchBinaryOperator.php +++ b/lib/private/Files/Search/SearchBinaryOperator.php @@ -28,7 +28,7 @@ use OCP\Files\Search\ISearchOperator; class SearchBinaryOperator implements ISearchBinaryOperator { /** @var string */ private $type; - /** @var ISearchOperator[] */ + /** @var (SearchBinaryOperator|SearchComparison)[] */ private $arguments; private $hints = []; @@ -36,7 +36,7 @@ class SearchBinaryOperator implements ISearchBinaryOperator { * SearchBinaryOperator constructor. * * @param string $type - * @param ISearchOperator[] $arguments + * @param (SearchBinaryOperator|SearchComparison)[] $arguments */ public function __construct($type, array $arguments) { $this->type = $type; @@ -57,6 +57,14 @@ class SearchBinaryOperator implements ISearchBinaryOperator { return $this->arguments; } + /** + * @param ISearchOperator[] $arguments + * @return void + */ + public function setArguments(array $arguments): void { + $this->arguments = $arguments; + } + public function getQueryHint(string $name, $default) { return $this->hints[$name] ?? $default; } @@ -64,4 +72,11 @@ class SearchBinaryOperator implements ISearchBinaryOperator { public function setQueryHint(string $name, $value): void { $this->hints[$name] = $value; } + + public function __toString(): string { + if ($this->type === ISearchBinaryOperator::OPERATOR_NOT) { + return '(not ' . $this->arguments[0] . ')'; + } + return '(' . implode(' ' . $this->type . ' ', $this->arguments) . ')'; + } } diff --git a/lib/private/Files/Search/SearchComparison.php b/lib/private/Files/Search/SearchComparison.php index d94b3e9dfab..8ca05236105 100644 --- a/lib/private/Files/Search/SearchComparison.php +++ b/lib/private/Files/Search/SearchComparison.php @@ -33,7 +33,7 @@ class SearchComparison implements ISearchComparison { public function __construct( private string $type, private string $field, - private \DateTime|int|string|bool $value, + private \DateTime|int|string|bool|array $value, private string $extra = '' ) { } @@ -53,9 +53,9 @@ class SearchComparison implements ISearchComparison { } /** - * @return \DateTime|int|string|bool + * @return \DateTime|int|string|bool|(\DateTime|int|string)[] */ - public function getValue(): string|int|bool|\DateTime { + public function getValue(): string|int|bool|\DateTime|array { return $this->value; } @@ -78,4 +78,8 @@ class SearchComparison implements ISearchComparison { public static function escapeLikeParameter(string $param): string { return addcslashes($param, '\\_%'); } + + public function __toString(): string { + return $this->field . ' ' . $this->type . ' ' . json_encode($this->value); + } } |