airborne12 commented on code in PR #67538: URL: https://github.com/apache/doris/pull/67538#discussion_r3985300672
########## be/src/storage/index/snii/format/format_constants.h: ########## @@ -93,7 +93,14 @@ inline constexpr uint8_t kEnc = 1u << 1; // 0=slim / 1=windowed inline constexpr uint8_t kHasSb = 1u << 2; // posting prelude includes sub-block directory inline constexpr uint8_t kHasChampion = 1u << 3; // v1 always 0 inline constexpr uint8_t kOffsetsRef = 1u << 4; // v1 always 0 -// bit5-7 reserved +// The entry keeps its term key and df but carries no posting locator and no payload: the +// writer dropped a posting list too large for any reader to want. bit0/bit1/bit2 are +// meaningless when this is set, and nothing follows the term stats. A reader that finds +// this entry must treat the term as matching every document -- which is what the query +// side's cost gate already does for a df this high -- and must never confuse it with a +// term absent from the dictionary, which means the opposite: matching no document. +inline constexpr uint8_t kPostingDropped = 1u << 5; Review Comment: Fixed in e613a244c06: the metadata directory raises `kFeatureDroppedPostings` (= 2) in `required_features` whenever an inverted entry dropped at least one posting list, so a reader without the feature refuses the container as unsupported up front -- the same path as the blob feature -- and the query is evaluated without the index; directories without such entries keep their pre-feature bytes. Test: `SniiMetadataDirectory.DroppedPostingsRaiseTheFeatureAndRoundTrip`. On a writer-side fence: dropped entries are only ever produced for gram-family indexes, which this PR introduces, so a BE without this code cannot use such an index at all and the required feature is the fence that keeps it from misreading one. Stop-gram deliberately has no switch (the size target depends on it), so there is no separate write-side toggle. ########## be/src/storage/index/inverted/gram/gram_density.cpp: ########## @@ -0,0 +1,125 @@ +// 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/gram/gram_density.h" + +#include <algorithm> + +#include "storage/index/inverted/gram/gram_extractor.h" + +namespace doris::segment_v2::gram { + +DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len) + : _min_literal_len(min_literal_len), + _max_gram_len(max_gram_len), + _histogram(kHashValues, 0) {} + +void DensitySolver::observe(std::string_view value) { + if (_min_literal_len < _max_gram_len || _max_gram_len < 2) { Review Comment: Fixed in 2cc0776c891: `GramScheme`'s default `max_gram` is now 4 (measured earlier in this PR: about 60% less dictionary than 16 with the posting lists unchanged), so a bare `mode=sparse` tokenizer keeps the 12-byte promise, and where a tokenizer sets `max_gram` above the promise the writer raises the promise to `max_gram` instead of collecting nothing. Test: `GramDensityCalibrationTest.DefaultsCollectEvidenceAndALongMaxGramRaisesThePromise` (a tokenizer with only `mode=sparse` solves; `max_gram=16` yields a 16-byte promise). ########## be/src/storage/index/inverted/gram/gram_density.cpp: ########## @@ -0,0 +1,125 @@ +// 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/gram/gram_density.h" + +#include <algorithm> + +#include "storage/index/inverted/gram/gram_extractor.h" + +namespace doris::segment_v2::gram { + +DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len) + : _min_literal_len(min_literal_len), + _max_gram_len(max_gram_len), + _histogram(kHashValues, 0) {} + +void DensitySolver::observe(std::string_view value) { + if (_min_literal_len < _max_gram_len || _max_gram_len < 2) { + return; + } + // Boundaries with a whole gram's room after them inside a window: a boundary at k yields + // [k, k+max_gram_len) at worst, so k may not exceed len - max_gram_len. That leaves + // `per_window` candidate positions in a window of the promised length. + const size_t per_window = _min_literal_len - _max_gram_len + 1; + + size_t i = 0; + const size_t n = value.size(); + while (i < n) { + // Only ASCII runs: they are the only bytes the extractor indexes, so a window + // spanning anything else could never produce a gram. + if (static_cast<unsigned char>(value[i]) >= 0x80) { + ++i; + continue; + } + size_t j = i; + while (j < n && static_cast<unsigned char>(value[j]) < 0x80) { + ++j; + } + const std::string_view run = value.substr(i, j - i); + i = j; + if (run.size() < _min_literal_len) { + continue; + } + // Sliding minimum over the run's pair hashes, one window per start position. The + // monotonic queue keeps this linear in the run rather than quadratic in the window, + // which is what makes it affordable on the write path. + const size_t pairs = run.size() - 1; + _mono.clear(); + size_t head = 0; + for (size_t p = 0; p < pairs; ++p) { Review Comment: Fixed in 2cc0776c891: the scan stops at pair `run.size() - max_gram`, so exactly `run.size() - L + 1` windows are counted. Test: `GramDensityTest.CountsExactlyOneWindowPerStartPosition` pins the counts for `max_gram` in {2, 3, 4, 8} at lengths 24 / 25 / 40, an L-byte run as one window and a shorter run as none. ########## be/src/storage/index/inverted/gram/gram_density.cpp: ########## @@ -0,0 +1,125 @@ +// 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/gram/gram_density.h" + +#include <algorithm> + +#include "storage/index/inverted/gram/gram_extractor.h" + +namespace doris::segment_v2::gram { + +DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len) + : _min_literal_len(min_literal_len), + _max_gram_len(max_gram_len), + _histogram(kHashValues, 0) {} + +void DensitySolver::observe(std::string_view value) { + if (_min_literal_len < _max_gram_len || _max_gram_len < 2) { + return; + } + // Boundaries with a whole gram's room after them inside a window: a boundary at k yields + // [k, k+max_gram_len) at worst, so k may not exceed len - max_gram_len. That leaves + // `per_window` candidate positions in a window of the promised length. + const size_t per_window = _min_literal_len - _max_gram_len + 1; + + size_t i = 0; + const size_t n = value.size(); + while (i < n) { + // Only ASCII runs: they are the only bytes the extractor indexes, so a window + // spanning anything else could never produce a gram. + if (static_cast<unsigned char>(value[i]) >= 0x80) { + ++i; + continue; + } + size_t j = i; + while (j < n && static_cast<unsigned char>(value[j]) < 0x80) { Review Comment: Fixed in 2cc0776c891: NUL ends a run the way a non-ASCII byte does. Test: `GramDensityTest.NulEndsARunLikeNonAscii` (`A\0B` with L=3, M=2 observes no window; 14 bytes + NUL + 15 bytes observes 3 + 4 rather than 19). ########## be/src/common/config.cpp: ########## @@ -1324,6 +1324,39 @@ DEFINE_Int32(inverted_index_query_cache_shards, "256"); // inverted index match bitmap cache size DEFINE_String(inverted_index_query_cache_limit, "10%"); +namespace { + +bool valid_gram_index_candidate_ratio(int32_t value) { + return value >= 0; +} + +bool valid_gram_index_candidate_min_rows(int32_t value) { + return value >= 0; +} + +} // namespace + +// Whether LIKE/REGEXP tries to compile a constant pattern into a gram boolean query pushed down +// to a gram-family inverted index (master switch). +DEFINE_mBool(enable_gram_index_regexp, "true"); + +// Cost gate for the gram boolean query: give up pruning above this share (in basis points) of a +// segment's rows, and only on segments of at least this many rows. Giving up returns the segment's +// whole docid range, so it can never drop a candidate row. +DEFINE_mInt32(gram_index_max_candidate_ratio_bp, "15"); +DEFINE_Validator(gram_index_max_candidate_ratio_bp, valid_gram_index_candidate_ratio); +DEFINE_mInt32(gram_index_candidate_ratio_min_rows, "65536"); + +// On by default: a configured density is wrong on every column but the one it was chosen for, +// and the solve costs one pass over a bounded sample. +DEFINE_mBool(enable_gram_index_adaptive_density, "true"); +// 12 bytes at 95% of windows. Both are the promise rather than a tuning pair -- what a user +// may reasonably change is how short a literal they expect to find, not the boundary rate. +DEFINE_mInt32(gram_index_min_literal_bytes, "12"); +DEFINE_mInt32(gram_index_density_coverage_permille, "950"); Review Comment: Fixed in 2cc0776c891: validators are registered for `gram_index_density_coverage_permille` (1..1000), `gram_index_min_literal_bytes` (>= 1) and `gram_index_density_sample_bytes` (>= 0); a live update to -1 / 0 / 1001 is rejected and the previous value kept. Test: `GramDensityCalibrationTest.ConfigValidatorsRejectImpossibleValues`. The config framework runs validators on the update paths only (the adjacent ratio validators behave the same way), so startup takes be.conf as written; the writer no longer reaches a checked cast on a bad value because the validated range is what `cast_set` needs. -- 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]
