#include <Storages/MergeTree/KeyCondition.h>

#include <Storages/MergeTree/BoolMask.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;

}

/// for "^prefix..." string it returns "prefix"

static String extractFixedPrefixFromRegularExpression(const String & regexp)

{

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;

switch (*pos)

{

case '|':

case '(':

case ')':

case '^':

case '$':

case '.':

case '[':

case ']':

case '?':

case '*':

case '+':

case '\\':

case '{':

case '}':

case '-':

fixed_prefix += *pos;

++pos;

break;

default:

/// all other escape sequences are not supported

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;

}

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>();

/// This optimization can't process alternation - this would require

/// a comprehensive parsing of regular expression.

if (expression.contains('|'))

return false;

String prefix = extractFixedPrefixFromRegularExpression(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;

}

}

return true;

}

/** Calculate expressions, that depend only on constants.

* For index to work when something like "WHERE Date = toDate(now())" is written.

*/

Block KeyCondition::getBlockWithConstants(

const ASTPtr & query, const TreeRewriterResultPtr & syntax_analyzer_result, ContextPtr context)

{

Block result

{

{ DataTypeUInt8().createColumnConstWithDefaultValue(1), std::make_shared<DataTypeUInt8>(), "_dummy" }

};

if (syntax_analyzer_result)

{

auto actions = ExpressionAnalyzer(query, syntax_analyzer_result, context).getConstActionsDAG();

for (const auto & action_node : actions.getOutputs())

{

if (action_node->column)

result.insert(ColumnWithTypeAndName{action_node->column, action_node->result_type, action_node->result_name});

}

}

return result;

}

static NameSet getAllSubexpressionNames(const ExpressionActions & key_expr)

{

NameSet names;

for (const auto & action : key_expr.getActions())

names.insert(action.node->result_name);

return names;

}

void KeyCondition::getAllSpaceFillingCurves(const BuildInfo & info)

{

/// So far the only supported function is mortonEncode and hilbertEncode (Morton and Hilbert curves).

for (const auto & action : info.key_expr->getActions())

{

if (action.node->type == ActionsDAG::ActionType::FUNCTION

&& action.node->children.size() >= 2

&& space_filling_curve_name_to_type.contains(action.node->function_base->getName()))

{

SpaceFillingCurveDescription curve;

curve.function_name = action.node->function_base->getName();

curve.type = space_filling_curve_name_to_type.at(curve.function_name);

curve.key_column_pos = key_columns.at(action.node->result_name);

for (const auto & child : action.node->children)

{

/// All arguments should be regular input columns.

if (child->type == ActionsDAG::ActionType::INPUT)

{

curve.arguments.push_back(child->result_name);

}

else

{

curve.arguments.clear();

break;

}

}

/// So far we only support the case of two arguments.

if (2 == curve.arguments.size())

key_space_filling_curves.push_back(std::move(curve));

}

}

}

ActionsDAGWithInversionPushDown::ActionsDAGWithInversionPushDown(const ActionsDAG::Node * predicate_, const ContextPtr & context)

{

if (!predicate_)

return;

/** When non-strictly monotonic functions are employed in functional index (e.g. ORDER BY toStartOfHour(dateTime)),

* the use of NOT operator in predicate will result in the indexing algorithm leave out some data.

* This is caused by rewriting in KeyCondition::tryParseAtomFromAST of relational operators to less strict

* when parsing the AST into internal RPN representation.

* To overcome the problem, before parsing the AST we transform it to its semantically equivalent form where all NOT's

* are pushed down and applied (when possible) to leaf nodes.

*/

dag = cloneDAGWithInversionPushDown(predicate_, context);

predicate = dag->getOutputs()[0];

}

KeyCondition::KeyCondition(

const ActionsDAGWithInversionPushDown & filter_dag,

ContextPtr context,

const Names & key_column_names_,

const ExpressionActionsPtr & key_expr_,

bool single_point_,

bool skip_analysis_)

: num_key_columns(key_column_names_.size())

, single_point(single_point_)

, date_time_overflow_behavior_ignore(

context->getSettingsRef()[Setting::date_time_overflow_behavior] == FormatSettings::DateTimeOverflowBehavior::Ignore)

{

size_t key_index = 0;

for (const auto & name : key_column_names_)

{

key_columns.try_emplace(name, key_index);

++key_index;

}

/// Skip any analysis. Toggled by the `use_primary_key` setting. This is useful for catching bugs

/// in the index condition analysis logic. It is better to skip analysis in the constructor rather than in

/// `checkInHyperrectangle` or elsewhere, because bugs during `extractAtomFromTree` calls can lead to

/// unexpected exceptions.

/// This will lead to reading all granules with no primary key skipping.

if (skip_analysis_)

{

has_filter = (filter_dag.predicate != nullptr);

relaxed = true;

rpn.emplace_back(RPNElement::FUNCTION_UNKNOWN);

return;

}

auto info = BuildInfo {.key_expr = key_expr_, .key_subexpr_names = getAllSubexpressionNames(*key_expr_)};

if (context->getSettingsRef()[Setting::analyze_index_with_space_filling_curves])

getAllSpaceFillingCurves(info);

if (!filter_dag.predicate)

{

has_filter = false;

relaxed = true;

rpn.emplace_back(RPNElement::FUNCTION_UNKNOWN);

return;

}

has_filter = true;

RPNBuilder<RPNElement> builder(filter_dag.predicate, context, [&](const RPNBuilderTreeNode & node, RPNElement & out)

{

return extractAtomFromTree(node, info, out);

});

rpn = std::move(builder).extractRPN();

findHyperrectanglesForArgumentsOfSpaceFillingCurves();

if (std::any_of(rpn.begin(), rpn.end(), [&](const auto & elem) { return always_relaxed_atom_elements.contains(elem.function); }))

relaxed = true;

}

KeyCondition::KeyCondition(

ThisIsPrivate, ColumnIndices key_columns_, size_t num_key_columns_, bool single_point_,

bool date_time_overflow_behavior_ignore_, bool relaxed_)

: has_filter(true)

, key_columns(std::move(key_columns_))

, num_key_columns(num_key_columns_)

, single_point(single_point_)

, date_time_overflow_behavior_ignore(date_time_overflow_behavior_ignore_)

, relaxed(relaxed_)

{}

bool KeyCondition::addCondition(const String & column, const Range & range)

{

if (!key_columns.contains(column))

return false;

rpn.emplace_back(RPNElement::FUNCTION_IN_RANGE, std::vector<size_t>{key_columns[column]}, range);

rpn.emplace_back(RPNElement::FUNCTION_AND);

return true;

}

bool KeyCondition::getConstant(const ASTPtr & expr, Block & block_with_constants, Field & out_value, DataTypePtr & out_type)

{

RPNBuilderTreeContext tree_context(nullptr, block_with_constants, nullptr);

RPNBuilderTreeNode node(expr.get(), tree_context);

return node.tryGetConstant(out_value, out_type);

}

bool KeyCondition::hasOnlyConjunctions() const

{

return std::ranges::none_of(rpn, [](RPNElement element) { return element.function == RPNElement::FUNCTION_OR; });

}

static Field applyFunctionForField(

const FunctionBasePtr & func,

const DataTypePtr & arg_type,

const Field & arg_value)

{

ColumnsWithTypeAndName columns

{

{ arg_type->createColumnConst(1, arg_value), arg_type, "x" },

};

auto col = func->execute(columns, func->getResultType(), 1, /* dry_run = */ false);

return (*col)[0];

}

/// applyFunction will execute the function with one `field` or the column which `field` refers to.

static FieldRef applyFunction(const FunctionBasePtr & func, const DataTypePtr & current_type, const FieldRef & field)

{

chassert(func != nullptr);

/// Fallback for fields without block reference.

if (field.isExplicit())

return applyFunctionForField(func, current_type, field);

/// We will cache the function result inside `field.columns`, because this function will call many times

/// from many fields from same column. When the column is huge, for example there are thousands of marks, we need a cache.

/// The cache key is like `_[function_pointer]_[param_column_id]` to identify a unique <function, param> pair.

WriteBufferFromOwnString buf;

writeText("_", buf);

writePointerHex(func.get(), buf);

writeText("_" + toString(field.column_idx), buf);

String result_name = buf.str();

const auto & columns = field.columns;

size_t result_idx = columns->size();

for (size_t i = 0; i < result_idx; ++i)

{

if ((*columns)[i].name == result_name)