/* Copyright (c) 2000, 2025, Oracle and/or its affiliates.

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License, version 2.0,

as published by the Free Software Foundation.

This program is designed to work with certain software (including

but not limited to OpenSSL) that is licensed under separate terms,

as designated in a particular file or component or in included license

documentation. The authors of MySQL hereby grant you an additional

permission to link the program and your derivative works with the

separately licensed software that they have either included with

the program or referenced in the documentation.

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 General Public License, version 2.0, for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */

#include "sql/range_optimizer/tree.h"

#include <algorithm>

#include <set>

#include <utility>

#include "m_ctype.h"

#include "m_string.h"

#include "memory_debugging.h"

#include "my_dbug.h"

#include "my_loglevel.h"

#include "my_sqlcommand.h"

#include "mysql/components/services/log_builtins.h"

#include "mysqld_error.h"

#include "sql/handler.h"

#include "sql/key.h"

#include "sql/key_spec.h"

#include "sql/range_optimizer/internal.h"

#include "sql/range_optimizer/range_opt_param.h"

#include "sql/range_optimizer/range_optimizer.h"

#include "sql/sql_class.h"

#include "sql/sql_lex.h"

#include "sql/system_variables.h"

#include "sql/table.h"

#include "sql_string.h"

using std::max;

using std::min;

// Note: tree1 and tree2 are not usable by themselves after tree_and() or

// tree_or().

SEL_TREE *tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2);

SEL_TREE *tree_or(RANGE_OPT_PARAM *param, bool remove_jump_scans,

SEL_TREE *tree1, SEL_TREE *tree2);

SEL_ROOT *key_or(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2);

SEL_ROOT *key_and(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2);

SEL_ARG *rb_delete_fixup(SEL_ARG *root, SEL_ARG *key, SEL_ARG *par);

#ifndef NDEBUG

int test_rb_tree(SEL_ARG *element, SEL_ARG *parent);

#endif

static bool eq_tree(const SEL_ROOT *a, const SEL_ROOT *b);

static bool eq_tree(const SEL_ARG *a, const SEL_ARG *b);

static bool get_range(SEL_ARG **e1, SEL_ARG **e2, const SEL_ROOT *root1);

using opt_range::null_element;

/*

Returns a number of keypart values appended to the key buffer

for min key and max key. This function is used by both Range

Analysis and Partition pruning. For partition pruning we have

to ensure that we don't store also subpartition fields. Thus

we have to stop at the last partition part and not step into

the subpartition fields. For Range Analysis we set last_part

to MAX_KEY which we should never reach.

Note: Caller of this function should take care of sending the

correct flags and correct key to be stored into. In case of

ascending indexes, store_min_key() gets called to store the

min_value to range start_key. In case of descending indexes, it's

called for storing min_value to range end_key.

*/

int SEL_ROOT::store_min_key(KEY_PART *key, uchar **range_key,

uint *range_key_flag, uint last_part,

bool start_key) {

SEL_ARG *key_tree = root->first();

uint res = key_tree->store_min_value(key[key_tree->part].store_length,

range_key, *range_key_flag);

// We've stored min_value, so append min_flag

*range_key_flag |= key_tree->min_flag;

if (key_tree->next_key_part &&

key_tree->next_key_part->type == SEL_ROOT::Type::KEY_RANGE &&

key_tree->part != last_part &&

key_tree->next_key_part->root->part == key_tree->part + 1 &&

!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) {

const bool asc = key_tree->next_key_part->root->is_ascending;

if ((start_key && asc) || (!start_key && !asc))

res += key_tree->next_key_part->store_min_key(

key, range_key, range_key_flag, last_part, start_key);

else {

uint tmp_flag = invert_min_flag(*range_key_flag);

res += key_tree->next_key_part->store_max_key(key, range_key, &tmp_flag,

last_part, start_key);

*range_key_flag = invert_max_flag(tmp_flag);

}

}

return res;

}

/*

Returns the number of keypart values appended to the key buffer.

Note: Caller of this function should take care of sending the

correct flags and correct key to be stored into. In case of

ascending indexes, store_max_key() gets called while storing the

max_value into range end_key. In case of descending indexes,

its max_value to range start_key.

*/

int SEL_ROOT::store_max_key(KEY_PART *key, uchar **range_key,

uint *range_key_flag, uint last_part,

bool start_key) {

SEL_ARG *key_tree = root->last();

uint res = key_tree->store_max_value(key[key_tree->part].store_length,

range_key, *range_key_flag);

// We've stored max value, so return max_flag

(*range_key_flag) |= key_tree->max_flag;

if (key_tree->next_key_part &&

key_tree->next_key_part->type == SEL_ROOT::Type::KEY_RANGE &&

key_tree->part != last_part &&

key_tree->next_key_part->root->part == key_tree->part + 1 &&

!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) {

const bool asc = key_tree->next_key_part->root->is_ascending;

if ((!start_key && asc) || (start_key && !asc))

res += key_tree->next_key_part->store_max_key(

key, range_key, range_key_flag, last_part, start_key);

else {

uint tmp_flag = invert_max_flag(*range_key_flag);

res += key_tree->next_key_part->store_min_key(key, range_key, &tmp_flag,

last_part, start_key);

*range_key_flag = invert_min_flag(tmp_flag);

}

}

return res;

}

void SEL_ROOT::free_tree() {

if (use_count == 0) {

for (SEL_ARG *pos = root->first(); pos; pos = pos->next) {

SEL_ROOT *root = pos->release_next_key_part();

if (root) root->free_tree();

}

}

}

/**

Helper function to compare two SEL_ROOTs.

*/

static bool all_same(const SEL_ROOT *sa1, const SEL_ROOT *sa2) {

if (sa1 == nullptr && sa2 == nullptr) return true;

if ((sa1 != nullptr && sa2 == nullptr) || (sa1 == nullptr && sa2 != nullptr))

return false;

if (sa1->type == SEL_ROOT::Type::KEY_RANGE &&

sa2->type == SEL_ROOT::Type::KEY_RANGE) {

const SEL_ARG *sa1_arg = sa1->root->first();

const SEL_ARG *sa2_arg = sa2->root->first();

for (; sa1_arg && sa2_arg && sa1_arg->is_same(sa2_arg);

sa1_arg = sa1_arg->next, sa2_arg = sa2_arg->next)

;

if (sa1_arg || sa2_arg) return false;

return true;

} else

return sa1->type == sa2->type;

}

SEL_TREE::SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param)

: keys(param->temp_mem_root, param->keys), n_ror_scans(0) {

keys_map = arg->keys_map;

type = arg->type;

for (uint idx = 0; idx < param->keys; idx++) {

if (arg->keys[idx]) {

set_key(idx, arg->keys[idx]->clone_tree(param));

if (!keys[idx]) break;

} else

set_key(idx, nullptr);

}

List_iterator<SEL_IMERGE> it(arg->merges);

for (SEL_IMERGE *el = it++; el; el = it++) {

SEL_IMERGE *merge = new (param->temp_mem_root) SEL_IMERGE(el, param);

if (!merge || merge->trees.empty() || param->has_errors()) {

merges.clear();

return;

}

merges.push_back(merge);

}

/*

SEL_TREEs are only created by get_mm_tree() (and functions called

by get_mm_tree()). Index intersection is checked after

get_mm_tree() has constructed all ranges. In other words, there

should not be any ROR scans to copy when this ctor is called.

*/

assert(n_ror_scans == 0);

}

/*

Perform AND operation on two index_merge lists and store result in *im1.

*/

inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2) {

im1->concat(im2);

}

/*

Perform OR operation on 2 index_merge lists, storing result in first list.

NOTES

The following conversion is implemented:

(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>

=> (a_1||b_1).

i.e. all conjuncts except the first one are currently dropped.

This is done to avoid producing N*K ways to do index_merge.

If (a_1||b_1) produce a condition that is always true, NULL is returned

and index_merge is discarded (while it is actually possible to try

harder).

As a consequence of this, choice of keys to do index_merge read may depend

on the order of conditions in WHERE part of the query.

RETURN

0 OK, result is stored in *im1

other Error, both passed lists are unusable

*/

static int imerge_list_or_list(RANGE_OPT_PARAM *param, bool remove_jump_scans,

List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2) {

SEL_IMERGE *imerge = im1->head();

im1->clear();

im1->push_back(imerge);

return imerge->or_sel_imerge_with_checks(param, remove_jump_scans,

im2->head());

}

/*

Perform OR operation on index_merge list and key tree.

RETURN

false OK, result is stored in *im1.

true Error

*/

static bool imerge_list_or_tree(RANGE_OPT_PARAM *param, bool remove_jump_scans,

List<SEL_IMERGE> *im1, SEL_TREE *tree) {

DBUG_TRACE;

SEL_IMERGE *imerge;

List_iterator<SEL_IMERGE> it(*im1);

uint remaining_trees = im1->elements;

while ((imerge = it++)) {

SEL_TREE *or_tree;

/*

Need to make a copy of 'tree' for all but the last OR operation

because or_sel_tree_with_checks() may change it.

*/

if (--remaining_trees == 0)

or_tree = tree;

else {

or_tree = new (param->temp_mem_root) SEL_TREE(tree, param);

if (!or_tree || param->has_errors()) return true;

if (or_tree->keys_map.is_clear_all() && or_tree->merges.is_empty())

return false;

}

int result_or =

imerge->or_sel_tree_with_checks(param, remove_jump_scans, or_tree);

if (result_or == 1)

it.remove();

else if (result_or == -1)

return true;

}

assert(remaining_trees == 0);

return im1->is_empty();

}

SEL_ARG::SEL_ARG(SEL_ARG &arg)

: min_flag(arg.min_flag),

max_flag(arg.max_flag),

maybe_flag(arg.maybe_flag),

part(arg.part),

rkey_func_flag(arg.rkey_func_flag),

field(arg.field),

min_value(arg.min_value),

max_value(arg.max_value),

left(null_element),

right(null_element),

next(nullptr),

prev(nullptr),

next_key_part(arg.next_key_part),

is_ascending(arg.is_ascending) {

if (next_key_part) ++next_key_part->use_count;

}

SEL_ARG::SEL_ARG(Field *f, const uchar *min_value_arg,

const uchar *max_value_arg, bool asc)

: part(0),

rkey_func_flag(HA_READ_INVALID),

field(f),

min_value(const_cast<uchar *>(min_value_arg)),

max_value(const_cast<uchar *>(max_value_arg)),

left(null_element),

right(null_element),

next(nullptr),

prev(nullptr),

parent(nullptr),

color(BLACK),

is_ascending(asc) {}

SEL_ARG::SEL_ARG(Field *field_, uint8 part_, uchar *min_value_,

uchar *max_value_, uint8 min_flag_, uint8 max_flag_,

bool maybe_flag_, bool asc, ha_rkey_function gis_flag)

: min_flag(min_flag_),

max_flag(max_flag_),

maybe_flag(maybe_flag_),

part(part_),

rkey_func_flag(gis_flag),

field(field_),

min_value(min_value_),

max_value(max_value_),

left(null_element),

right(null_element),

next(nullptr),

prev(nullptr),

parent(nullptr),

color(BLACK),

is_ascending(asc) {}

SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,

SEL_ARG **next_arg) {

SEL_ARG *tmp;

if (param->has_errors()) return nullptr;

if (!(tmp = new (param->temp_mem_root)

SEL_ARG(field, part, min_value, max_value, min_flag, max_flag,

maybe_flag, is_ascending,

min_flag & GEOM_FLAG ? rkey_func_flag : HA_READ_INVALID)))

return nullptr; // OOM

tmp->parent = new_parent;

tmp->set_next_key_part(next_key_part);

if (left == null_element || left == nullptr) {

tmp->left = left;

} else {

if (!(tmp->left = left->clone(param, tmp, next_arg)))

return nullptr; // OOM

}

tmp->prev = *next_arg; // Link into next/prev chain

(*next_arg)->next = tmp;

(*next_arg) = tmp;

if (right == null_element || right == nullptr) {

tmp->right = right;

} else {

if (!(tmp->right = right->clone(param, tmp, next_arg)))

return nullptr; // OOM

}

tmp->color = color;

return tmp;

}

/**

This gives the first SEL_ARG in the interval list, and the minimal element

in the red-black tree

@return

SEL_ARG first SEL_ARG in the interval list

*/

SEL_ARG *SEL_ARG::first() {

SEL_ARG *next_arg = this;

if (!next_arg->left) return nullptr; // MAYBE_KEY

while (next_arg->left != null_element) next_arg = next_arg->left;

return next_arg;

}

const SEL_ARG *SEL_ARG::first() const {

return const_cast<SEL_ARG *>(this)->first();

}

SEL_ARG *SEL_ARG::last() {

SEL_ARG *next_arg = this;

if (!next_arg->right) return nullptr; // MAYBE_KEY

while (next_arg->right != null_element) next_arg = next_arg->right;

return next_arg;

}

/*

Check if a compare is ok, when one takes ranges in account

Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2

*/

int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag, uint8 b_flag) {

int cmp;

/* First check if there was a compare to a min or max element */

if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) {

if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==

(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))

return 0;

return (a_flag & NO_MIN_RANGE) ? -1 : 1;

}

if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))

return (b_flag & NO_MIN_RANGE) ? 1 : -1;

if (field->is_nullable()) // If null is part of key

{

if (*a != *b) {

return *a ? -1 : 1;

}

if (*a) goto end; // NULL where equal

a++;

b++; // Skip NULL marker

}

cmp = field->key_cmp(a, b);

if (cmp) return cmp < 0 ? -1 : 1; // The values differed

// Check if the compared equal arguments was defined with open/closed range

end:

if (a_flag & (NEAR_MIN | NEAR_MAX)) {

if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))

return 0;

if (!(b_flag & (NEAR_MIN | NEAR_MAX))) return (a_flag & NEAR_MIN) ? 2 : -2;

return (a_flag & NEAR_MIN) ? 1 : -1;

}

if (b_flag & (NEAR_MIN | NEAR_MAX)) return (b_flag & NEAR_MIN) ? -2 : 2;

return 0; // The elements where equal

}

namespace {

size_t count_elements(const SEL_ARG *arg) {

size_t elements = 1;

assert(arg->left);

assert(arg->right);

if (arg->left && arg->left != null_element)

elements += count_elements(arg->left);

if (arg->right && arg->right != null_element)

elements += count_elements(arg->right);

return elements;

}

} // Namespace

SEL_ROOT::SEL_ROOT(SEL_ARG *root_arg)

: type(Type::KEY_RANGE),

root(root_arg),

elements(count_elements(root_arg)) {}

SEL_ROOT::SEL_ROOT(MEM_ROOT *mem_root, Type type_arg)

: type(type_arg), root(new(mem_root) SEL_ARG()), elements(1) {

assert(type_arg == Type::MAYBE_KEY || type_arg == Type::IMPOSSIBLE);

root->make_root();

if (type_arg == Type::MAYBE_KEY) {

// See todo for left/right pointers

root->left = root->right = nullptr;

}

}

SEL_ROOT *SEL_ROOT::clone_tree(RANGE_OPT_PARAM *param) const {

/*

Only SEL_ROOTs of type KEY_RANGE has any elements that need to be cloned.

For other types, just create a new SEL_ROOT object.

*/

if (type != Type::KEY_RANGE)

return new (param->temp_mem_root) SEL_ROOT(param->temp_mem_root, type);

SEL_ARG tmp_link, *next_arg, *new_root;

SEL_ROOT *new_tree;

next_arg = &tmp_link;

// Clone the underlying SEL_ARG tree, starting from the root node.

if (!(new_root = root->clone(param, (SEL_ARG *)nullptr, &next_arg)) ||

(param && param->has_errors()))

return nullptr;

// Make the SEL_ROOT itself.

if (!(new_tree = new (param->temp_mem_root) SEL_ROOT(new_root)))

return nullptr;

new_tree->elements = elements;

next_arg->next = nullptr; // Fix last link

tmp_link.next->prev = nullptr; // Fix first link

new_tree->use_count = 0;

return new_tree;

}

SEL_TREE *tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2) {

DBUG_TRACE;

if (param->has_errors()) return nullptr;

if (tree1 == nullptr) {

if (tree2 != nullptr) {

tree2->inexact = true;

}

return tree2;

}

if (tree2 == nullptr) {

if (tree1 != nullptr) {

tree1->inexact = true;

}

return tree1;

}

if (tree1->type == SEL_TREE::IMPOSSIBLE) {

return tree1;

}

if (tree2->type == SEL_TREE::IMPOSSIBLE) {

return tree2;

}

if (tree2->type == SEL_TREE::ALWAYS) {

tree1->inexact |= tree2->inexact;

return tree1;

}

if (tree1->type == SEL_TREE::ALWAYS) {

tree2->inexact |= tree1->inexact;

return tree2;

}

dbug_print_tree("tree1", tree1, param);

dbug_print_tree("tree2", tree2, param);

Key_map result_keys;

/* Join the trees key per key */

for (uint idx = 0; idx < param->keys; idx++) {

SEL_ROOT *key1 = tree1->release_key(idx);

SEL_ROOT *key2 = tree2->release_key(idx);

if (key1 != nullptr || key2 != nullptr) {

if (key1 == nullptr || key2 == nullptr) {

// If AND-ing two trees together, and one has an expression over a

// different index from the other, we cannot guarantee that the entire

// expression is exact if that index is chosen. (The only time this

// really matters is when there's an AND within an OR; only the

// hypergraph optimizer cares about the inexact flag, and it does its

// own splitting of top-level ANDs.)

tree1->inexact = true;

}

SEL_ROOT *new_key = key_and(param, key1, key2);

tree1->set_key(idx, new_key);

if (new_key) {

if (new_key->type == SEL_ROOT::Type::IMPOSSIBLE) {

tree1->type = SEL_TREE::IMPOSSIBLE;

return tree1;

}

result_keys.set_bit(idx);

#ifndef NDEBUG

/*

Do not test use_count if there is a large range tree created.

It takes too much time to traverse the tree.

*/

if (param->temp_mem_root->allocated_size() < 2097152)

new_key->test_use_count(new_key);

#endif

}

}

}

tree1->keys_map = result_keys;

tree1->inexact |= tree2->inexact;

/* ok, both trees are index_merge trees */

imerge_list_and_list(&tree1->merges, &tree2->merges);

return tree1;

}

/*

Check if two SEL_TREES can be combined into one (i.e. a single key range

read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without

using index_merge.

*/

bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,

RANGE_OPT_PARAM *param) {

Key_map common_keys = tree1->keys_map;

DBUG_TRACE;

common_keys.intersect(tree2->keys_map);

dbug_print_tree("tree1", tree1, param);

dbug_print_tree("tree2", tree2, param);

if (common_keys.is_clear_all()) return false;

/* trees have a common key, check if they refer to same key part */

for (uint key_no = 0; key_no < param->keys; key_no++) {

if (common_keys.is_set(key_no)) {

const SEL_ROOT *key1 = tree1->keys[key_no];

const SEL_ROOT *key2 = tree2->keys[key_no];

/* GIS_OPTIMIZER_FIXME: temp solution. key1 could be all nulls */

if (key1 && key2 && key1->root->part == key2->root->part) return true;

}

}

return false;

}

/*

Remove the trees that are not suitable for record retrieval.

SYNOPSIS

param Range analysis parameter

tree Tree to be processed, tree->type is KEY

DESCRIPTION

This function walks through tree->keys[] and removes the SEL_ARG* trees

that are not "maybe" trees (*) and cannot be used to construct quick range

selects.

(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of

these types here as well.

A SEL_ARG* tree cannot be used to construct quick select if it has

tree->part != 0. (e.g. it could represent "keypart2 < const").

WHY THIS FUNCTION IS NEEDED

Normally we allow construction of SEL_TREE objects that have SEL_ARG

trees that do not allow quick range select construction. For example for

" keypart1=1 AND keypart2=2 " the execution will proceed as follows:

tree1= SEL_TREE { SEL_ARG{keypart1=1} }

tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select

from this

call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG

tree.

There is an exception though: when we construct index_merge SEL_TREE,

any SEL_ARG* tree that cannot be used to construct quick range select can

be removed, because current range analysis code doesn't provide any way

that tree could be later combined with another tree.

Consider an example: we should not construct

st1 = SEL_TREE {

merges = SEL_IMERGE {

SEL_TREE(t.key1part1 = 1),

SEL_TREE(t.key2part2 = 2) -- (*)

}

};

because

- (*) cannot be used to construct quick range select,

- There is no execution path that would cause (*) to be converted to

a tree that could be used.

The latter is easy to verify: first, notice that the only way to convert

(*) into a usable tree is to call tree_and(something, (*)).

Second look at what tree_and/tree_or function would do when passed a

SEL_TREE that has the structure like st1 tree has, and conclude that

tree_and(something, (*)) will not be called.

RETURN

0 Ok, some suitable trees left

1 No tree->keys[] left.

*/

static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree) {

bool res = false;

for (uint i = 0; i < param->keys; i++) {

if (tree->keys[i]) {

if (tree->keys[i]->root->part) {

tree->keys[i] = NULL;

tree->keys_map.clear_bit(i);

} else

res = true;

}

}

return !res;

}

SEL_TREE *tree_or(RANGE_OPT_PARAM *param, bool remove_jump_scans,

SEL_TREE *tree1, SEL_TREE *tree2) {

DBUG_TRACE;

if (param->has_errors()) return nullptr;

if (!tree1 || !tree2) return nullptr;

tree1->inexact = tree2->inexact = tree1->inexact | tree2->inexact;

if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)

return tree2;

if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)

return tree1;

/*

It is possible that a tree contains both

a) simple range predicates (in tree->keys[]) and

b) index merge range predicates (in tree->merges)

If a tree has both, they represent equally *valid* range

predicate alternatives; both will return all relevant rows from

the table but one may return more unnecessary rows than the

other (additional rows will be filtered later). However, doing

an OR operation on trees with both types of predicates is too

complex at the time. We therefore remove the index merge

predicates (if we have both types) before OR'ing the trees.

TODO: enable tree_or() for trees with both simple and index

merge range predicates.

*/

if (!tree1->merges.is_empty()) {

for (uint i = 0; i < param->keys; i++)

if (tree1->keys[i] != NULL &&

tree1->keys[i]->type == SEL_ROOT::Type::KEY_RANGE) {

tree1->merges.clear();

break;

}

}

if (!tree2->merges.is_empty()) {

for (uint i = 0; i < param->keys; i++)

if (tree2->keys[i] != NULL &&

tree2->keys[i]->type == SEL_ROOT::Type::KEY_RANGE) {

tree2->merges.clear();

break;

}

}

SEL_TREE *result = nullptr;

Key_map result_keys;

if (sel_trees_can_be_ored(tree1, tree2, param)) {

/* Join the trees key per key */

for (uint idx = 0; idx < param->keys; idx++) {

SEL_ROOT *key1 = tree1->release_key(idx);

SEL_ROOT *key2 = tree2->release_key(idx);

SEL_ROOT *new_key = key_or(param, key1, key2);

tree1->set_key(idx, new_key);

if (new_key) {

result = tree1; // Added to tree1

result_keys.set_bit(idx);

#ifndef NDEBUG

/*

Do not test use count if there is a large range tree created.

It takes too much time to traverse the tree.

*/

if (param->temp_mem_root->allocated_size() < 2097152)

new_key->test_use_count(new_key);

#endif

}

}

if (result) result->keys_map = result_keys;

} else {

/* ok, two trees have KEY type but cannot be used without index merge */

if (tree1->merges.is_empty() && tree2->merges.is_empty()) {

if (remove_jump_scans) {

bool no_trees = remove_nonrange_trees(param, tree1);

no_trees = no_trees || remove_nonrange_trees(param, tree2);

if (no_trees)

return new (param->temp_mem_root)

SEL_TREE(SEL_TREE::ALWAYS, param->temp_mem_root, param->keys);

}

SEL_IMERGE *merge;

/* both trees are "range" trees, produce new index merge structure */

if (!(result = new (param->temp_mem_root)

SEL_TREE(param->temp_mem_root, param->keys)) ||

!(merge =

new (param->temp_mem_root) SEL_IMERGE(param->temp_mem_root)) ||

result->merges.push_back(merge) || merge->or_sel_tree(tree1) ||

merge->or_sel_tree(tree2))

result = nullptr;

else

result->type = tree1->type;

} else if (!tree1->merges.is_empty() && !tree2->merges.is_empty()) {

if (imerge_list_or_list(param, remove_jump_scans, &tree1->merges,

&tree2->merges))

result = new (param->temp_mem_root)

SEL_TREE(SEL_TREE::ALWAYS, param->temp_mem_root, param->keys);

else

result = tree1;

} else {

/* one tree is index merge tree and another is range tree */

if (tree1->merges.is_empty()) std::swap(tree1, tree2);

if (remove_jump_scans && remove_nonrange_trees(param, tree2))

return new (param->temp_mem_root)

SEL_TREE(SEL_TREE::ALWAYS, param->temp_mem_root, param->keys);

/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */

if (imerge_list_or_tree(param, remove_jump_scans, &tree1->merges, tree2))

result = new (param->temp_mem_root)

SEL_TREE(SEL_TREE::ALWAYS, param->temp_mem_root, param->keys);

else

result = tree1;

}

}

return result;

}

/**

And key trees where key1->part < key2->part

key2 will be connected to every key in key1, and thus

have its use_count incremented many times. The returned node

will not have its use_count increased; you are supposed to do

that yourself when you connect it to a root.

@param param Range analysis context (needed to track if we have allocated

too many SEL_ARGs)

@param key1 Root of first tree to AND together

@param key2 Root of second tree to AND together

@return Root of (key1 AND key2)

*/

static SEL_ROOT *and_all_keys(RANGE_OPT_PARAM *param, SEL_ROOT *key1,

SEL_ROOT *key2) {

SEL_ARG *next;

// We will be modifying key1, so clone it if we need to.

if (key1->use_count > 0) {

if (!(key1 = key1->clone_tree(param))) return nullptr; // OOM

}

/*

We will be using key2 several times, so temporarily increase

its use_count artificially to keep key_and() below from modifying

it in-place.

Note that this makes test_use_count() fail since our use_count is

now higher than the actual number of references, but that is only ever

called from tree_and() and tree_or(), not from anything below this,

and we undo it below.

*/

++key2->use_count;

if (key1->type == SEL_ROOT::Type::MAYBE_KEY) {

// See todo for left/right pointers

assert(!key1->root->left);

assert(!key1->root->right);

key1->root->next = key1->root->prev = nullptr;

}

for (next = key1->root->first(); next; next = next->next) {

if (next->next_key_part) {

/*

The more complicated case; there's already another AND clause,

so we cannot connect key2 to key1 directly, but need to recurse.

*/

SEL_ROOT *tmp = key_and(param, next->release_next_key_part(), key2);

next->set_next_key_part(tmp);

if (tmp && tmp->type == SEL_ROOT::Type::IMPOSSIBLE) {

key1->tree_delete(next);

}

} else {

// The trivial case.

next->set_next_key_part(key2);

}

}

// Undo the temporary use_count modification above.

--key2->use_count;

return key1;

}

/*

Produce a SEL_ARG graph that represents "key1 AND key2"

SYNOPSIS

key_and()

param Range analysis context (needed to track if we have allocated

too many SEL_ARGs)

key1 First argument, root of its RB-tree

key2 Second argument, root of its RB-tree

key_and() does not modify key1 nor key2 if they are in use by other roots

(although typical use is that key1 has been disconnected from its root

and thus can be modified in-place). Thus, it does not change their use_count

in the typical case.

The returned node will not have its use_count increased; you are supposed

to do that yourself when you connect it to a root.

RETURN

RB-tree root of the resulting SEL_ARG graph.

NULL if the result of AND operation is an empty interval {0}.

*/

SEL_ROOT *key_and(RANGE_OPT_PARAM *param, SEL_ROOT *key1, SEL_ROOT *key2) {

if (param->has_errors()) return nullptr;

if (key1 == nullptr || key1->is_always()) {

if (key1) key1->free_tree();

return key2;

}

if (key2 == nullptr || key2->is_always()) {

if (key2) key2->free_tree();

return key1;

}

if (key1->root->part != key2->root->part) {

if (key1->root->part > key2->root->part) {

std::swap(key1, key2);

}

assert(key1->root->part < key2->root->part);

return and_all_keys(param, key1, key2);

}

if ((!key2->simple_key() && key1->simple_key() &&

key2->type != SEL_ROOT::Type::MAYBE_KEY) ||

key1->type == SEL_ROOT::Type::MAYBE_KEY) { // Put simple key in key2

std::swap(key1, key2);

}

/* If one of the key is MAYBE_KEY then the found region may be smaller */

if (key2->type == SEL_ROOT::Type::MAYBE_KEY) {

if (key1->use_count > 0) {

// We are going to modify key1, so we need to clone it.

if (!(key1 = key1->clone_tree(param))) return nullptr; // OOM

}

if (key1->type == SEL_ROOT::Type::MAYBE_KEY) { // Both are maybe key

SEL_ROOT *new_part = key_and(param, key1->root->release_next_key_part(),

key2->root->next_key_part);

key1->root->set_next_key_part(new_part);

return key1;

} else {

key1->root->maybe_smaller();

if (key2->root->next_key_part) {

return and_all_keys(param, key1, key2);

} else {

/*

key2 is MAYBE_KEY and nothing more; simply discard it,

since we've now moved that information into key1's maybe_flag.

*/

key2->free_tree();

return key1;

}

}

// Unreachable.

assert(false);

return nullptr;

}

if ((key1->root->min_flag | key2->root->min_flag) & GEOM_FLAG) {

/*

Cannot optimize geometry ranges. The next best thing is to keep

one of them.

*/

key2->free_tree();

return key1;

}

// Two non-overlapped key ranges for multi-valued index do not mean

// an always false condition.

// For example, "1 member of(f) AND 2 member of(f)" for f=[1, 2].

if (key1->root->field->is_array() || key2->root->field->is_array()) {

return and_all_keys(param, key1, key2);

}

SEL_ARG *e1 = key1->root->first(), *e2 = key2->root->first();

SEL_ROOT *new_tree = nullptr;

while (e1 && e2) {

int cmp = e1->cmp_min_to_min(e2);

if (cmp < 0) {

if (get_range(&e1, &e2, key1)) continue;

} else if (get_range(&e2, &e1, key2))

continue;

/*

NOTE: We don't destroy e1->next_key_part nor e2->next_key_part

(if used at all, the return value here goes into a brand new element;

it does not overwrite either of them), so we keep their use_counts

intact here.

*/

SEL_ROOT *next = key_and(param, e1->next_key_part, e2->next_key_part);

if (next && next->type == SEL_ROOT::Type::IMPOSSIBLE)

next->free_tree();

else {

SEL_ARG *new_arg = e1->clone_and(e2, param->temp_mem_root);

if (!new_arg) return nullptr; // End of memory

new_arg->set_next_key_part(next);

if (!new_tree) {

new_tree = new (param->temp_mem_root) SEL_ROOT(new_arg);

} else

new_tree->insert(new_arg);

}

if (e1->cmp_max_to_max(e2) < 0)

e1 = e1->next; // e1 can't overlap next e2

else

e2 = e2->next;

}

key1->free_tree();

key2->free_tree();

if (!new_tree)

// Impossible range

return new (param->temp_mem_root)

SEL_ROOT(param->temp_mem_root, SEL_ROOT::Type::IMPOSSIBLE);

return new_tree;

}

static bool get_range(SEL_ARG **e1, SEL_ARG **e2, const SEL_ROOT *root1) {

(*e1) = root1->find_range(*e2); // first e1->min < e2->min

if ((*e1)->cmp_max_to_min(*e2) < 0) {

if (!((*e1) = (*e1)->next)) return true;

if ((*e1)->cmp_min_to_max(*e2) > 0) {

(*e2) = (*e2)->next;