#include <Storages/MergeTree/KeyCondition.h>

#include <Storages/MergeTree/BoolMask.h>

#include <Columns/ColumnLowCardinality.h>

#include <Core/AccurateComparison.h>

#include <Core/PlainRanges.h>

#include <DataTypes/DataTypesNumber.h>

#include <DataTypes/DataTypeTime64.h>

#include <DataTypes/DataTypeLowCardinality.h>

#include <DataTypes/DataTypeNullable.h>

#include <DataTypes/DataTypeNothing.h>

#include <DataTypes/FieldToDataType.h>

#include <DataTypes/getLeastSupertype.h>

#include <DataTypes/Utils.h>

#include <Interpreters/Context.h>

#include <Interpreters/TreeRewriter.h>

#include <Interpreters/ExpressionAnalyzer.h>

#include <Interpreters/ExpressionActions.h>

#include <Interpreters/castColumn.h>

#include <Interpreters/misc.h>

#include <Functions/FunctionFactory.h>

#include <Functions/indexHint.h>

#include <Functions/CastOverloadResolver.h>

#include <Functions/IFunction.h>

#include <Functions/IFunctionAdaptors.h>

#include <Functions/IFunctionDateOrDateTime.h>

#include <Functions/geometryConverters.h>

#include <Common/FieldVisitorToString.h>

#include <Common/HilbertUtils.h>

#include <Common/FieldVisitorConvertToNumber.h>

#include <Common/MortonUtils.h>

#include <Common/typeid_cast.h>

#include <DataTypes/DataTypeArray.h>

#include <DataTypes/DataTypeTuple.h>

#include <Columns/ColumnArray.h>

#include <Columns/ColumnSet.h>

#include <Columns/ColumnConst.h>

#include <Columns/ColumnTuple.h>

#include <Core/Settings.h>

#include <Interpreters/convertFieldToType.h>

#include <Interpreters/Set.h>

#include <Parsers/ASTLiteral.h>

#include <Parsers/ASTSelectQuery.h>

#include <IO/WriteBufferFromString.h>

#include <IO/Operators.h>

#include <algorithm>

#include <cassert>

#include <stack>

#include <boost/geometry.hpp>

#include <boost/geometry/geometries/polygon.hpp>

#include <boost/smart_ptr/make_shared_object.hpp>

namespace DB

{

namespace Setting

{

extern const SettingsBool analyze_index_with_space_filling_curves;

extern const SettingsDateTimeOverflowBehavior date_time_overflow_behavior;

extern const SettingsTimezone session_timezone;

}

namespace ErrorCodes

{

extern const int LOGICAL_ERROR;

}

/// Returns true if '\' followed by this character means "match this character

/// literally". For example, '\.' matches a literal dot, '\(' matches a

/// literal '(', '\-' matches a literal '-'.

/// Returns false for escape sequences where the matched character is different

/// from what follows '\': '\n' matches a newline (not 'n'), '\d' matches any

/// digit (not 'd'), '\x41' matches 'A' (not 'x').

static bool isLiteralEscape(char c)

{

switch (c)

{

case '|':

case '(':

case ')':

case '^':

case '$':

case '.':

case '[':

case ']':

case '?':

case '*':

case '+':

case '\\':

case '{':

case '}':

case '-':

return true;

default:

return false;

}

UNREACHABLE();

}

/// Extracts a conservative fixed literal prefix from a ^-anchored regular expression.

///

/// In regex, '^' means "must start at the beginning of the string".

/// This function walks the pattern after '^' and collects characters that

/// are guaranteed to appear, in order, at the start of every matching string.

/// It stops as soon as it hits any metacharacter or special construct where it

/// cannot guarantee a fixed character. The parser is conservative and may miss

/// some cases where a guaranteed fixed prefix could be derived but would be

/// complicated to do so. The result is a prefix that is common to all possible

/// matching strings.

///

/// "^abc"

/// Every matching string starts with exactly "abc".

/// Prefix: "abc".

///

/// "^abc.*"

/// '.' means "any single character" and '*' means "zero or more times".

/// So after "abc" anything can follow. We can only guarantee "abc".

/// Prefix: "abc".

///

/// "^abc\\|def"

/// A backslash before a special character removes its special meaning.

/// '|' normally means "or" (see below), but '\\|' means a literal '|'

/// character. So this matches strings starting with the text "abc|def".

/// Prefix: "abc|def".

///

/// "^abc\\d"

/// '\\d' means "any digit" (0-9). It is not a single fixed character,

/// so we stop. We can only guarantee "abc".

/// Prefix: "abc".

///

/// "^abc|def"

/// '|' means "or" — match the left side or the right side.

/// This means: (string starts with "abc") OR (string contains "def" anywhere).

/// The right side has no '^', so it can match in the middle of a string.

/// We cannot guarantee any prefix at all.

/// Prefix: "".

///

/// "^abc[12]"

/// '[12]' is a character class — it matches either '1' or '2'.

/// Since the next character is not fixed, we stop at "abc".

/// Prefix: "abc".

///

/// '(' is treated as a stop character (')' cannot appear unescaped in a

/// valid regex without a preceding '('). Patterns like

/// "^(abc)def" could theoretically yield prefix "abcdef", but analyzing

/// group semantics (optional groups, alternation inside groups, etc.)

/// is complex and error-prone. The alternation helper

/// `extractCommonPrefixFromAlternationBranches` handles the important case of

/// "^(branch1|branch2|...)" separately.

static String extractFixedPrefixFromRegularExpression(const String & regexp)

{

/// We can only analyze regexes that start with '^' — those are the only ones that guarantee a fixed prefix.

if (regexp.size() <= 1 || regexp[0] != '^')

return {};

String fixed_prefix;

const char * begin = regexp.data() + 1;

const char * pos = begin;

const char * end = regexp.data() + regexp.size();

while (pos < end)

{

switch (*pos)

{

case '\0':

pos = end;

break;

case '\\':

{

++pos;

if (pos == end)

break;

if (isLiteralEscape(*pos))

{

fixed_prefix += *pos;

++pos;

}

else

pos = end;

break;

}

/// non-trivial cases

case '|':

fixed_prefix.clear();

[[fallthrough]];

case '(':

case '[':

case '^':

case '$':

case '.':

case '+':

pos = end;

break;

/// Quantifiers that allow a zero number of occurrences.

case '{':

case '?':

case '*':

if (!fixed_prefix.empty())

fixed_prefix.pop_back();

pos = end;

break;

default:

fixed_prefix += *pos;

pos++;

break;

}

}

return fixed_prefix;

}

/// Returns true if the expression contains any unescaped '|'.

static bool expressionHasUnescapedAlternation(const String & expression)

{

for (size_t i = 0; i < expression.size(); ++i)

{

/// \\| is not an alternation, but a literal '|', so skip the next character after a backslash.

if (expression[i] == '\\' && i + 1 < expression.size())

{

++i;

continue;

}

if (expression[i] == '|')

return true;

}

return false;

}

/// Handles the simple alternation pattern "^(branch1|branch2|...)$?" where

/// each branch is a plain literal string (no metacharacters, no nesting).

///

/// This is called when the expression contains an unescaped '|', meaning

/// `extractFixedPrefixFromRegularExpression` cannot be used (it would stop

/// at '|' or '('). Returns empty for any pattern more complex than simple

/// literal branches inside a single group.

///

/// "^(abc-xx|abc-yy)"

/// The '|' gives two alternatives: the string starts with "abc-xx" or "abc-yy".

/// Both start with "abc-", so every matching string begins with "abc-".

/// Prefix: "abc-".

///

/// "^(abc-xx-1|abc-xx-2|abc-yy-1)"

/// Three alternatives. All three start with "abc-", but they diverge

/// after that ('x' vs 'y'). So "abc-" is the longest common start.

/// Prefix: "abc-".

///

/// "^(abc|def)"

/// Two alternatives: "abc" and "def". They share nothing at the start —

/// 'a' vs 'd' already differ. We cannot guarantee any prefix.

/// Prefix: "".

///

/// "^(abc|def)$"

/// '$' means "must end at the end of the string". It constrains what

/// comes after the match, but does not change what the string starts

/// with. So the prefix analysis is the same as without '$'.

/// Prefix: "".

///

/// Not supported (returns empty — could be improved in the future):

///

/// "^(abc.*|abd.*)"

/// Branches contain '.*' (wildcard). We only handle plain literal branches.

/// The common prefix "ab" could theoretically be extracted, but is not.

/// Prefix: "".

///

/// "^(abc|abd)+"

/// The '+' after the group means it must appear at least once.

/// We only handle patterns where the group is followed by '$' or end

/// of expression. Prefix: "".

///

/// "^(abc(1|2)|abc(3|4))"

/// Branches contain nested groups. We only handle flat literal branches.

/// The common prefix "abc" could theoretically be extracted, but is not.

/// Prefix: "".

static String extractCommonPrefixFromAlternationBranches(const String & expression)

{

/// We only handle "^(literal1|literal2|...)$?".

/// Reject anything that doesn't start with "^(".

if (expression.size() < 4 || expression[0] != '^' || expression[1] != '(')

return {};

const char * pos = expression.data() + 2; /// Start right after "^("

const char * end = expression.data() + expression.size();

/// Split branches by '|'. Each branch must be a plain literal —

/// no metacharacters, no nested groups, no character classes.

/// If we see anything other than a literal char, escaped char, or '|',

/// we give up.

std::vector<String> branches;

String current_branch;

while (pos < end)

{

if (*pos == '\\' && pos + 1 < end)

{

char next = *(pos + 1);

if (isLiteralEscape(next))

{

current_branch += next;

pos += 2;

}

else

return {};

}

else if (*pos == '|')

{

/// Branch separator — save the current branch and start a new one.

branches.push_back(std::move(current_branch));

current_branch.clear();

++pos;

}

else if (*pos == ')')

{

/// End of the group. Save the last branch.

branches.push_back(std::move(current_branch));

++pos;

/// Allow only '$' or end of expression after ')'.

if (pos < end && *pos == '$')

++pos;

if (pos != end)

return {};

break;

}

else if (

*pos == '(' || *pos == '[' || *pos == '.' || *pos == '*' || *pos == '+' || *pos == '?' || *pos == '{' || *pos == '^'

|| *pos == '$')

{

/// Any metacharacter inside a branch — too complex, give up.

return {};

}

else

{

/// Plain literal character.

current_branch += *pos;

++pos;

}

}

if (branches.size() < 2)

return {};

/// Compute the longest prefix common to all branches.

String common_prefix = branches[0];

for (size_t i = 1; i < branches.size(); ++i)

{

size_t common_len = 0;

size_t max_len = std::min(common_prefix.size(), branches[i].size());

while (common_len < max_len && common_prefix[common_len] == branches[i][common_len])

++common_len;

common_prefix.resize(common_len);

if (common_prefix.empty())

return {};

}

return common_prefix;

}

const KeyCondition::AtomMap KeyCondition::atom_map

{

{

"notEquals",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_NOT_IN_RANGE;

out.range = Range(value);

return true;

}

},

{

"equals",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range(value);

return true;

}

},

{

"less",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range::createRightBounded(value, false);

return true;

}

},

{

"greater",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range::createLeftBounded(value, false);

return true;

}

},

{

"lessOrEquals",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range::createRightBounded(value, true);

return true;

}

},

{

"greaterOrEquals",

[] (RPNElement & out, const Field & value)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range::createLeftBounded(value, true);

return true;

}

},

{

"in",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_SET;

return true;

}

},

{

"notIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_NOT_IN_SET;

return true;

}

},

{

"globalIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_SET;

return true;

}

},

{

"globalNotIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_NOT_IN_SET;

return true;

}

},

{

"has",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_SET;

return true;

}

},

{

"nullIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_SET;

return true;

}

},

{

"notNullIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_NOT_IN_SET;

return true;

}

},

{

"globalNullIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_SET;

return true;

}

},

{

"globalNotNullIn",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_NOT_IN_SET;

return true;

}

},

{

"empty",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = Range(String{});

return true;

}

},

{

"notEmpty",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_NOT_IN_RANGE;

out.range = Range(String{});

return true;

}

},

{

"like",

[] (RPNElement & out, const Field & value)

{

if (value.getType() != Field::Types::String)

return false;

auto [prefix, is_perfect] = extractFixedPrefixFromLikePattern(value.safeGet<String>(), /*requires_perfect_prefix*/ false);

if (prefix.empty())

return false;

if (!is_perfect)

out.relaxed = true;

String right_bound = firstStringThatIsGreaterThanAllStringsWithPrefix(prefix);

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = !right_bound.empty()

? Range(prefix, true, right_bound, false)

: Range::createLeftBounded(prefix, true);

return true;

}

},

{

"notLike",

[] (RPNElement & out, const Field & value)

{

if (value.getType() != Field::Types::String)

return false;

auto [prefix, is_perfect] = extractFixedPrefixFromLikePattern(value.safeGet<String>(), /*requires_perfect_prefix*/ true);

if (prefix.empty())

return false;

chassert(is_perfect);

String right_bound = firstStringThatIsGreaterThanAllStringsWithPrefix(prefix);

out.function = RPNElement::FUNCTION_NOT_IN_RANGE;

out.range = !right_bound.empty()

? Range(prefix, true, right_bound, false)

: Range::createLeftBounded(prefix, true);

return true;

}

},

{

"startsWith",

[] (RPNElement & out, const Field & value)

{

if (value.getType() != Field::Types::String)

return false;

String prefix = value.safeGet<String>();

if (prefix.empty())

return false;

String right_bound = firstStringThatIsGreaterThanAllStringsWithPrefix(prefix);

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = !right_bound.empty()

? Range(prefix, true, right_bound, false)

: Range::createLeftBounded(prefix, true);

return true;

}

},

{

"startsWithUTF8",

[] (RPNElement & out, const Field & value)

{

if (value.getType() != Field::Types::String)

return false;

String prefix = value.safeGet<String>();

if (prefix.empty())

return false;

const bool is_ascii = isAllASCII(reinterpret_cast<const UInt8 *>(prefix.data()), prefix.size());

if (is_ascii == false)

return false;

String right_bound = firstStringThatIsGreaterThanAllStringsWithPrefix(prefix);

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = !right_bound.empty()

? Range(prefix, true, right_bound, false)

: Range::createLeftBounded(prefix, true);

return true;

}

},

{

"match",

[] (RPNElement & out, const Field & value)

{

if (value.getType() != Field::Types::String)

return false;

const String & expression = value.safeGet<String>();

/// ClickHouse `match` patterns must not contain NUL bytes.

/// Do not attempt to optimize such patterns.

if (expression.find('\0') != String::npos)

return false;

String prefix;

if (!expressionHasUnescapedAlternation(expression))

prefix = extractFixedPrefixFromRegularExpression(expression);

else

prefix = extractCommonPrefixFromAlternationBranches(expression);

if (prefix.empty())

return false;

String right_bound = firstStringThatIsGreaterThanAllStringsWithPrefix(prefix);

out.function = RPNElement::FUNCTION_IN_RANGE;

out.range = !right_bound.empty()

? Range(prefix, true, right_bound, false)

: Range::createLeftBounded(prefix, true);

out.relaxed = true;

return true;

}

},

{

"isNotNull",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IS_NOT_NULL;

// isNotNull means (-Inf, +Inf)

out.range = Range::createWholeUniverseWithoutNull();

return true;

}

},

{

"isNull",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_IS_NULL;

// isNull means +Inf (NULLS_LAST) or -Inf (NULLS_FIRST), We don't support discrete

// ranges, instead will use the inverse of (-Inf, +Inf). The inversion happens in

// checkInHyperrectangle.

out.range = Range::createWholeUniverseWithoutNull();

return true;

}

},

{

"pointInPolygon",

[] (RPNElement & out, const Field &)

{

out.function = RPNElement::FUNCTION_POINT_IN_POLYGON;

return true;

}

}

};

static const std::set<KeyCondition::RPNElement::Function> always_relaxed_atom_elements

= {KeyCondition::RPNElement::FUNCTION_UNKNOWN, KeyCondition::RPNElement::FUNCTION_ARGS_IN_HYPERRECTANGLE, KeyCondition::RPNElement::FUNCTION_POINT_IN_POLYGON};

/// Functions with range inversion cannot be relaxed. It will become stricter instead.

/// For example:

/// create table test(d Date, k Int64, s String) Engine=MergeTree order by toYYYYMM(d);

/// insert into test values ('2020-01-01', 1, '');

/// insert into test values ('2020-01-02', 1, '');

/// select * from test where d != '2020-01-01'; -- If relaxed, no record will return

static const std::set<std::string_view> no_relaxed_atom_functions

= {"notLike", "notIn", "globalNotIn", "notNullIn", "globalNotNullIn", "notEquals", "notEmpty"};

static const std::map<std::string, std::string> inverse_relations =

{

{"equals", "notEquals"},

{"notEquals", "equals"},

{"less", "greaterOrEquals"},

{"greaterOrEquals", "less"},

{"greater", "lessOrEquals"},

{"lessOrEquals", "greater"},

{"in", "notIn"},

{"notIn", "in"},

{"globalIn", "globalNotIn"},

{"globalNotIn", "globalIn"},

{"nullIn", "notNullIn"},

{"notNullIn", "nullIn"},

{"globalNullIn", "globalNotNullIn"},

{"globalNullNotIn", "globalNullIn"},

{"isNull", "isNotNull"},

{"isNotNull", "isNull"},

{"like", "notLike"},

{"notLike", "like"},

{"ilike", "notILike"},

{"notILike", "ilike"},

{"empty", "notEmpty"},

{"notEmpty", "empty"},

};

static bool isLogicalOperator(const String & func_name)

{

return (func_name == "and" || func_name == "or" || func_name == "not" || func_name == "indexHint");

}

/// The node can be one of:

/// - Logical operator (AND, OR, NOT and indexHint() - logical NOOP)

/// - An "atom" (relational operator, constant, expression)

/// - A logical constant expression

/// - Any other function

ASTPtr cloneASTWithInversionPushDown(const ASTPtr node, const bool need_inversion = false)

{

const ASTFunction * func = node->as<ASTFunction>();

if (func && isLogicalOperator(func->name))

{

if (func->name == "not")

{

return cloneASTWithInversionPushDown(func->arguments->children.front(), !need_inversion);

}

const auto result_node = makeASTFunction(func->name);

/// indexHint() is a special case - logical NOOP function

if (result_node->name != "indexHint" && need_inversion)

{

result_node->name = (result_node->name == "and") ? "or" : "and";

}

if (func->arguments)

{

for (const auto & child : func->arguments->children)

{

result_node->arguments->children.push_back(cloneASTWithInversionPushDown(child, need_inversion));

}

}

return result_node;

}

auto cloned_node = node->clone();

if (func && inverse_relations.find(func->name) != inverse_relations.cend())

{

if (need_inversion)

{

cloned_node->as<ASTFunction>()->name = inverse_relations.at(func->name);

}

return cloned_node;

}

return need_inversion ? makeASTOperator("not", cloned_node) : cloned_node;

}

static bool isTrivialCast(const ActionsDAG::Node & node)

{

if (node.function_base->getName() != "CAST" || node.children.size() != 2 || node.children[1]->type != ActionsDAG::ActionType::COLUMN)

return false;

const auto * column_const = typeid_cast<const ColumnConst *>(node.children[1]->column.get());

if (!column_const)

return false;

Field field = column_const->getField();

if (field.getType() != Field::Types::String)

return false;

auto type_name = field.safeGet<String>();

return node.children[0]->result_type->getName() == type_name;

}

static const ActionsDAG::Node & cloneDAGWithInversionPushDown(

const ActionsDAG::Node & node,

ActionsDAG & inverted_dag,

std::unordered_map<const ActionsDAG::Node *, const ActionsDAG::Node *> & inputs_mapping,

const ContextPtr & context,

const bool need_inversion)

{

const ActionsDAG::Node * res = nullptr;

bool handled_inversion = false;

switch (node.type)

{

case (ActionsDAG::ActionType::INPUT):

{

auto & input = inputs_mapping[&node];

if (input == nullptr)

/// Note: inputs order is not important here. Will match columns by names.

input = &inverted_dag.addInput({node.column, node.result_type, node.result_name});

res = input;

break;

}

case (ActionsDAG::ActionType::COLUMN):

{

String name;

if (const auto * column_const = typeid_cast<const ColumnConst *>(node.column.get());

column_const && column_const->getDataType() != TypeIndex::Function)

{

/// Re-generate column name for constant.

/// DAG from the query (with enabled analyzer) uses suffixes for constants, like 1_UInt8.

/// DAG from the PK does not use it. This breaks matching by column name sometimes.

/// Ideally, we should not compare names, but DAG subtrees instead.

name = ASTLiteral(column_const->getField()).getColumnName();

}

else

name = node.result_name;

res = &inverted_dag.addColumn({node.column, node.result_type, name});

break;

}

case (ActionsDAG::ActionType::ALIAS):

{

/// Ignore aliases

res = &cloneDAGWithInversionPushDown(*node.children.front(), inverted_dag, inputs_mapping, context, need_inversion);

handled_inversion = true;

break;

}

case (ActionsDAG::ActionType::ARRAY_JOIN):

{

const auto & arg = cloneDAGWithInversionPushDown(*node.children.front(), inverted_dag, inputs_mapping, context, false);

res = &inverted_dag.addArrayJoin(arg, {});

break;

}

case (ActionsDAG::ActionType::FUNCTION):

{

auto name = node.function_base->getName();

if (name == "not")

{

res = &cloneDAGWithInversionPushDown(*node.children.front(), inverted_dag, inputs_mapping, context, !need_inversion);

handled_inversion = true;

}

else if (name == "indexHint")

{

ActionsDAG::NodeRawConstPtrs children;

if (const auto * adaptor = typeid_cast<const FunctionToFunctionBaseAdaptor *>(node.function_base.get()))

{

if (const auto * index_hint = typeid_cast<const FunctionIndexHint *>(adaptor->getFunction().get()))

{

const auto & index_hint_dag = index_hint->getActions();

children = index_hint_dag.getOutputs();

for (auto & arg : children)

arg = &cloneDAGWithInversionPushDown(*arg, inverted_dag, inputs_mapping, context, need_inversion);

}

}

res = &inverted_dag.addFunction(node.function_base, children, "");

handled_inversion = true;

}

else if (name == "materialize")

{

/// Remove "materialize" from index analysis.

res = &cloneDAGWithInversionPushDown(*node.children.front(), inverted_dag, inputs_mapping, context, need_inversion);

/// `need_inversion` was already pushed into the child; avoid adding an extra `not()` wrapper

/// Without this, we could add an extra `not()` here (double inversion), e.g. `NOT materialize(x = 0)` -> `not(notEquals(x, 0))`.

handled_inversion = true;

}

else if (isTrivialCast(node))

{

/// Remove trivial cast and keep its first argument.

res = &cloneDAGWithInversionPushDown(*node.children.front(), inverted_dag, inputs_mapping, context, need_inversion);

/// `need_inversion` was already pushed into the child; avoid adding an extra `not()` wrapper

/// Without this, we could add an extra `not()` here (double inversion), e.g. `NOT CAST(x = 0, 'UInt8')` -> `not(notEquals(x, 0))`.

handled_inversion = true;

}

else if (need_inversion && (name == "and" || name == "or"))

{

ActionsDAG::NodeRawConstPtrs children(node.children);

for (auto & arg : children)

arg = &cloneDAGWithInversionPushDown(*arg, inverted_dag, inputs_mapping, context, need_inversion);

FunctionOverloadResolverPtr function_builder;

if (name == "and")

function_builder = FunctionFactory::instance().get("or", context);

else if (name == "or")

function_builder = FunctionFactory::instance().get("and", context);

assert(function_builder);

/// We match columns by name, so it is important to fill name correctly.

/// So, use empty string to make it automatically.

res = &inverted_dag.addFunction(function_builder, children, "");

handled_inversion = true;

}

else

{

ActionsDAG::NodeRawConstPtrs children(node.children);

for (auto & arg : children)

arg = &cloneDAGWithInversionPushDown(*arg, inverted_dag, inputs_mapping, context, false);

auto it = inverse_relations.find(name);

if (it != inverse_relations.end())

{

const auto & func_name = need_inversion ? it->second : it->first;

auto function_builder = FunctionFactory::instance().get(func_name, context);

res = &inverted_dag.addFunction(function_builder, children, "");

handled_inversion = true;

}

else

{

/// Argument types could change slightly because of our transformations, e.g.

/// LowCardinality can be added because some subexpressions became constant

/// (in particular, sets). If that happens, re-run function overload resolver.

/// Otherwise don't re-run it because some functions may not be available

/// through FunctionFactory::get(), e.g. FunctionCapture.

bool types_changed = false;

for (size_t i = 0; i < children.size(); ++i)

{

if (!node.children[i]->result_type->equals(*children[i]->result_type))

{

types_changed = true;

break;

}

}

if (types_changed)

{

auto function_builder = FunctionFactory::instance().get(name, context);

res = &inverted_dag.addFunction(function_builder, children, "");

}

else

{

res = &inverted_dag.addFunction(node.function_base, children, "");

}

}

}

break;

}

case ActionsDAG::ActionType::PLACEHOLDER:

{

/// I guess it should work as INPUT.

res = &inverted_dag.addPlaceholder(node.result_name, node.result_type);

break;

}

}

if (!handled_inversion && need_inversion)

res = &inverted_dag.addFunction(FunctionFactory::instance().get("not", context), {res}, "");

return *res;

}

static ActionsDAG cloneDAGWithInversionPushDown(const ActionsDAG::Node * predicate, const ContextPtr & context)

{

ActionsDAG res;

std::unordered_map<const ActionsDAG::Node *, const ActionsDAG::Node *> inputs_mapping;

predicate = &DB::cloneDAGWithInversionPushDown(*predicate, res, inputs_mapping, context, false);

res.getOutputs() = {predicate};

return res;

}

const std::unordered_map<String, KeyCondition::SpaceFillingCurveType> KeyCondition::space_filling_curve_name_to_type {

{"mortonEncode", SpaceFillingCurveType::Morton},

{"hilbertEncode", SpaceFillingCurveType::Hilbert}

};

static bool mayExistOnBloomFilter(const KeyCondition::BloomFilterData & condition_bloom_filter_data,

const KeyCondition::ColumnIndexToBloomFilter & column_index_to_column_bf)

{

chassert(condition_bloom_filter_data.hashes_per_column.size() == condition_bloom_filter_data.key_columns.size());

for (auto column_index = 0u; column_index < condition_bloom_filter_data.hashes_per_column.size(); column_index++)

{

// In case bloom filter is missing for parts of the data

// (e.g. for some Parquet row groups: https://github.com/ClickHouse/ClickHouse/pull/62966#discussion_r1722361237).

if (!column_index_to_column_bf.contains(condition_bloom_filter_data.key_columns[column_index]))

{

continue;

}

const auto & column_bf = column_index_to_column_bf.at(condition_bloom_filter_data.key_columns[column_index]);

const auto & hashes = condition_bloom_filter_data.hashes_per_column[column_index];

if (!column_bf->findAnyHash(hashes))

{

return false;

}

}