/**

* Copyright (c) 2021 OceanBase

* OceanBase CE is licensed under Mulan PubL v2.

* You can use this software according to the terms and conditions of the Mulan PubL v2.

* You may obtain a copy of Mulan PubL v2 at:

* http://license.coscl.org.cn/MulanPubL-2.0

* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,

* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,

* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.

* See the Mulan PubL v2 for more details.

*/

#define USING_LOG_PREFIX SQL_REWRITE

#include "lib/timezone/ob_time_convert.h"

#include "lib/container/ob_array_serialization.h"

#include "lib/geo/ob_geo_utils.h"

#include "lib/rc/ob_rc.h"

#include "sql/resolver/dml/ob_dml_stmt.h"

#include "sql/rewrite/ob_query_range.h"

#include "sql/engine/expr/ob_expr_result_type_util.h"

#include "sql/engine/expr/ob_expr_like.h"

#include "common/ob_smart_call.h"

#include "sql/optimizer/ob_optimizer_util.h"

#include "observer/omt/ob_tenant_srs.h"

#include "sql/engine/expr/ob_geo_expr_utils.h"

//if cnd is true get full range key part which is always true

//else, get empty key part which is always false

#define GET_ALWAYS_TRUE_OR_FALSE(cnd, out_key_part) \

do { \

if (OB_SUCC(ret)) { \

query_range_ctx_->cur_expr_is_precise_ = false; \

if (OB_ISNULL(table_graph_.key_part_head_)) { \

ret = OB_ERR_NULL_VALUE; \

LOG_WARN("Can not find key_part"); \

} else if (cnd) { \

if (OB_FAIL(alloc_full_key_part(out_key_part))) { \

LOG_WARN("alloc_full_key_part failed", K(ret)); \

} else { \

out_key_part->id_ = table_graph_.key_part_head_->id_; \

out_key_part->pos_ = table_graph_.key_part_head_->pos_; \

} \

} else { \

if (OB_FAIL(alloc_empty_key_part(out_key_part))) { \

LOG_WARN("alloc_empty_key_part failed", K(ret)); \

} else if (OB_ISNULL(out_key_part)) { \

ret = OB_ALLOCATE_MEMORY_FAILED; \

LOG_ERROR("out_key_part is null.", K(ret)); \

} else { \

out_key_part->id_ = table_graph_.key_part_head_->id_; \

out_key_part->pos_ = table_graph_.key_part_head_->pos_; \

} \

} \

} \

} while(0)

namespace oceanbase

{

using namespace common;

using namespace share::schema;

namespace sql

{

ObQueryRange::ObQueryRange()

: state_(NEED_INIT),

range_size_(0),

column_count_(0),

contain_row_(false),

contain_in_(false),

contain_geo_filters_(false),

inner_allocator_(ObModIds::OB_SQL_QUERY_RANGE),

allocator_(inner_allocator_),

bucket_allocator_wrapper_(allocator_),

map_alloc_(OB_MALLOC_NORMAL_BLOCK_SIZE, bucket_allocator_wrapper_),

query_range_ctx_(NULL),

key_part_store_(allocator_),

range_exprs_(allocator_),

ss_range_exprs_(allocator_),

mbr_filters_(allocator_),

has_exec_param_(false),

is_equal_and_(false),

equal_offs_(allocator_),

expr_final_infos_(allocator_),

mem_used_(allocator_.used()),

is_reach_mem_limit_(false)

{

}

ObQueryRange::ObQueryRange(ObIAllocator &alloc)

: state_(NEED_INIT),

range_size_(0),

column_count_(0),

contain_row_(false),

contain_in_(false),

contain_geo_filters_(false),

inner_allocator_(ObModIds::OB_SQL_QUERY_RANGE),

allocator_(alloc),

bucket_allocator_wrapper_(allocator_),

map_alloc_(OB_MALLOC_NORMAL_BLOCK_SIZE, bucket_allocator_wrapper_),

query_range_ctx_(NULL),

key_part_store_(allocator_),

range_exprs_(allocator_),

ss_range_exprs_(allocator_),

mbr_filters_(allocator_),

has_exec_param_(false),

is_equal_and_(false),

equal_offs_(allocator_),

expr_final_infos_(allocator_),

mem_used_(allocator_.used()),

is_reach_mem_limit_(false)

{

}

ObQueryRange::~ObQueryRange()

{

reset();

}

ObQueryRange &ObQueryRange::operator=(const ObQueryRange &other)

{

if (this != &other) {

reset();

deep_copy(other);

}

return *this;

}

void ObQueryRange::reset()

{

DLIST_FOREACH_NORET(node, key_part_store_.get_obj_list()) {

if (node != NULL && node->get_obj() != NULL) {

node->get_obj()->~ObKeyPart();

}

}

key_part_store_.destroy();

query_range_ctx_ = NULL;

state_ = NEED_INIT;

range_size_ = 0;

column_count_ = 0;

contain_row_ = false;

contain_in_ = false;

mbr_filters_.reset(),

contain_geo_filters_ = false;

table_graph_.reset();

range_exprs_.reset();

ss_range_exprs_.reset();

inner_allocator_.reset();

has_exec_param_ = false;

is_equal_and_ = false;

equal_offs_.reset();

expr_final_infos_.reset();

columnId_map_.destroy();

is_reach_mem_limit_ = false;

mem_used_ = 0;

}

int ObQueryRange::init_query_range_ctx(ObIAllocator &allocator,

const ColumnIArray &range_columns,

ObExecContext *exec_ctx,

ExprConstrantArray *expr_constraints,

const ParamsIArray *params,

const bool phy_rowid_for_table_loc,

const bool ignore_calc_failure,

const bool use_in_optimization)

{

int ret = OB_SUCCESS;

void *ptr = NULL;

uint64_t table_id = OB_INVALID_ID;

if (OB_UNLIKELY(range_columns.count() <= 0)) {

ret = OB_INVALID_ARGUMENT;

LOG_WARN("range column array is empty", K(ret));

} else if (OB_ISNULL(ptr = allocator.alloc(sizeof(ObQueryRangeCtx)))) {

ret = OB_ALLOCATE_MEMORY_FAILED;

LOG_ERROR("alloc query range context failed", K(ret));

} else if (OB_ISNULL(exec_ctx) || OB_ISNULL(exec_ctx->get_my_session())) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret), K(exec_ctx));

} else {

query_range_ctx_ = new(ptr) ObQueryRangeCtx(exec_ctx, expr_constraints, params);

query_range_ctx_->phy_rowid_for_table_loc_ = phy_rowid_for_table_loc;

query_range_ctx_->ignore_calc_failure_ = ignore_calc_failure;

query_range_ctx_->range_optimizer_max_mem_size_ = exec_ctx->get_my_session()->get_range_optimizer_max_mem_size();

query_range_ctx_->use_in_optimization_ = use_in_optimization;

}

for (int64_t i = 0; OB_SUCC(ret) && i < range_columns.count(); ++i) {

const ColumnItem &col = range_columns.at(i);

if (OB_UNLIKELY(col.is_invalid())) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get invalid table id", K(ret), K(table_id), K(range_columns.at(0).expr_));

} else {

ObKeyPartId key_part_id(col.table_id_, col.column_id_);

const ObExprResType *expr_res_type = col.get_column_type();

void *ptr = NULL;

if (OB_ISNULL(expr_res_type)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("expr result type is null", K(ret));

} else if (OB_ISNULL(ptr = allocator.alloc(sizeof(ObKeyPartPos)))) {

ret = OB_ALLOCATE_MEMORY_FAILED;

LOG_WARN("failed to allocate memory for ObKeyPartPos", K(ret));

} else {

ObExprResType tmp_expr_type = *expr_res_type;

if (tmp_expr_type.is_lob_locator()) {

tmp_expr_type.set_type(ObLongTextType);

}

table_id = (i > 0 ? table_id : col.table_id_);

ObKeyPartPos *key_part_pos = new(ptr) ObKeyPartPos(i, tmp_expr_type);

if (OB_UNLIKELY(table_id != col.table_id_)) { // table_id of range columns must be same

ret = OB_INVALID_ARGUMENT;

LOG_WARN("range columns must have the same table id", K(table_id), K_(col.table_id));

} else if (OB_FAIL(key_part_pos->set_enum_set_values(allocator_, col.expr_->get_enum_set_values()))) {

LOG_WARN("fail to set values", K(ret), K(key_part_pos));

} else if (OB_FAIL(query_range_ctx_->key_part_map_.set_refactored(key_part_id, key_part_pos))) {

LOG_WARN("set key part map failed", K(ret), K(key_part_id));

} else if (OB_FAIL(query_range_ctx_->key_part_pos_array_.push_back(key_part_pos))) {

LOG_WARN("failed to push back key part pos", K(ret));

}

}

}

}

if (OB_SUCC(ret)) {

// Add the default range of the index and remember the count of the rowkeys.

// Just to handle the full range case

// E.g.

// select * from t where true;

ObKeyPart *full_key_part = NULL;

if (OB_FAIL(alloc_full_key_part(full_key_part))) {

LOG_WARN("alloc_full_key_part failed", K(ret));

} else if (OB_ISNULL(full_key_part)) {

ret = OB_ALLOCATE_MEMORY_FAILED;

LOG_ERROR("full_key_part is null.", K(ret));

} else {

ObExprResType col_type(allocator_);

full_key_part->id_ = ObKeyPartId(table_id, OB_INVALID_ID);

full_key_part->pos_.column_type_ = col_type;

table_graph_.key_part_head_ = full_key_part;

column_count_ = range_columns.count();

}

}

if (OB_SUCCESS != ret && NULL != query_range_ctx_) {

destroy_query_range_ctx(allocator);

}

return ret;

}

void ObQueryRange::destroy_query_range_ctx(ObIAllocator &ctx_allocator)

{

if (NULL != query_range_ctx_) {

for (int64_t i = 0; i < query_range_ctx_->key_part_pos_array_.count(); ++i) {

if (NULL != query_range_ctx_->key_part_pos_array_.at(i)) {

query_range_ctx_->key_part_pos_array_.at(i)->~ObKeyPartPos();

ctx_allocator.free(query_range_ctx_->key_part_pos_array_.at(i));

}

}

query_range_ctx_->~ObQueryRangeCtx();

ctx_allocator.free(query_range_ctx_);

query_range_ctx_ = NULL;

}

}

int ObQueryRange::preliminary_extract_query_range(const ColumnIArray &range_columns,

const ObRawExpr *expr_root,

const ObDataTypeCastParams &dtc_params,

ObExecContext *exec_ctx,

ExprConstrantArray *expr_constraints /* = NULL */,

const ParamsIArray *params /* = NULL */,

const bool use_in_optimization /* = false */)

{

int ret = OB_SUCCESS;

ObArenaAllocator ctx_allocator(ObModIds::OB_QUERY_RANGE_CTX);

if (OB_FAIL(init_query_range_ctx(ctx_allocator, range_columns, exec_ctx, expr_constraints, params,

false, true, use_in_optimization))) {

LOG_WARN("init query range context failed", K(ret));

} else if (OB_ISNULL(query_range_ctx_)) {

ret = OB_NOT_INIT;

LOG_WARN("query_range_ctx_ is not inited.", K(ret));

} else {

query_range_ctx_->need_final_extract_ = false;

query_range_ctx_->only_one_expr_ = true;

ObKeyPart *root = NULL;

if (OB_UNLIKELY(NULL == expr_root)) {

//(MIN, MAX), whole range

GET_ALWAYS_TRUE_OR_FALSE(true, root);

} else {

if (OB_FAIL(preliminary_extract(expr_root, root, dtc_params, T_OP_IN == expr_root->get_expr_type()))) {

LOG_WARN("gen table range failed", K(ret));

} else if (query_range_ctx_->cur_expr_is_precise_ && root != NULL) {

// for simple in_expr

int64_t max_pos = -1;

int64_t cur_pos = 0;

bool is_strict_equal = true;

if (OB_FAIL(is_strict_equal_graph(root, cur_pos, max_pos, is_strict_equal))) {

LOG_WARN("is strict equal graph failed", K(ret));

} else if (is_strict_equal) {

ObRangeExprItem expr_item;

expr_item.cur_expr_ = expr_root;

for (const ObKeyPart *cur_and = root; OB_SUCC(ret) && cur_and != NULL; cur_and = cur_and->and_next_) {

if (OB_FAIL(add_expr_offsets(expr_item.cur_pos_, cur_and))) {

LOG_WARN("failed to add expr pos", K(ret));

}

}

if (OB_SUCC(ret) && OB_FAIL(query_range_ctx_->precise_range_exprs_.push_back(expr_item))) {

LOG_WARN("store precise range exprs failed", K(ret));

}

} else if (NULL == root->and_next_ && is_general_graph(*root)) {

//因为optimizer去filter只能够在顶端去，而且去filter的目标是合取范式

//标准的合取范式例如(c1>1 or c1<0) and c2=1这样的表达式在resolver必须拆分成多个表达式

//如果没有拆分，这样的表达式也不能被去掉，因为去表达式每次都是一个完整的表达式

//这个表达式包含了多个键，要么全部去掉，要么都不去掉，显然全部去掉是不对的

ObRangeExprItem expr_item;

expr_item.cur_expr_ = expr_root;

if (OB_FAIL(add_expr_offsets(expr_item.cur_pos_, root))) {

LOG_WARN("failed to add expr pos", K(ret));

} else if (OB_FAIL(query_range_ctx_->precise_range_exprs_.push_back(expr_item))) {

LOG_WARN("store precise range exprs failed", K(ret));

}

}

}

}

if (OB_SUCC(ret) && NULL != root) {

ObSqlBitSet<> key_offsets;

if (OB_FAIL(refine_large_range_graph(root, use_in_optimization))) {

LOG_WARN("failed to refine large range graph", K(ret));

} else if (OB_FAIL(check_graph_type(*root))) {

LOG_WARN("check graph type failed", K(ret));

} else if (OB_FAIL(generate_expr_final_info())) {

LOG_WARN("failed to generate final exprs", K(ret));

}

}

}

if (OB_SUCC(ret)) {

if (query_range_ctx_->need_final_extract_) {

state_ = NEED_PREPARE_PARAMS;

} else {

state_ = CAN_READ;

}

}

destroy_query_range_ctx(ctx_allocator);

return ret;

}

int ObQueryRange::extract_valid_exprs(const ExprIArray &root_exprs, ObIArray<ObRawExpr *> &candi_exprs)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(query_range_ctx_)) {

ret = OB_NOT_INIT;

LOG_WARN("query range not inited", K(ret));

} else {

ObSEArray<int64_t, 16> offsets;

for (int64_t i = 0; OB_SUCC(ret) && i < root_exprs.count(); ++i) {

bool is_valid_expr = false;

bool tmp_need_extract_const = false;

if (OB_FAIL(check_cur_expr(root_exprs.at(i), offsets,

tmp_need_extract_const, is_valid_expr))) {

LOG_WARN("failed to check current expr", K(ret));

} else if (tmp_need_extract_const || is_valid_expr) {

if (OB_FAIL(candi_exprs.push_back(root_exprs.at(i)))) {

LOG_WARN("failed to push back candidate exprs", K(ret));

}

}

}

if (OB_SUCC(ret)) {

if (offsets.count() != 0 || !query_range_ctx_->row_in_offsets_.empty()) {

ObSEArray<int64_t, 4> common_offsets;

if (OB_FAIL(ObOptimizerUtil::intersect(query_range_ctx_->row_in_offsets_, offsets, common_offsets))) {

LOG_WARN("failed to intersect common offsets", K(ret));

} else if (!common_offsets.empty()) {

// (c1,c2) in () and c1 .. is not allowed to use in optimization

query_range_ctx_->use_in_optimization_ = false;

}

if (OB_FAIL(ret)) {

} else if (OB_FAIL(append_array_no_dup(offsets, query_range_ctx_->row_in_offsets_))) {

LOG_WARN("failed to append array no dup", K(ret));

} else {

int64_t postfix_offset = -1;

std::sort(offsets.begin(), offsets.end());

int64_t idx = 0;

for (; idx < offsets.count(); ++idx) {

if (postfix_offset != -1) {

if (offsets.at(idx) != postfix_offset + 1) {

break;

} else {

postfix_offset = offsets.at(idx);

query_range_ctx_->max_valid_offset_ = postfix_offset;

}

} else if (idx != offsets.at(idx)) {

postfix_offset = offsets.at(idx);

query_range_ctx_->max_valid_offset_ = postfix_offset;

} else {

query_range_ctx_->max_valid_offset_ = idx;

}

}

}

}

LOG_TRACE("succeed to check need extract range",

K(candi_exprs), K(offsets), K(query_range_ctx_->row_in_offsets_), K(query_range_ctx_->max_valid_offset_));

}

}

return ret;

}

int ObQueryRange::check_cur_expr(const ObRawExpr *cur_expr, ObIArray<int64_t> &offsets,

bool &need_extract_const, bool &is_valid_expr)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(cur_expr)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else if (cur_expr->is_const_expr()) {

need_extract_const = true;

} else {

const ObOpRawExpr *op_expr = static_cast<const ObOpRawExpr *>(cur_expr);

ObItemType cmp_type = cur_expr->get_expr_type();

if (T_OP_OR == cmp_type || T_OP_AND == cmp_type) {

for (int64_t i = 0; OB_SUCC(ret) && i < op_expr->get_param_count(); ++i) {

if (OB_ISNULL(op_expr->get_param_expr(i))) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else if (OB_FAIL(check_cur_expr(op_expr->get_param_expr(i), offsets,

need_extract_const, is_valid_expr))) {

LOG_WARN("failed to check and or", K(ret));

}

}

} else if (cur_expr->is_spatial_expr()) {

is_valid_expr = true;

} else if (IS_BASIC_CMP_OP(cmp_type) || T_OP_NE == cmp_type ||

T_OP_IS == cmp_type || T_OP_IN == cmp_type || T_OP_NOT_IN == cmp_type) {

const ObRawExpr *l_expr = op_expr->get_param_expr(0);

const ObRawExpr *r_expr = op_expr->get_param_expr(1);

if (OB_ISNULL(l_expr) || OB_ISNULL(r_expr)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret), K(l_expr), K(r_expr));

} else if ((T_OP_LIKE == cmp_type) &&

(OB_UNLIKELY(3 != op_expr->get_param_count()) || OB_ISNULL(op_expr->get_param_expr(2)))) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get invalid arguments", K(ret), K(cmp_type), K(*op_expr));

} else if (T_OP_ROW == l_expr->get_expr_type()) {

if (OB_FAIL(extract_row_info(l_expr, r_expr,

cmp_type, offsets,

need_extract_const,

is_valid_expr))) {

LOG_WARN("failed to extract row info", K(ret));

}

} else {

if (OB_FAIL(extract_basic_info(l_expr, r_expr,

cmp_type, offsets,

need_extract_const,

is_valid_expr))) {

LOG_WARN("failed to extract basic info", K(ret));

}

}

} else if (T_OP_BTW == cmp_type || T_OP_NOT_BTW == cmp_type) {

if (OB_UNLIKELY(3 != op_expr->get_param_count())) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get invalid argument", K(ret));

} else {

for (int64_t i = 0; OB_SUCC(ret) && i < op_expr->get_param_count(); ++i) {

const ObRawExpr *param = op_expr->get_param_expr(i);

if (OB_ISNULL(param)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else if (OB_FAIL(ObOptimizerUtil::get_expr_without_lossless_cast(param, param))) {

LOG_WARN("failed to get expr without lossless cast", K(ret));

} else if (param->is_column_ref_expr()) {

const ObColumnRefRawExpr *col_expr = static_cast<const ObColumnRefRawExpr *>(param);

ObKeyPartId id(col_expr->get_table_id(), col_expr->get_column_id());

ObKeyPartPos *pos = nullptr;

bool b_key_part;

if (OB_FAIL(is_key_part(id, pos, b_key_part))) {

LOG_WARN("failed to get key part", K(ret));

} else if (b_key_part) {

is_valid_expr = true;

if (OB_ISNULL(pos)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get null key pos");

} else if (OB_FAIL(add_var_to_array_no_dup(offsets, pos->offset_))) {

LOG_WARN("failed to add var to array no dup");

}

}

}

}

}

}

}

return ret;

}

int ObQueryRange::extract_basic_info(const ObRawExpr *l_expr,

const ObRawExpr *r_expr,

const ObItemType &cmp_type,

ObIArray<int64_t> &offsets,

bool &need_extract_const,

bool &is_valid_expr)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(l_expr) || OB_ISNULL(r_expr)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret), K(l_expr), K(r_expr));

} else if (OB_FAIL(ObOptimizerUtil::get_expr_without_lossless_cast(l_expr, l_expr))) {

LOG_WARN("failed to get expr without lossless cast", K(ret));

} else if (OB_FAIL(ObOptimizerUtil::get_expr_without_lossless_cast(r_expr, r_expr))) {

LOG_WARN("failed to get expr without lossless cast", K(ret));

} else if (l_expr->is_const_expr() && r_expr->is_const_expr()) {

need_extract_const = true;

} else if (l_expr->has_flag(IS_COLUMN) && r_expr->has_flag(IS_COLUMN)) {

// always true

} else if (T_OP_IN == cmp_type || T_OP_NOT_IN == cmp_type) {

if (l_expr->is_column_ref_expr()) {

const ObColumnRefRawExpr *col_expr = static_cast<const ObColumnRefRawExpr *>(l_expr);

ObKeyPartId key_part_id(col_expr->get_table_id(), col_expr->get_column_id());

ObKeyPartPos *key_part_pos = nullptr;

bool b_key_part = false;

if (OB_FAIL(is_key_part(key_part_id, key_part_pos, b_key_part))) {

LOG_WARN("failed to get key part", K(ret));

} else if (!b_key_part) {

// do nothing

} else if (OB_ISNULL(key_part_pos)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get null key part pos");

} else if (OB_FAIL(add_var_to_array_no_dup(offsets, key_part_pos->offset_))) {

LOG_WARN("failed to add key part offset", K(ret));

} else {

is_valid_expr = true;

}

} else if (l_expr->has_flag(IS_ROWID)) {

ObSEArray<const ObColumnRefRawExpr *, 4> pk_column_items;

bool is_physical_rowid = false;

uint64_t part_column_id = common::OB_INVALID_ID;

uint64_t table_id = common::OB_INVALID_ID;

if (OB_FAIL(get_extract_rowid_range_infos(l_expr,

pk_column_items,

is_physical_rowid,

table_id,

part_column_id))) {

LOG_WARN("failed to get extract rowid range infos");

} else if (OB_FAIL(check_can_extract_rowid(pk_column_items,

is_physical_rowid,

table_id,

part_column_id,

offsets,

is_valid_expr))) {

LOG_WARN("failed to check can extract rowid range", K(ret));

}

}

} else if ((l_expr->has_flag(IS_COLUMN) && r_expr->is_const_expr())

|| (l_expr->is_const_expr() && r_expr->has_flag(IS_COLUMN))) {

const ObColumnRefRawExpr *col_expr = NULL;

const ObRawExpr *const_expr = NULL;

bool b_is_key_part = false;

if (l_expr->has_flag(IS_COLUMN)) {

col_expr = static_cast<const ObColumnRefRawExpr *>(l_expr);

const_expr = r_expr;

} else if (r_expr->has_flag(IS_COLUMN)) {

col_expr = static_cast<const ObColumnRefRawExpr *>(r_expr);

const_expr = l_expr;

}

ObKeyPartId key_part_id(col_expr->get_table_id(), col_expr->get_column_id());

ObKeyPartPos *key_part_pos = nullptr;

if (OB_FAIL(is_key_part(key_part_id, key_part_pos, b_is_key_part))) {

LOG_WARN("failed to check is key part", K(ret));

} else if (!b_is_key_part || OB_UNLIKELY(!const_expr->is_const_expr())) {

// always true

} else if (OB_ISNULL(key_part_pos)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get null key part pos");

} else if (OB_FAIL(add_var_to_array_no_dup(offsets, key_part_pos->offset_))) {

LOG_WARN("failed to add key part offset", K(ret));

} else {

is_valid_expr = true;

}

} else if (((l_expr->has_flag(IS_ROWID) && r_expr->is_const_expr())

|| (r_expr->has_flag(IS_ROWID) && l_expr->is_const_expr())) && T_OP_LIKE != cmp_type) {

ObSEArray<const ObColumnRefRawExpr *, 4> pk_column_items;

bool is_physical_rowid = false;

uint64_t part_column_id = common::OB_INVALID_ID;

uint64_t table_id = common::OB_INVALID_ID;

const ObRawExpr *calc_urowid_expr = NULL;

if (OB_UNLIKELY(r_expr->has_flag(IS_ROWID))) {

calc_urowid_expr = r_expr;

} else if (l_expr->has_flag(IS_ROWID)) {

calc_urowid_expr = l_expr;

}

if (OB_FAIL(get_extract_rowid_range_infos(calc_urowid_expr,

pk_column_items,

is_physical_rowid,

table_id,

part_column_id))) {

LOG_WARN("failed to get extract rowid range infos");

} else if (OB_FAIL(check_can_extract_rowid(pk_column_items,

is_physical_rowid,

table_id,

part_column_id,

offsets,

is_valid_expr))) {

LOG_WARN("failed to check can extract rowid range", K(ret));

}

}

return ret;

}

int ObQueryRange::check_can_extract_rowid(const ObIArray<const ObColumnRefRawExpr *> &pk_column_items,

const bool is_physical_rowid,

const uint64_t table_id,

const uint64_t part_column_id,

ObIArray<int64_t> &offsets,

bool &is_valid_expr)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(query_range_ctx_)) {

ret = OB_NOT_INIT;

LOG_WARN("get invalid query range ctx", K(ret));

} else {

for (int64_t i = 0; OB_SUCC(ret) && i < pk_column_items.count(); ++i) {

const ObColumnRefRawExpr *col_expr = pk_column_items.at(i);

bool b_key_part = false;

bool cur_valid = false;

if (OB_ISNULL(col_expr)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else {

ObKeyPartId key_part_id(col_expr->get_table_id(), col_expr->get_column_id());

ObKeyPartPos *key_part_pos = nullptr;

if (OB_FAIL(is_key_part(key_part_id, key_part_pos, b_key_part))) {

LOG_WARN("failed to get key part", K(ret));

} else if (b_key_part) {

cur_valid = true;

} else if (is_physical_rowid &&

query_range_ctx_->phy_rowid_for_table_loc_ &&

part_column_id != common::OB_INVALID_ID) {

key_part_id.table_id_ = table_id;

key_part_id.column_id_ = part_column_id;

if (OB_FAIL(is_key_part(key_part_id, key_part_pos, b_key_part))) {

LOG_WARN("failed to get key part", K(ret));

} else {

cur_valid = b_key_part;

}

}

if (OB_SUCC(ret) && cur_valid) {

is_valid_expr = true;

if (OB_ISNULL(key_part_pos)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get null key part pos");

} else if (OB_FAIL(add_var_to_array_no_dup(offsets, key_part_pos->offset_))) {

LOG_WARN("failed to add var to array no dup", K(ret));

}

}

}

}

}

return ret;

}

int ObQueryRange::extract_row_info(const ObRawExpr *l_expr,

const ObRawExpr *r_expr,

const ObItemType &cmp_type,

ObIArray<int64_t> &offsets,

bool &need_extract_const,

bool &is_valid_expr)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(l_expr) || OB_ISNULL(r_expr) || OB_ISNULL(query_range_ctx_)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret), K(l_expr), K(r_expr), K(query_range_ctx_));

} else if (lib::is_oracle_mode()) {

if (T_OP_ROW == r_expr->get_expr_type() &&

1 == r_expr->get_param_count() &&

T_OP_ROW == r_expr->get_param_expr(0)->get_expr_type()) {

r_expr = r_expr->get_param_expr(0);

}

}

if (OB_SUCC(ret)) {

const ObOpRawExpr *l_row = static_cast<const ObOpRawExpr *>(l_expr);

const ObOpRawExpr *r_row = static_cast<const ObOpRawExpr *>(r_expr);

if (T_OP_IN == cmp_type || T_OP_NOT_IN == cmp_type) {

ObSEArray<int64_t, 4> common_offsets;

ObSEArray<int64_t, 4> tmp_offsets;

for (int64_t i = 0; OB_SUCC(ret) && i < l_row->get_param_count(); ++i) {

const ObRawExpr *r_param = r_row->get_param_expr(0);

if (OB_ISNULL(r_param) || OB_UNLIKELY(l_row->get_param_count() != r_param->get_param_count())) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else if (OB_FAIL(extract_basic_info(l_row->get_param_expr(i),

r_param->get_param_expr(i),

cmp_type,

tmp_offsets,

need_extract_const,

is_valid_expr))) {

LOG_WARN("failed to extract single offset", K(ret),

K(i), K(l_row), K(r_row), K(cmp_type));

}

}

if (OB_FAIL(ret)) {

} else if (T_OP_NOT_IN == cmp_type) {

if (OB_FAIL(append_array_no_dup(offsets, tmp_offsets))) {

LOG_WARN("failed to append array no dup", K(ret));

}

} else if (query_range_ctx_->use_in_optimization_ && !query_range_ctx_->row_in_offsets_.empty()) {

if (OB_FAIL(ObOptimizerUtil::intersect(query_range_ctx_->row_in_offsets_,

tmp_offsets,

common_offsets))) {

LOG_WARN("failed to intersect offsets", K(ret));

} else if (!common_offsets.empty()) {

// (c1,c2) in and (c1,c3) in can not use in optimization

query_range_ctx_->use_in_optimization_ = false;

}

}

if (OB_SUCC(ret) && T_OP_IN == cmp_type &&

OB_FAIL(append_array_no_dup(query_range_ctx_->row_in_offsets_, tmp_offsets))) {

LOG_WARN("failed to append row_in offsets", K(ret));

}

} else {

for (int64_t i = 0; OB_SUCC(ret) && i < r_row->get_param_count(); ++i) {

if (OB_FAIL(extract_basic_info(l_row->get_param_expr(i),

r_row->get_param_expr(i),

cmp_type,

offsets,

need_extract_const,

is_valid_expr))) {

LOG_WARN("failed to extract single offset", K(ret),

K(i), K(l_row), K(r_row), K(cmp_type));

}

}

}

}

return ret;

}

int ObQueryRange::preliminary_extract_query_range(const ColumnIArray &range_columns,

const ExprIArray &root_exprs,

const ObDataTypeCastParams &dtc_params,

ObExecContext *exec_ctx,

ExprConstrantArray *expr_constraints /* = NULL */,

const ParamsIArray *params /* = NULL */,

const bool phy_rowid_for_table_loc /* = false*/,

const bool ignore_calc_failure /* = true*/,

const bool use_in_optimization /* = false */)

{

int ret = OB_SUCCESS;

ObKeyPartList and_ranges;

ObKeyPart *temp_result = NULL;

has_exec_param_ = false;

ObKeyPartList geo_ranges;

bool has_geo_expr = false;

SQL_REWRITE_LOG(DEBUG, "preliminary extract", K(range_columns), K(root_exprs), K(use_in_optimization));

ObSEArray<ObRawExpr *, 16> candi_exprs;

ObArenaAllocator ctx_allocator(ObModIds::OB_QUERY_RANGE_CTX);

if (OB_FAIL(init_query_range_ctx(ctx_allocator, range_columns, exec_ctx,

expr_constraints, params, phy_rowid_for_table_loc,

ignore_calc_failure, use_in_optimization))) {

LOG_WARN("init query range context failed", K(ret));

} else if (OB_ISNULL(query_range_ctx_)) {

ret = OB_NOT_INIT;

LOG_WARN("query_range_ctx_ is not inited.", K(ret));

} else if (OB_FAIL(extract_valid_exprs(root_exprs, candi_exprs))) {

LOG_WARN("failed to extract candidate range exprs", K(ret));

} else if (candi_exprs.empty()) {

GET_ALWAYS_TRUE_OR_FALSE(true, temp_result);

if (OB_SUCC(ret) && !and_ranges.add_last(temp_result)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("add key part range failed", K(ret));

}

} else {

query_range_ctx_->only_one_expr_ = candi_exprs.count() == 1;

for (int64_t i = 0; OB_SUCC(ret) && i < candi_exprs.count(); ++i) {

const ObRawExpr *cur_expr = candi_exprs.at(i);

if (OB_ISNULL(cur_expr)) {

// continue

} else if (OB_FAIL(preliminary_extract(cur_expr, temp_result, dtc_params,

T_OP_IN == cur_expr->get_expr_type()))) {

LOG_WARN("Generate table range failed", K(ret));

} else if (NULL == temp_result) {

// ignore the condition from which we can not extract query range

} else if (cur_expr->has_flag(CNT_DYNAMIC_PARAM) &&

OB_FALSE_IT(has_exec_param_ = true)) {

} else if (is_contain_geo_filters()) {

// or connect with spatial filters for functional correctness

has_geo_expr = true;

if (OB_FAIL(add_or_item(geo_ranges, temp_result))) {

LOG_WARN("Link geo keypart failed", K(ret));

}

} else if (!and_ranges.add_last(temp_result)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("Add key part range failed", K(ret));

} else if (query_range_ctx_->cur_expr_is_precise_) {

if (is_strict_in_graph(temp_result)) {

ObRangeExprItem expr_item;

expr_item.cur_expr_ = cur_expr;

for (const ObKeyPart *cur_and = temp_result; OB_SUCC(ret) && cur_and != NULL;

cur_and = cur_and->and_next_) {

if (OB_FAIL(add_expr_offsets(expr_item.cur_pos_, cur_and))) {

LOG_WARN("failed to add expr pos", K(ret));

}

}

if (OB_SUCC(ret) &&

OB_FAIL(query_range_ctx_->precise_range_exprs_.push_back(expr_item))) {

LOG_WARN("store precise range exprs failed", K(ret));

}

} else if (NULL == temp_result->and_next_ && is_general_graph(*temp_result)) {

ObRangeExprItem expr_item;

expr_item.cur_expr_ = cur_expr;

for (const ObKeyPart *cur_or = temp_result; OB_SUCC(ret) && cur_or != NULL;

cur_or = cur_or->or_next_) {

if (OB_FAIL(add_expr_offsets(expr_item.cur_pos_, cur_or))) {

LOG_WARN("failed to add expr pos", K(ret));

}

}

if (OB_SUCC(ret) &&

OB_FAIL(query_range_ctx_->precise_range_exprs_.push_back(expr_item))) {

LOG_WARN("store precise range exprs failed", K(ret));

}

}

} // for each where condition

}

}

if (OB_SUCC(ret)) {

if (has_geo_expr) {

ObKeyPart *geo_results = NULL;

if (OB_FAIL(or_range_graph(geo_ranges, NULL, geo_results, dtc_params))) {

LOG_WARN("or range graph failed", K(ret));

} else if (!and_ranges.add_last(geo_results)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("add key part range failed", K(ret));

}

}

if (OB_FAIL(ret)) {

} else if (OB_FAIL(and_range_graph(and_ranges, temp_result))) {

LOG_WARN("And query range failed", K(ret));

} else if (OB_FAIL(refine_large_range_graph(temp_result, use_in_optimization))) {

LOG_WARN("failed to refine large range graph", K(ret));

} else if (OB_FAIL(check_graph_type(*temp_result))) {

LOG_WARN("check graph type failed", K(ret));

} else if (!is_reach_mem_limit_ && OB_FAIL(generate_expr_final_info())) {

LOG_WARN("failed to generate final exprs");

}

}

if (OB_SUCC(ret)) {

if (query_range_ctx_->need_final_extract_) {

state_ = NEED_PREPARE_PARAMS;

} else {

state_ = CAN_READ;

}

}

destroy_query_range_ctx(ctx_allocator);

return ret;

}

int ObQueryRange::add_expr_offsets(ObIArray<int64_t> &cur_pos, const ObKeyPart *cur_key)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(cur_key)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected null", K(ret));

} else if (cur_key->is_in_key()) {

if (OB_FAIL(append_array_no_dup(cur_pos, cur_key->in_keypart_->offsets_))) {

LOG_WARN("failed to append offset", K(ret));

}

} else if (OB_FAIL(add_var_to_array_no_dup(cur_pos, cur_key->pos_.offset_))) {

LOG_WARN("push back key index failed", K(ret));

}

return ret;

}

int ObQueryRange::remove_useless_range_graph(ObKeyPart *key_part, ObSqlBitSet<> &valid_offsets)

{

int ret = OB_SUCCESS;

if (OB_ISNULL(key_part)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("keypart is null", K(ret), K(key_part));

} else if (key_part->is_always_true() || key_part->is_always_false()) {

// do nothing

} else {

ObKeyPart *cur = key_part;

while (cur != NULL && OB_SUCC(ret)) {

if (OB_FAIL(set_valid_offsets(cur, &valid_offsets))) {

LOG_WARN("failed to set valid offsets", K(ret));

}

int64_t max_valid_offset = get_max_valid_offset(valid_offsets);

ObKeyPart *cur_key = cur;

while (OB_SUCC(ret) && cur_key != NULL) {

ObKeyPart *and_next = cur_key->and_next_;

if (is_and_next_useless(cur_key, and_next, max_valid_offset)) {

LOG_TRACE("remove useless keypart",

K(*cur_key), K(*and_next), K(max_valid_offset));

ObKeyPart *tmp = cur_key;

while (NULL != tmp && and_next == tmp->and_next_) {

tmp->and_next_ = NULL;

tmp = tmp->or_next_;

}

}

cur_key = cur_key->and_next_;

}

if (OB_FAIL(ret) || cur == NULL) {

// do nothing

} else if (OB_FAIL(remove_and_next_offset(cur, valid_offsets))) {

LOG_WARN("failed to remove and next offsets", K(ret));

} else {

cur = cur->or_next_;

}

}

}

return ret;

}

bool ObQueryRange::is_and_next_useless(ObKeyPart *cur_key, ObKeyPart *and_next, const int64_t max_valid_offset)

{

bool is_useless = false;

if (and_next != NULL && cur_key != NULL) {

int64_t and_next_offset = and_next->is_in_key() ?

and_next->in_keypart_->get_min_offset() :

and_next->pos_.offset_;

if (max_valid_offset != -1 && and_next_offset > max_valid_offset) {

is_useless = true;

for (ObKeyPart *tmp = cur_key; is_useless && NULL != tmp &&

and_next == tmp->and_next_; tmp = tmp->or_next_) {

// c3 can be extracted for predicates like c1 > 1 and c3 op/in X

is_useless = tmp->is_equal_condition();

}

}

}

return is_useless;

}

// if the range size is large then RANGE_MAX_SIZE, remove some ranges according to pos_.offset_

int ObQueryRange::refine_large_range_graph(ObKeyPart *&key_part, bool use_in_optimization)

{

int ret = OB_SUCCESS;

ObSEArray<ObKeyPart*, 8> pre_key_parts;

ObSEArray<ObKeyPart*, 8> key_parts;

ObSEArray<uint64_t, 8> or_count;

ObSEArray<ObKeyPart*, 8> next_key_parts;

ObSEArray<uint64_t, 8> next_or_count;

uint64_t cur_range_size = 1;

bool need_refine = false;

int64_t max_range_size = use_in_optimization ? MAX_RANGE_SIZE_NEW : MAX_RANGE_SIZE_OLD;

if (OB_ISNULL(key_part)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("keypart is null", K(ret), K(key_part));

} else if (OB_FAIL(key_parts.push_back(key_part)) ||

OB_FAIL(next_key_parts.push_back(key_part))) {

LOG_WARN("failed to push back", K(ret));

} else if (OB_FAIL(or_count.push_back(1))) {

LOG_WARN("failed to push back", K(ret));

}

while (OB_SUCC(ret) && !next_key_parts.empty() && !need_refine) {

if (OB_FAIL(compute_range_size(key_parts, or_count, next_key_parts, next_or_count,

cur_range_size))) {

LOG_WARN("failed to compute range size", K(ret));

} else if (cur_range_size > max_range_size) {

need_refine = true;

} else if (OB_FAIL(pre_key_parts.assign(key_parts))) {

LOG_WARN("failed to assign array", K(ret), K(key_parts));

} else if (OB_FAIL(key_parts.assign(next_key_parts))) {

LOG_WARN("failed to assign array", K(ret), K(next_key_parts));

} else if (OB_FAIL(or_count.assign(next_or_count))) {

LOG_WARN("failed to assign array", K(ret), K(next_or_count));

} else { /* do nothing */ }

}

range_size_ = need_refine ? max_range_size :

cur_range_size < RANGE_BUCKET_SIZE ? RANGE_BUCKET_SIZE : cur_range_size;

if (OB_SUCC(ret) && need_refine) {

ObKeyPart *first_keypart = NULL;

if (pre_key_parts.empty()) {

// first or_next_ list size is large than RANGE_MAX_SIZE, create a full key part

ObKeyPart *new_key = NULL;

if (OB_FAIL(alloc_full_key_part(new_key))) {

LOG_WARN("alloc full key part failed", K(ret));

} else if (OB_ISNULL(new_key)) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("keypart is null", K(ret));

} else if (OB_FAIL(remove_precise_range_expr(0))) {

LOG_WARN("remove precise range expr failed", K(ret));

} else {

new_key->id_ = key_part->id_;

key_part = new_key;

LOG_TRACE("refine large query range with full key", K(cur_range_size));

}

} else if (OB_ISNULL(first_keypart = pre_key_parts.at(0))) {

ret = OB_ERR_UNEXPECTED;

LOG_WARN("get unexpected input", K(ret), K(pre_key_parts));

} else {

int64_t redundant_offset = first_keypart->is_in_key() ?

first_keypart->in_keypart_->get_min_offset() + 1 :

first_keypart->pos_.offset_ + 1;

if (OB_FAIL(remove_precise_range_expr(redundant_offset))) {

LOG_WARN("remove precise range expr failed", K(ret));

} else {

// remove key part after pre key parts

LOG_TRACE("refine large query range remove some key parts",

K(cur_range_size), K(redundant_offset));

ObKeyPart *cur = NULL;;

ObKeyPart *and_next = NULL;

for (int64_t i = 0; OB_SUCC(ret) && i < pre_key_parts.count(); ++i) {

cur = pre_key_parts.at(i);

while (NULL != cur) {

if (NULL == cur->and_next_) {

cur = cur->or_next_;

} else {

and_next = cur->and_next_;