Skip to content

Commit e078d4f

Browse files
committed
enhance scalar index filter
1 parent a425660 commit e078d4f

14 files changed

Lines changed: 4080 additions & 47 deletions

File tree

‎be/src/format_v2/table/lance_reader.cpp‎

Lines changed: 40 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,18 @@ Status LanceTableReader::init(TableReadOptions&& options) {
160160
{"deltas_searched",
161161
ADD_CHILD_COUNTER_WITH_LEVEL(_scanner_profile, "LanceVectorIndexSegmentsSearched",
162162
TUnit::UNIT, LANCE_READER_PROFILE, 1)},
163+
{"scalar_segments_requested",
164+
ADD_CHILD_COUNTER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexSegmentsRequested",
165+
TUnit::UNIT, LANCE_READER_PROFILE, 1)},
166+
{"scalar_segments_searched",
167+
ADD_CHILD_COUNTER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexSegmentsSearched",
168+
TUnit::UNIT, LANCE_READER_PROFILE, 1)},
169+
{"scalar_segment_fallbacks",
170+
ADD_CHILD_COUNTER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexSegmentFallbacks",
171+
TUnit::UNIT, LANCE_READER_PROFILE, 1)},
172+
{"scalar_segment_candidate_rows",
173+
ADD_CHILD_COUNTER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexCandidateRows",
174+
TUnit::UNIT, LANCE_READER_PROFILE, 1)},
163175
};
164176
_lance_time_metrics = {
165177
// This is wait time reported by the same Lance scan execution node described above,
@@ -169,6 +181,12 @@ Status LanceTableReader::init(TableReadOptions&& options) {
169181
{"find_partitions_elapsed",
170182
ADD_CHILD_TIMER_WITH_LEVEL(_scanner_profile, "LanceIVFPartitionRankingTime",
171183
LANCE_READER_PROFILE, 1)},
184+
{"scalar_segment_prepare_time",
185+
ADD_CHILD_TIMER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexSegmentPrepareTime",
186+
LANCE_READER_PROFILE, 1)},
187+
{"scalar_segment_search_time",
188+
ADD_CHILD_TIMER_WITH_LEVEL(_scanner_profile, "LanceScalarIndexSegmentSearchTime",
189+
LANCE_READER_PROFILE, 1)},
172190
};
173191
if (_search_kind != SearchKind::NORMAL) {
174192
RETURN_IF_ERROR(_validate_external_search_request());
@@ -857,8 +875,28 @@ Status LanceTableReader::_configure_normal_scan(LanceScanner* scanner,
857875
lance_scanner_set_fragment_ids(scanner, fragment_ids.data(), fragment_ids.size()) != 0) {
858876
return lance_error("set Lance scanner fragment ids");
859877
}
860-
if (lance_params.__isset.index_segment_uuids && !lance_params.index_segment_uuids.empty()) {
861-
return Status::InvalidArgument("normal Lance scan cannot contain index segment UUIDs");
878+
std::vector<uint8_t> segment_uuids;
879+
size_t segment_count = 0;
880+
RETURN_IF_ERROR(parse_index_segment_uuids(lance_params, &segment_uuids, &segment_count));
881+
if (segment_count > 1) {
882+
return Status::InvalidArgument("normal Lance scan accepts only one scalar index segment");
883+
}
884+
if (segment_count == 1) {
885+
if (fragment_ids.empty() || !lance_params.__isset.version || lance_params.version <= 0) {
886+
return Status::InvalidArgument(
887+
"Lance scalar index segment requires a fixed version and nonempty fragment "
888+
"ids");
889+
}
890+
if (lance_params.__isset.use_scalar_index && !lance_params.use_scalar_index) {
891+
return Status::InvalidArgument(
892+
"Lance scalar index segment cannot be combined with use_scalar_index=false");
893+
}
894+
if (lance_scanner_set_scalar_index_segment(scanner, segment_uuids.data()) != 0) {
895+
return lance_error("set Lance scanner scalar index segment");
896+
}
897+
} else if (lance_params.__isset.use_scalar_index &&
898+
lance_scanner_set_use_scalar_index(scanner, lance_params.use_scalar_index) != 0) {
899+
return lance_error("set Lance scanner scalar index usage");
862900
}
863901
// FE sets this only when every predicate has been pushed into Lance.
864902
if (lance_params.__isset.limit && lance_params.limit > 0 &&

‎be/test/format_v2/table/lance_reader_test.cpp‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1220,6 +1220,131 @@ TEST(LanceTableReaderFilterTest, CombinesStaticSubstraitFilterWithRuntimeFilter)
12201220
EXPECT_TRUE(combined_reader.close().ok());
12211221
}
12221222

1223+
TEST(LanceTableReaderScalarSegmentTest, FiltersIndexedAndUncoveredDomainsWithoutLosingRows) {
1224+
const auto unique_suffix = std::chrono::steady_clock::now().time_since_epoch().count();
1225+
for (const auto index_type : {LANCE_SCALAR_BTREE, LANCE_SCALAR_BITMAP}) {
1226+
const auto dataset_uri = std::filesystem::temp_directory_path() /
1227+
("doris_lance_scalar_segment_" + std::to_string(unique_suffix) +
1228+
"_" + std::to_string(index_type) + ".lance");
1229+
Defer cleanup {[&] {
1230+
std::error_code error;
1231+
std::filesystem::remove_all(dataset_uri, error);
1232+
}};
1233+
const auto schema = arrow::schema({arrow::field("row_id", arrow::int64(), false)});
1234+
for (int64_t first_id : {1, 3}) {
1235+
arrow::Int64Builder values;
1236+
ASSERT_TRUE(values.AppendValues({first_id, first_id + 1}).ok());
1237+
auto array = values.Finish();
1238+
ASSERT_TRUE(array.ok());
1239+
auto batch = arrow::RecordBatch::Make(schema, 2, {std::move(array).ValueUnsafe()});
1240+
auto batches = arrow::RecordBatchReader::Make({batch}, schema);
1241+
ASSERT_TRUE(batches.ok());
1242+
ArrowArrayStream stream {};
1243+
ASSERT_TRUE(
1244+
arrow::ExportRecordBatchReader(std::move(batches).ValueUnsafe(), &stream).ok());
1245+
auto dataset = ::lance::Dataset::write(
1246+
dataset_uri.string(), &stream,
1247+
first_id == 1 ? ::lance::WriteMode::Create : ::lance::WriteMode::Append);
1248+
if (first_id == 1) {
1249+
// The second append remains uncovered by this index segment.
1250+
dataset.create_scalar_index("row_id", index_type, "row_id_idx");
1251+
}
1252+
}
1253+
LanceFixtureInfo fixture;
1254+
ASSERT_TRUE(get_fixture_info(dataset_uri, &fixture).ok());
1255+
ASSERT_EQ(2, fixture.fragment_ids.size());
1256+
std::vector<std::string> segments;
1257+
ASSERT_TRUE(get_index_segment_uuids(dataset_uri, "row_id_idx", &segments).ok());
1258+
ASSERT_EQ(1, segments.size());
1259+
1260+
const auto read_domain = [&](const std::vector<int64_t>& fragments, bool use_segment,
1261+
const std::vector<int64_t>& expected, int64_t searched,
1262+
int64_t fallbacks) {
1263+
TQueryGlobals globals;
1264+
RuntimeState state(globals);
1265+
RuntimeProfile profile("lance_scalar_segment");
1266+
TFileScanRangeParams scan_params;
1267+
const Columns columns {projected_column("row_id", TYPE_BIGINT, false)};
1268+
LanceTableReader reader;
1269+
auto filter = create_int64_runtime_in_conjunct("row_id", {2, 4}, 41);
1270+
ASSERT_TRUE(
1271+
init_reader(&reader, columns, &state, &profile, &scan_params, {filter}).ok());
1272+
auto range = make_lance_range(dataset_uri, fixture.version, fragments);
1273+
if (use_segment) {
1274+
range.table_format_params.lance_params.__set_index_segment_uuids(segments);
1275+
} else {
1276+
range.table_format_params.lance_params.__set_use_scalar_index(false);
1277+
}
1278+
ASSERT_TRUE(prepare_range(&reader, std::move(range)).ok());
1279+
Block block;
1280+
add_output_columns(&block, columns);
1281+
std::vector<int64_t> actual;
1282+
bool eos = false;
1283+
while (!eos) {
1284+
auto status = reader.get_block(&block, &eos);
1285+
ASSERT_TRUE(status.ok()) << status.to_string();
1286+
if (!eos) {
1287+
const auto& ids =
1288+
assert_cast<const ColumnInt64&>(*block.get_by_position(0).column);
1289+
actual.insert(actual.end(), ids.get_data().begin(), ids.get_data().end());
1290+
}
1291+
}
1292+
std::ranges::sort(actual);
1293+
EXPECT_EQ(expected, actual);
1294+
EXPECT_EQ(use_segment ? 1 : 0,
1295+
profile.get_counter("LanceScalarIndexSegmentsRequested")->value());
1296+
EXPECT_EQ(searched, profile.get_counter("LanceScalarIndexSegmentsSearched")->value());
1297+
EXPECT_EQ(fallbacks, profile.get_counter("LanceScalarIndexSegmentFallbacks")->value());
1298+
if (!use_segment) {
1299+
EXPECT_EQ(0, profile.get_counter("LanceIndexComparisons")->value());
1300+
}
1301+
EXPECT_TRUE(reader.close().ok());
1302+
};
1303+
read_domain({fixture.fragment_ids[0]}, true, {2}, 1, 0);
1304+
read_domain({fixture.fragment_ids[1]}, false, {4}, 0, 0);
1305+
// A segment which cannot cover the whole task must filter the entire explicit domain.
1306+
read_domain(fixture.fragment_ids, true, {2, 4}, 0, 1);
1307+
}
1308+
}
1309+
1310+
TEST(LanceTableReaderScalarSegmentTest, RejectsInvalidSegmentAssignments) {
1311+
const std::filesystem::path dataset_uri =
1312+
"./be/test/format_v2/table/lance/data/all_types.lance";
1313+
LanceFixtureInfo fixture;
1314+
ASSERT_TRUE(get_fixture_info(dataset_uri, &fixture).ok());
1315+
const auto check_invalid = [&](TLanceFileDesc params, const std::string& message) {
1316+
TQueryGlobals globals;
1317+
RuntimeState state(globals);
1318+
RuntimeProfile profile("lance_invalid_scalar_segment");
1319+
TFileScanRangeParams scan_params;
1320+
LanceTableReader reader;
1321+
ASSERT_TRUE(init_reader(&reader, {projected_column("row_id", TYPE_BIGINT, false)}, &state,
1322+
&profile, &scan_params)
1323+
.ok());
1324+
auto range = make_lance_range(dataset_uri, fixture.version, fixture.fragment_ids);
1325+
range.table_format_params.__set_lance_params(std::move(params));
1326+
auto status = prepare_range(&reader, std::move(range));
1327+
EXPECT_FALSE(status.ok());
1328+
EXPECT_NE(status.to_string().find(message), std::string::npos) << status.to_string();
1329+
EXPECT_TRUE(reader.close().ok());
1330+
};
1331+
auto params = make_lance_range(dataset_uri, fixture.version, fixture.fragment_ids)
1332+
.table_format_params.lance_params;
1333+
params.__set_index_segment_uuids({"too-short"});
1334+
check_invalid(params, "16 bytes");
1335+
params.__set_index_segment_uuids({std::string(16, 'a'), std::string(16, 'b')});
1336+
check_invalid(params, "only one scalar index segment");
1337+
params.__set_index_segment_uuids({std::string(16, 'a')});
1338+
params.__set_fragment_ids({});
1339+
check_invalid(params, "nonempty fragment ids");
1340+
params.__set_fragment_ids(fixture.fragment_ids);
1341+
params.__set_version(0);
1342+
check_invalid(params, "fixed version");
1343+
params.__set_version(fixture.version);
1344+
params.__set_use_scalar_index(false);
1345+
check_invalid(params, "use_scalar_index=false");
1346+
}
1347+
12231348
TEST(LanceTableReaderFilterTest, PushesRuntimeInFilterIntoLanceScanner) {
12241349
const std::filesystem::path dataset_uri =
12251350
"./be/test/format_v2/table/lance/data/all_types.lance";

‎fe/fe-core/src/main/java/org/apache/doris/datasource/lance/LanceFragmentInfo.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -47,8 +47,8 @@ public long getRowCount() {
4747
/**
4848
* Returns the number of physical rows stored before deletions.
4949
*
50-
* <p>The BE legacy reader reads and merges physical batches before applying the deletion
51-
* vector, so split scheduling uses this value rather than {@link #getRowCount()}.
50+
* <p>Reading a fragment can process rows later discarded by deletion vectors, so split
51+
* scheduling uses this value rather than {@link #getRowCount()}.
5252
*/
5353
public long getPhysicalRows() {
5454
return physicalRows;

‎fe/fe-core/src/main/java/org/apache/doris/datasource/lance/source/IndexSegmentSplitPlan.java‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -64,12 +64,6 @@ void addIndexSegmentSplit(UUID indexSegmentUuid,
6464
datasetUri, version, indexSegmentUuid, fragmentIds, physicalRows));
6565
}
6666

67-
// Ordinary scans use segment coverage only to group fragments. No UUID is sent to Lance.
68-
void addIndexSegmentFragmentGroup(List<Long> fragmentIds, long physicalRows) {
69-
indexSegmentFragmentIds.addAll(fragmentIds);
70-
addFragmentGroup(fragmentIds, physicalRows);
71-
}
72-
7367
// Manifest order and row-based split weights are shared by ordinary scans and fallbacks.
7468
// An empty index coverage set groups all fragments; vector fallbacks use a group size of 1.
7569
void addUncoveredFragments(Iterable<LanceFragmentInfo> fragments, int fragmentsPerSplit) {
@@ -99,7 +93,7 @@ private void addFragmentGroup(List<Long> fragmentIds, long physicalRows) {
9993
splits.add(LanceSplit.forFragments(datasetUri, version, fragmentIds, physicalRows));
10094
}
10195

102-
/** Subdivides ordinary fragment groups to provide work for the available backends. */
96+
/** Subdivides fragment-only groups for available backends; assigned segments stay intact. */
10397
List<Split> buildFragmentSplits(int numBackends, Map<Long, LanceFragmentInfo> visibleFragments) {
10498
int targetSplits = Math.min(numBackends, visibleFragments.size());
10599
if (splits.size() >= targetSplits) {

‎fe/fe-core/src/main/java/org/apache/doris/datasource/lance/source/LancePredicateConverter.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -607,7 +607,7 @@ private byte[] serialize(Expression expression) {
607607
schemaBuilder.addNames(field.getName());
608608
structBuilder.addTypes(type.get());
609609
} else {
610-
// Lance 4.x removes user-defined top-level fields before handing the
610+
// Lance removes user-defined top-level fields before handing the
611611
// ExtendedExpression to DataFusion and remaps field ordinals. This keeps the
612612
// envelope aligned with the full dataset schema when unrelated complex or
613613
// otherwise unsupported columns are present.

‎fe/fe-core/src/main/java/org/apache/doris/datasource/lance/source/LanceScalarIndexPlanner.java‎

Lines changed: 26 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -17,22 +17,24 @@
1717

1818
package org.apache.doris.datasource.lance.source;
1919

20+
import org.apache.doris.analysis.CompoundPredicate;
2021
import org.apache.doris.analysis.Expr;
2122
import org.apache.doris.analysis.SlotRef;
2223
import org.apache.doris.datasource.lance.LanceFragmentInfo;
2324
import org.apache.doris.datasource.lance.LanceIndexSegmentInfo;
2425
import org.apache.doris.datasource.lance.LanceTableMetadata;
2526

27+
import org.lance.index.IndexType;
28+
2629
import java.util.ArrayList;
27-
import java.util.Collections;
2830
import java.util.HashSet;
2931
import java.util.List;
3032
import java.util.Map;
3133
import java.util.Set;
3234
import java.util.TreeMap;
3335
import java.util.stream.Collectors;
3436

35-
/** Groups fragments using scalar-index coverage. Index search planning remains entirely in Lance. */
37+
/** Assigns one BTree/Bitmap/LabelList segment and a disjoint fragment domain to each ordinary scan task. */
3638
final class LanceScalarIndexPlanner {
3739
static final class Plan {
3840
final String indexName;
@@ -62,11 +64,12 @@ static Plan plan(LanceTableMetadata metadata, List<Expr> pushedConjuncts,
6264
TreeMap::new, Collectors.toList()));
6365
Plan selected = null;
6466
for (List<LanceIndexSegmentInfo> segments : indices.values()) {
65-
// The loader copies logical-index field metadata into every segment. An index
66-
// is a candidate when any of its fields occurs in a pushed filter.
67-
// Non-vector indices include INVERTED (FTS); this selects grouping, not search semantics.
67+
// PR #79 supports one top-level key in BTree/Bitmap/LabelList indices. Lance
68+
// performs the final typed driver selection and falls back within the same domain.
6869
LanceIndexSegmentInfo index = segments.get(0);
69-
if (index.isVectorIndex() || Collections.disjoint(index.getFieldIds(), filterFields)) {
70+
if ((index.getIndexType() != IndexType.BTREE && index.getIndexType() != IndexType.BITMAP
71+
&& index.getIndexType() != IndexType.LABEL_LIST)
72+
|| index.getFieldIds().size() != 1 || !filterFields.contains(index.getFieldIds().get(0))) {
7073
continue;
7174
}
7275
Plan candidate = groupFragments(metadata, segments, visibleFragments);
@@ -79,22 +82,36 @@ static Plan plan(LanceTableMetadata metadata, List<Expr> pushedConjuncts,
7982

8083
private static Set<Integer> collectFilterFields(LanceTableMetadata metadata, List<Expr> pushedConjuncts) {
8184
Set<SlotRef> slots = new HashSet<>();
82-
pushedConjuncts.forEach(expr -> expr.collect(SlotRef.class, slots));
85+
pushedConjuncts.forEach(expr -> collectDriverSlots(expr, slots));
8386
Set<Integer> fields = new HashSet<>();
8487
for (SlotRef slot : slots) {
8588
metadata.getLanceFieldId(slot.getColumnName()).ifPresent(fields::add);
8689
}
8790
return fields;
8891
}
8992

93+
private static void collectDriverSlots(Expr expr, Set<SlotRef> slots) {
94+
// A predicate below OR or NOT is not a necessary condition of the whole filter.
95+
// Do not select its index and then force every task into a non-indexed fallback.
96+
if (expr instanceof CompoundPredicate) {
97+
if (((CompoundPredicate) expr).getOp() == CompoundPredicate.Operator.AND) {
98+
expr.getChildren().forEach(child -> collectDriverSlots(child, slots));
99+
}
100+
} else {
101+
expr.collect(SlotRef.class, slots);
102+
}
103+
}
104+
90105
private static Plan groupFragments(LanceTableMetadata metadata, List<LanceIndexSegmentInfo> segments,
91106
Map<Long, LanceFragmentInfo> visibleFragments) {
92107
IndexSegmentSplitPlan splits = new IndexSegmentSplitPlan(
93108
metadata.getDatasetUri(), metadata.getVersion(), segments.size());
94109
Set<Long> coveredFragments = new HashSet<>();
95110
long coveredRows = 0;
96111
for (LanceIndexSegmentInfo segment : segments) {
97-
if (!segment.getFragmentIds().isPresent()) {
112+
if (!segment.getFragmentIds().isPresent()
113+
|| segment.getIndexType() != segments.get(0).getIndexType()
114+
|| !segment.getFieldIds().equals(segments.get(0).getFieldIds())) {
98115
return null;
99116
}
100117
List<Long> fragments = new ArrayList<>();
@@ -114,7 +131,7 @@ private static Plan groupFragments(LanceTableMetadata metadata, List<LanceIndexS
114131
coveredRows += Math.max(fragment.getPhysicalRows(), 0);
115132
}
116133
if (!fragments.isEmpty()) {
117-
splits.addIndexSegmentFragmentGroup(fragments, physicalRows);
134+
splits.addIndexSegmentSplit(segment.getUuid(), fragments, physicalRows);
118135
}
119136
}
120137
return splits.isEmpty() ? null : new Plan(segments.get(0).getIndexName(), splits, coveredRows);

0 commit comments

Comments
 (0)