github-actions[bot] commented on code in PR #68758: URL: https://github.com/apache/doris/pull/68758#discussion_r4278981620
########## be/src/storage/index/inverted/query/engine/boolean_query/listed_terms.cpp: ########## @@ -0,0 +1,304 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#include "storage/index/inverted/query/engine/boolean_query/listed_terms.h" + +#include <parallel_hashmap/phmap.h> + +#include <algorithm> +#include <bit> +#include <optional> +#include <span> +#include <utility> + +#include "common/check.h" +#include "common/exception.h" +#include "storage/index/inverted/query/engine/postings/listed_walk.h" +#include "storage/index/inverted/query/engine/scored_rows_scorer.h" +#include "storage/index/inverted/query/exec/block_doc_set.h" +#include "storage/index/inverted/query/exec/cursor_chained_postings.h" +#include "storage/index/inverted/query/exec/roaring_docid_sink.h" +#include "storage/index/inverted/query/exec/term_waves.h" +#include "storage/index/inverted/query/phrase/position_span.h" + +namespace doris::segment_v2::inverted_index::query_v2 { + +ListedTerms::ListedTerms(index_query::IndexSourcePtr source, + std::shared_ptr<roaring::Roaring> nulls) + : _source(std::move(source)), _nulls(std::move(nulls)) {} + +void ListedTerms::add(size_t clause, std::string term, + index_query::ScoringContextPtr<float> similarity) { + DCHECK(_clauses.empty() || _clauses.back() < clause); + _clauses.push_back(clause); + _terms.push_back(std::move(term)); + _similarities.push_back(std::move(similarity)); +} + +bool ListedTerms::holds(size_t clause) const { + return std::ranges::binary_search(_clauses, clause); +} + +void ListedTerms::open(bool conjunctive, bool scoring) { + if (!conjunctive) { + return; + } + for (const std::string& term : _terms) { + bool held = false; + THROW_IF_ERROR(_source->may_hold(term, &held)); + if (!held) { + _cursors.resize(_terms.size()); + return; + } + } + // A scored conjunction reads the positions of the rows it lists. + THROW_IF_ERROR( + _source->open_terms(_terms, /*positions=*/scoring, /*scoring=*/false, &_cursors)); +} + +bool ListedTerms::has_absent_term() const { + return std::ranges::any_of(_cursors, [](const auto& cursor) { return cursor == nullptr; }); +} + +uint64_t ListedTerms::cheapest_doc_freq() const { + uint64_t cheapest = UINT64_MAX; + for (const auto& cursor : _cursors) { + cheapest = std::min<uint64_t>(cheapest, cursor == nullptr ? 0 : cursor->doc_freq()); + } + return cheapest; +} + +index_query::TruthSet ListedTerms::conjunction(const std::vector<uint32_t>* candidates) { + index_query::TruthSet result; + if (_nulls != nullptr) { + result.null_rows = *_nulls; + } + if (has_absent_term()) { + return result; + } + std::vector<uint32_t> docs; + THROW_IF_ERROR(index_query::chain_cursors(_cursors, candidates, &docs)); Review Comment: [P2] Keep dense CLucene conjunctions in range or bitmap form. For an unscored CLucene `MATCH_ALL 'alpha beta'` where both terms occur in every row, the new unscored OP_AND grouping reaches this chain. `CursorChainedPostings` expands the first term's dense ranges into a uint32 vector, and `chained_conjunction` holds that vector while copying the second term's candidate rows into another one, requiring roughly 8*N temporary bytes (about 8 MB for one million rows) before converting back to Roaring. The removed ConjunctionQuery kept these runs compressed with addRange and bitmap intersection. This adds per-row copying and large transient allocations to dense MATCH_ALL scans, independently in each scanner. Preserve a range/bitmap path for dense nonbatching sources or use a bounded streaming intersection. ########## be/src/exprs/function/search/function_search.cpp: ########## @@ -0,0 +1,656 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#include "exprs/function/search/function_search.h" + +#include <CLucene/config/repl_wchar.h> +#include <CLucene/debug/error.h> +#include <fmt/format.h> +#include <gen_cpp/Exprs_types.h> +#include <glog/logging.h> + +#include <algorithm> +#include <iterator> +#include <memory> +#include <optional> +#include <roaring/roaring.hh> +#include <string> +#include <unordered_map> +#include <utility> +#include <vector> + +#include "common/config.h" +#include "common/exception.h" +#include "common/status.h" +#include "core/block/columns_with_type_and_name.h" +#include "core/data_type/data_type_nullable.h" +#include "core/data_type/primitive_type.h" +#include "exprs/function/search/function_search_leaf.h" +#include "exprs/function/search/search_lowering.h" +#include "exprs/function/search/variant_inverted_index_search.h" +#include "exprs/function/simple_function_factory.h" +#include "exprs/vexpr_context.h" +#include "runtime/runtime_profile.h" +#include "storage/index/index_file_reader.h" +#include "storage/index/index_query_context.h" +#include "storage/index/inverted/analysis/analyzer/analyzer.h" +#include "storage/index/inverted/inverted_index_iterator.h" +#include "storage/index/inverted/inverted_index_reader.h" +#include "storage/index/inverted/query/engine/all_query/all_query.h" +#include "storage/index/inverted/query/engine/bit_set_query/bit_set_query.h" +#include "storage/index/inverted/query/engine/boolean_query/boolean_query_builder.h" +#include "storage/index/inverted/query/engine/boolean_query/operator.h" +#include "storage/index/inverted/query/engine/collect/doc_set_collector.h" +#include "storage/index/inverted/query/engine/collect/top_k_collector.h" +#include "storage/index/inverted/query/engine/null_masked_query.h" +#include "storage/index/inverted/query/exec/term_pattern.h" +#include "storage/index/inverted/query/logical/node.h" +#include "storage/index/inverted/reader/collection_statistics.h" +#include "storage/olap_common.h" +#include "storage/segment/variant/nested_group_provider.h" +#include "util/thrift_util.h" + +namespace doris { + +namespace query_v2 = segment_v2::inverted_index::query_v2; + +// Serializes the whole TSearchParam, so every field of the DSL takes part in the signature, and +// adds the limit on the terms PREFIX, WILDCARD and REGEXP clauses expand to. +std::string FunctionSearch::dsl_cache_signature(const TSearchParam& search_param, + const IndexQueryContext* context) { + ThriftSerializer ser(false, 1024); + TSearchParam copy = search_param; + std::string sig; + auto st = ser.serialize(©, &sig); + if (UNLIKELY(!st.ok())) { + LOG(WARNING) << "build_dsl_signature: Thrift serialization failed: " << st.to_string() + << ", caching disabled for this query"; + return ""; + } + sig += "|max_expansions="; + sig += std::to_string( + index_query::max_expansions(context != nullptr ? context->runtime_state : nullptr)); + return sig; +} + +// Extract segment path prefix from the first available inverted index iterator. +// All fields in the same segment share the same path prefix. +static std::string extract_segment_prefix( + const std::unordered_map<std::string, IndexIterator*>& iterators) { + for (const auto& [field_name, iter] : iterators) { + auto* inv_iter = dynamic_cast<InvertedIndexIterator*>(iter); + if (!inv_iter) continue; + // Try fulltext reader first, then string type + for (auto type : + {InvertedIndexReaderType::FULLTEXT, InvertedIndexReaderType::STRING_TYPE}) { + IndexReaderType reader_type = type; + auto reader = inv_iter->get_reader(reader_type); + if (!reader) continue; + auto inv_reader = std::dynamic_pointer_cast<InvertedIndexReader>(reader); + if (!inv_reader) continue; + auto file_reader = inv_reader->get_index_file_reader(); + if (!file_reader) continue; + return file_reader->get_index_path_prefix(); + } + } + VLOG_DEBUG << "extract_segment_prefix: no suitable inverted index reader found across " + << iterators.size() << " iterators, caching disabled for this query"; + return ""; +} + +namespace { + +// A SEARCH result is cached as two entries: its TRUE rows, and its UNKNOWN rows under the +// signature with a "__null" suffix. +InvertedIndexQueryCache::CacheKey dsl_cache_key(const std::string& seg_prefix, + const std::string& signature) { + return {seg_prefix, "__search_dsl__", InvertedIndexQueryType::SEARCH_DSL_QUERY, signature}; +} + +// Either entry can be evicted, or not yet inserted, without the other, and TRUE rows found +// without their UNKNOWN rows are no result. +bool lookup_dsl_result(InvertedIndexQueryCache* cache, const std::string& seg_prefix, + const std::string& signature, InvertedIndexResultBitmap* result) { + InvertedIndexQueryCacheHandle rows_handle; + InvertedIndexQueryCacheHandle nulls_handle; + if (!cache->lookup(dsl_cache_key(seg_prefix, signature), &rows_handle) || + !cache->lookup(dsl_cache_key(seg_prefix, signature + "__null"), &nulls_handle)) { + return false; + } + auto rows = rows_handle.get_bitmap(); + auto nulls = nulls_handle.get_bitmap(); + if (rows == nullptr || nulls == nullptr) { + return false; + } + *result = InvertedIndexResultBitmap(std::move(rows), std::move(nulls)); + return true; +} + +// The UNKNOWN rows go in first, so a search that finds the TRUE rows finds them as well. +void insert_dsl_result(InvertedIndexQueryCache* cache, const std::string& seg_prefix, + const std::string& signature, const InvertedIndexResultBitmap& result) { + auto nulls = result.get_null_bitmap() != nullptr ? result.get_null_bitmap() + : std::make_shared<roaring::Roaring>(); + InvertedIndexQueryCacheHandle nulls_handle; + cache->insert(dsl_cache_key(seg_prefix, signature + "__null"), std::move(nulls), &nulls_handle); + InvertedIndexQueryCacheHandle rows_handle; + cache->insert(dsl_cache_key(seg_prefix, signature), result.get_data_bitmap(), &rows_handle); +} + +bool is_nested_group_search_supported() { + auto provider = segment_v2::create_nested_group_read_provider(); + return provider != nullptr && provider->should_enable_nested_group_read_path(); +} + +namespace logical = index_query::logical; + +// Lowering's view of the resolver: what index a field binds to and how that +// index analyzes values. +class SearchFieldCatalog final : public logical::FieldCatalog { +public: + SearchFieldCatalog(FieldReaderResolver& resolver, std::shared_ptr<IndexQueryContext> context) + : _resolver(resolver), _context(std::move(context)) {} + + Status resolve(const std::string& field, InvertedIndexQueryType query_type, + logical::FieldProps* out) override { + FieldReaderBinding binding; + RETURN_IF_ERROR(_resolver.resolve(field, query_type, &binding)); + if (!binding.is_bound()) { + LOG(INFO) << "search: No inverted index for field '" << field + << "' in this segment, query_type=" << static_cast<int>(query_type) + << ", returning UNKNOWN bitmap"; + *out = logical::FieldProps {}; + return Status::OK(); + } + const bool scalar = binding.inverted_reader != nullptr && + binding.inverted_reader->type() == InvertedIndexReaderType::BKD; + const bool analyzed = !scalar && inverted_index::InvertedIndexAnalyzer::should_analyzer( + binding.index_properties); + *out = logical::FieldProps {.bound = true, + .direct_index = scalar, + .analyzed = analyzed, + .binding = binding.binding_key}; + return Status::OK(); + } + + Status analyze(const logical::FieldProps& props, const std::string& value, + std::vector<logical::Token>* out) override { + const FieldReaderBinding* binding = _resolver.find_binding(props.binding); + if (binding == nullptr) { + return Status::InternalError("search: no binding '{}' to analyze with", props.binding); + } + int64_t unused_timer = 0; + SCOPED_RAW_TIMER(_context != nullptr && _context->stats != nullptr + ? &_context->stats->inverted_index_analyzer_timer + : &unused_timer); + InvertedIndexAnalyzerCtxSPtr analyzer_ctx; + RETURN_IF_ERROR(_resolver.analyzer_context_for(props.binding, &analyzer_ctx)); + return inverted_index::InvertedIndexAnalyzer::analyze(value, analyzer_ctx.get(), + binding->index_properties, out); + } + + Status normalize(const logical::FieldProps& props, const std::string& value, + std::string* out) override { + const FieldReaderBinding* binding = _resolver.find_binding(props.binding); + if (binding == nullptr) { + return Status::InternalError("search: no binding '{}' to normalize with", + props.binding); + } + try { + *out = inverted_index::InvertedIndexAnalyzer::normalize(value, + binding->index_properties); + } catch (const CLuceneError& e) { + return Status::Error<ErrorCode::INVERTED_INDEX_ANALYZER_ERROR>( + "search: normalizing '{}' failed: {}", value, e.what()); + } catch (const Exception& e) { + return Status::Error<ErrorCode::INVERTED_INDEX_ANALYZER_ERROR>( + "search: normalizing '{}' failed: {}", value, e.what()); + } + return Status::OK(); + } + +private: + FieldReaderResolver& _resolver; + std::shared_ptr<IndexQueryContext> _context; +}; + +query_v2::Occur to_query_occur(logical::Occur occur) { + switch (occur) { + case logical::Occur::kShould: + return query_v2::Occur::SHOULD; + case logical::Occur::kMustNot: + return query_v2::Occur::MUST_NOT; + case logical::Occur::kMust: + default: + return query_v2::Occur::MUST; + } +} + +Status compile_node(const logical::Node& node, const SearchLeafContext& ctx, + FieldReaderResolver& resolver, query_v2::QueryPtr* out, + std::string* binding_key); + +// An array column can keep values in a row whose array is NULL, and its index lists the row +// under them; the leaf leaves such a row UNKNOWN, not TRUE. +Status mask_array_nulls(const FieldReaderBinding& binding, const FieldReaderResolver& resolver, + const std::string& field, query_v2::QueryPtr* query) { + if (binding.column_type == nullptr || + remove_nullable(binding.column_type)->get_primitive_type() != TYPE_ARRAY) { + return Status::OK(); + } + IndexIterator* iterator = resolver.get_iterator(field); + if (iterator == nullptr) { + return Status::OK(); + } + auto has_null = iterator->has_null(); + if (!has_null.has_value() || !has_null.value()) { + return Status::OK(); + } + InvertedIndexQueryCacheHandle handle; + RETURN_IF_ERROR(iterator->read_null_bitmap(&handle)); + auto nulls = handle.get_bitmap(); + if (nulls != nullptr && !nulls->isEmpty()) { + *query = std::make_shared<query_v2::NullMaskedQuery>(std::move(*query), std::move(nulls)); + } + return Status::OK(); +} + +using Clauses = std::vector<std::pair<logical::Occur, logical::NodePtr>>; + +bool has_required_clause(const Clauses& clauses) { + return std::ranges::any_of( + clauses, [](const auto& clause) { return clause.first == logical::Occur::kMust; }); +} + +// Without scoring, optional clauses beside a required one change neither the rows nor their +// UNKNOWN state, so they are left out. +Clauses matching_clauses(const logical::Bool& boolean, bool scoring) { + if (scoring || boolean.op != logical::BoolOp::kOccur || boolean.min_should_match != 0 || + !has_required_clause(boolean.clauses)) { + return boolean.clauses; + } + Clauses kept; + std::ranges::copy_if(boolean.clauses, std::back_inserter(kept), [](const auto& clause) { + return clause.first != logical::Occur::kShould; + }); + return kept; +} + +// AND, OR and NOT ignore the per-clause occur; OCCUR keeps it and the threshold. A Boolean +// left with one clause after dropping clauses that only score is that clause, with its binding. +Status compile_bool(const logical::Bool& boolean, const SearchLeafContext& ctx, + FieldReaderResolver& resolver, query_v2::QueryPtr* out, + std::string* binding_key) { + const Clauses clauses = matching_clauses(boolean, ctx.scoring); + if (clauses.size() == 1 && boolean.clauses.size() > 1) { + return compile_node(*clauses.front().second, ctx, resolver, out, binding_key); + } + std::vector<query_v2::QueryPtr> queries(clauses.size()); + std::vector<std::string> keys(clauses.size()); + for (size_t i = 0; i < clauses.size(); ++i) { + RETURN_IF_ERROR(compile_node(*clauses[i].second, ctx, resolver, &queries[i], &keys[i])); + } + if (boolean.op == logical::BoolOp::kOccur) { + auto builder = query_v2::create_occur_boolean_query_builder(); + builder->set_minimum_number_should_match(boolean.min_should_match); + for (size_t i = 0; i < clauses.size(); ++i) { + builder->add(queries[i], to_query_occur(clauses[i].first), std::move(keys[i])); + } + *out = builder->build(); + return Status::OK(); + } + query_v2::OperatorType op = query_v2::OperatorType::OP_AND; + if (boolean.op == logical::BoolOp::kOr) { + op = query_v2::OperatorType::OP_OR; + } else if (boolean.op == logical::BoolOp::kNot) { + op = query_v2::OperatorType::OP_NOT; + } + auto builder = query_v2::create_operator_boolean_query_builder(op); + for (size_t i = 0; i < clauses.size(); ++i) { + builder->add(queries[i], std::move(keys[i])); + } + *out = builder->build(); + return Status::OK(); +} + +// A threshold counts the set's terms above the field's compiler, so every format +// answers it the same way: each term is its own leaf on the field. +Status compile_term_threshold(const logical::TermSet& set, const SearchLeafContext& ctx, + SearchLeafCompiler& compiler, query_v2::QueryPtr* out) { + auto builder = query_v2::create_occur_boolean_query_builder(); + builder->set_minimum_number_should_match(set.min_should_match); + const query_v2::Occur occur = set.require_all ? query_v2::Occur::MUST : query_v2::Occur::SHOULD; + for (const auto& term : set.terms) { + const auto leaf = logical::make_node(logical::TermSet { + .field = set.field, .terms = {term}, .require_all = false, .min_should_match = 0}); + query_v2::QueryPtr term_query; + RETURN_IF_ERROR(compiler.compile(*leaf, ctx, &term_query)); + builder->add(term_query, occur, set.field.binding); + } + *out = builder->build(); Review Comment: [P1] Retain field NULL rows for SNII TERM thresholds. On a nullable analyzed SNII field containing foo, bar, baz and NULL, `search('NOT body:foo/bar', '{"mode":"standard","default_operator":"or","minimum_should_match":1}')` now returns the NULL row along with baz. This newly supported multi-token threshold is compiled as an OccurBooleanQuery whose scorer drops UNKNOWN, so the enclosing standard-mode NOT sees FALSE at the NULL row. `mask_array_nulls` restores a field bitmap only for arrays, leaving scalar fields affected. Both terms can exist and caching can be disabled, so this is separate from the absent-term and empty-leaf findings. Preserve the bound field's UNKNOWN rows around the threshold before leaf mapping and add nullable scalar scored/unscored coverage. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
