Skip to content

Commit f5b9247

Browse files
Gabriel39Gabriel39
committed
[fix](lance) Bound scalar segment planning and validate installed dependency
### What problem does this PR solve? Related PR: #68687 Problem Summary: Complement predicates repeated a full segment search per fragment, while oversized overlap and unsupported OR drivers coalesced fallback scans onto one task. Select positive indexable drivers within the native expression budget; otherwise keep fragment scans with scalar-index use disabled. Preserve simple BTree prefixes and full predicate evaluation. Record and check the installed Lance source and patch fingerprint so an ABI-compatible old library cannot be reused. ### Release note Preserve parallel Lance predicate scans and rebuild stale Lance dependencies. ### Check List (For Author) - Test: 65 focused FE JUnit tests; FE Checkstyle; 17 FE-generated plans / 30 native scans; build-gate and interrupted-publication tests; Groovy compilation. Full distributed SQL regression execution is pending CI. - Behavior changed: Yes, unsafe segment grouping falls back to fragment scans. - Does this need documentation: Existing predicate documentation PR #4184.
1 parent 531fcbd commit f5b9247

9 files changed

Lines changed: 446 additions & 64 deletions

File tree

‎build.sh‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -440,6 +440,7 @@ if [[ "${CLEAN}" -eq 1 && "${BUILD_BE}" -eq 0 && "${BUILD_FE}" -eq 0 && ${BUILD_
440440
fi
441441

442442
# build thirdparty libraries if necessary. check last thirdparty lib installation
443+
source "${DORIS_HOME}/thirdparty/lance-install.sh"
443444
if [[ "${TARGET_SYSTEM}" == 'Darwin' ]]; then
444445
LAST_THIRDPARTY_LIB='libbrotlienc.a'
445446
else
@@ -455,7 +456,8 @@ if [[ ! -f "${DORIS_THIRDPARTY}/installed/lib/${LAST_THIRDPARTY_LIB}" ||
455456
! -f "${DORIS_THIRDPARTY}/installed/include/paimon_rust/paimon.h" ||
456457
! -s "${DORIS_THIRDPARTY}/installed/lib64/libpaimon_c.a" ||
457458
! -s "${DORIS_THIRDPARTY}/installed/include/paimon_rust/paimon.h" ||
458-
-e "${DORIS_THIRDPARTY}/installed/lib64/.paimon-installing" ]]; then
459+
-e "${DORIS_THIRDPARTY}/installed/lib64/.paimon-installing" ]] ||
460+
! lance_c_install_is_current "${DORIS_HOME}/thirdparty" "${DORIS_THIRDPARTY}/installed"; then
459461
# Compilation images may contain only installed artifacts; never erase them without a rebuild source.
460462
if [[ ! -f "${DORIS_THIRDPARTY}/build-thirdparty.sh" ]]; then
461463
echo "Third-party dependencies require a rebuild, but build-thirdparty.sh is missing." >&2
@@ -471,6 +473,11 @@ if [[ ! -f "${DORIS_THIRDPARTY}/installed/lib/${LAST_THIRDPARTY_LIB}" ||
471473
else
472474
bash "${DORIS_THIRDPARTY}/build-thirdparty.sh" -j "${PARALLEL}" --clean
473475
fi
476+
# An external build script can itself be stale. Never link its old output silently.
477+
if ! lance_c_install_is_current "${DORIS_HOME}/thirdparty" "${DORIS_THIRDPARTY}/installed"; then
478+
echo "Lance dependency revision does not match this checkout. Refresh the third-party build tree." >&2
479+
exit 1
480+
fi
474481
fi
475482

476483
update_submodule() {

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

Lines changed: 123 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,17 @@
1717

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

20+
import org.apache.doris.analysis.ArrayLiteral;
2021
import org.apache.doris.analysis.BinaryPredicate;
2122
import org.apache.doris.analysis.CompoundPredicate;
2223
import org.apache.doris.analysis.Expr;
24+
import org.apache.doris.analysis.FunctionCallExpr;
2325
import org.apache.doris.analysis.InPredicate;
2426
import org.apache.doris.analysis.IsNullPredicate;
27+
import org.apache.doris.analysis.LikePredicate;
28+
import org.apache.doris.analysis.LiteralExpr;
2529
import org.apache.doris.analysis.SlotRef;
30+
import org.apache.doris.analysis.StringLiteral;
2631
import org.apache.doris.datasource.lance.index.LanceIndexSegmentGroup;
2732
import org.apache.doris.datasource.lance.index.LanceIndexSegmentInfo;
2833
import org.apache.doris.datasource.lance.metadata.LanceFragmentInfo;
@@ -31,13 +36,19 @@
3136
import org.lance.index.IndexType;
3237

3338
import java.util.ArrayList;
39+
import java.util.HashMap;
3440
import java.util.HashSet;
3541
import java.util.List;
3642
import java.util.Map;
3743
import java.util.Set;
3844

3945
/** Assigns one BTree/Bitmap/LabelList segment and a disjoint fragment domain to each ordinary scan task. */
4046
final class LanceScalarIndexPlanner {
47+
// Match the pinned lance-c scoped-expression bounds. Exceeding either bound makes
48+
// native planning scan the whole domain, so do not coalesce fragments in that case.
49+
private static final int MAX_EXPRESSION_NODES = 128;
50+
private static final int MAX_EXPRESSION_DEPTH = 32;
51+
4152
static final class Plan {
4253
final String indexName;
4354
final LanceSplitBuilder splits;
@@ -56,85 +67,164 @@ static Plan plan(LanceTableMetadata metadata, List<Expr> pushedConjuncts,
5667
|| !metadata.getIndexMetadataState().canPlanIndexSegments()) {
5768
return null;
5869
}
59-
Set<Integer> filterFields = collectFilterFields(metadata, pushedConjuncts);
60-
if (filterFields.isEmpty()) {
61-
return null;
70+
int nodes = Math.max(0, pushedConjuncts.size() - 1);
71+
for (Expr expr : pushedConjuncts) {
72+
nodes += expressionNodes(expr, Math.max(0, pushedConjuncts.size() - 1));
73+
if (nodes > MAX_EXPRESSION_NODES) {
74+
return null;
75+
}
6276
}
6377
// Metadata already groups physical segments by logical index. Name order
6478
// provides a stable winner when multiple indices cover the same number of rows.
6579
List<LanceIndexSegmentGroup> indices = new ArrayList<>(metadata.getIndexes());
6680
indices.sort(java.util.Comparator.comparing(LanceIndexSegmentGroup::getName));
67-
boolean splitComplementByFragment = pushedConjuncts.stream()
68-
.anyMatch(LanceScalarIndexPlanner::containsComplement);
6981
Plan selected = null;
82+
Map<IndexType, Set<Integer>> fieldsByIndexType = new HashMap<>();
7083
for (LanceIndexSegmentGroup logicalIndex : indices) {
7184
List<LanceIndexSegmentInfo> segments = logicalIndex.getSegments();
72-
// Segment-scoped scans support one top-level key in BTree/Bitmap/LabelList indices. Lance
73-
// performs the final typed driver selection and falls back within the same domain.
85+
// Only coalesce a segment when a positive, indexable necessary condition
86+
// exists. Broad complements keep fragment parallelism without repeating a
87+
// segment-wide index search once per fragment.
7488
LanceIndexSegmentInfo index = segments.get(0);
7589
if ((index.getIndexType() != IndexType.BTREE && index.getIndexType() != IndexType.BITMAP
7690
&& index.getIndexType() != IndexType.LABEL_LIST)
77-
|| index.getFieldIds().size() != 1 || !filterFields.contains(index.getFieldIds().get(0))) {
91+
|| index.getFieldIds().size() != 1
92+
|| !fieldsByIndexType.computeIfAbsent(index.getIndexType(),
93+
type -> collectFilterFields(metadata, pushedConjuncts, type))
94+
.contains(index.getFieldIds().get(0))) {
7895
continue;
7996
}
80-
Plan candidate = groupFragments(metadata, segments, visibleFragments,
81-
splitComplementByFragment);
97+
Plan candidate = groupFragments(metadata, segments, visibleFragments);
8298
if (candidate != null && (selected == null || candidate.coveredRows > selected.coveredRows)) {
8399
selected = candidate;
84100
}
85101
}
86102
return selected;
87103
}
88104

89-
private static Set<Integer> collectFilterFields(LanceTableMetadata metadata, List<Expr> pushedConjuncts) {
105+
private static Set<Integer> collectFilterFields(LanceTableMetadata metadata,
106+
List<Expr> pushedConjuncts, IndexType indexType) {
90107
Set<Integer> fields = new HashSet<>();
91108
for (Expr expr : pushedConjuncts) {
92-
fields.addAll(collectDriverFields(metadata, expr, false));
109+
fields.addAll(collectDriverFields(metadata, expr, indexType));
93110
}
94111
return fields;
95112
}
96113

97-
private static Set<Integer> collectDriverFields(LanceTableMetadata metadata, Expr expr, boolean complete) {
114+
private static Set<Integer> collectDriverFields(LanceTableMetadata metadata, Expr expr, IndexType indexType) {
115+
Set<Integer> fields = new HashSet<>();
98116
if (expr instanceof CompoundPredicate) {
99117
CompoundPredicate.Operator op = ((CompoundPredicate) expr).getOp();
100118
if (op == CompoundPredicate.Operator.NOT) {
101-
// NOT cannot complement a pruned AND: that would discard valid matches.
102-
return collectDriverFields(metadata, expr.getChild(0), true);
119+
return fields;
103120
}
104-
Set<Integer> left = collectDriverFields(metadata, expr.getChild(0), complete);
105-
Set<Integer> right = collectDriverFields(metadata, expr.getChild(1), complete);
106-
if (op == CompoundPredicate.Operator.AND && !complete) {
121+
Set<Integer> left = collectDriverFields(metadata, expr.getChild(0), indexType);
122+
Set<Integer> right = collectDriverFields(metadata, expr.getChild(1), indexType);
123+
if (op == CompoundPredicate.Operator.AND) {
107124
left.addAll(right);
108125
} else {
109-
// One selected index must supply candidates for both OR branches, and for
110-
// every leaf of a negated subtree. lance-c rechecks the complete predicate.
126+
// Sharing a slot is insufficient: both OR branches must actually be
127+
// indexable. A suffix LIKE, for example, cannot supply BTree candidates.
111128
left.retainAll(right);
112129
}
113130
return left;
114131
}
132+
if (!isPositiveIndexLeaf(expr, indexType)) {
133+
return fields;
134+
}
115135
Set<SlotRef> slots = new HashSet<>();
116136
expr.collect(SlotRef.class, slots);
117-
Set<Integer> fields = new HashSet<>();
118137
for (SlotRef slot : slots) {
119138
metadata.getLanceFieldId(slot.getColumnName()).ifPresent(fields::add);
120139
}
121140
return fields;
122141
}
123142

124-
private static boolean containsComplement(Expr expr) {
125-
if ((expr instanceof CompoundPredicate
126-
&& ((CompoundPredicate) expr).getOp() == CompoundPredicate.Operator.NOT)
127-
|| (expr instanceof InPredicate && ((InPredicate) expr).isNotIn())
128-
|| (expr instanceof BinaryPredicate
129-
&& ((BinaryPredicate) expr).getOp() == BinaryPredicate.Operator.NE)
130-
|| (expr instanceof IsNullPredicate && ((IsNullPredicate) expr).isNotNull())) {
131-
return true;
132-
}
133-
return expr.getChildren().stream().anyMatch(LanceScalarIndexPlanner::containsComplement);
143+
private static boolean isPositiveIndexLeaf(Expr expr, IndexType indexType) {
144+
if (indexType == IndexType.LABEL_LIST) {
145+
if (!(expr instanceof FunctionCallExpr) || expr.getChildren().size() != 2) {
146+
return false;
147+
}
148+
String name = ((FunctionCallExpr) expr).getFnName().getFunction();
149+
if ("array_contains".equalsIgnoreCase(name)) {
150+
return expr.getChild(0) instanceof SlotRef && expr.getChild(1) instanceof LiteralExpr;
151+
}
152+
return "arrays_overlap".equalsIgnoreCase(name) && overlapSize(expr) > 0;
153+
}
154+
if (expr instanceof BinaryPredicate) {
155+
BinaryPredicate.Operator op = ((BinaryPredicate) expr).getOp();
156+
return (op == BinaryPredicate.Operator.EQ || op == BinaryPredicate.Operator.GT
157+
|| op == BinaryPredicate.Operator.GE || op == BinaryPredicate.Operator.LT
158+
|| op == BinaryPredicate.Operator.LE)
159+
&& ((expr.getChild(0) instanceof SlotRef && expr.getChild(1) instanceof LiteralExpr)
160+
|| (expr.getChild(1) instanceof SlotRef && expr.getChild(0) instanceof LiteralExpr));
161+
}
162+
if (expr instanceof InPredicate) {
163+
return !((InPredicate) expr).isNotIn() && expr.getChild(0) instanceof SlotRef;
164+
}
165+
if (expr instanceof IsNullPredicate) {
166+
return !((IsNullPredicate) expr).isNotNull() && expr.getChild(0) instanceof SlotRef;
167+
}
168+
// Bitmap has no prefix-query support. Keep only unambiguous BTree prefixes;
169+
// escaped and other LIKE shapes remain pushed filters in fragment scans.
170+
if (indexType != IndexType.BTREE || expr.getChildren().size() != 2
171+
|| !(expr.getChild(0) instanceof SlotRef) || !(expr.getChild(1) instanceof StringLiteral)) {
172+
return false;
173+
}
174+
String name = expr instanceof FunctionCallExpr
175+
? ((FunctionCallExpr) expr).getFnName().getFunction() : "";
176+
boolean like = (expr instanceof LikePredicate && ((LikePredicate) expr).getOp() == LikePredicate.Operator.LIKE)
177+
|| "like".equalsIgnoreCase(name);
178+
String prefix = ((StringLiteral) expr.getChild(1)).getStringValue();
179+
if (like && prefix.endsWith("%")) {
180+
prefix = prefix.substring(0, prefix.length() - 1);
181+
} else if (!"starts_with".equalsIgnoreCase(name)) {
182+
return false;
183+
}
184+
return !prefix.isEmpty() && prefix.indexOf('%') < 0 && prefix.indexOf('_') < 0 && prefix.indexOf('\\') < 0;
185+
}
186+
187+
private static int overlapSize(Expr expr) {
188+
if (!(expr instanceof FunctionCallExpr) || expr.getChildren().size() != 2
189+
|| !"arrays_overlap".equalsIgnoreCase(((FunctionCallExpr) expr).getFnName().getFunction())) {
190+
return 0;
191+
}
192+
for (int i = 0; i < 2; i++) {
193+
if (expr.getChild(i) instanceof ArrayLiteral && expr.getChild(1 - i) instanceof SlotRef) {
194+
return expr.getChild(i).getChildren().size();
195+
}
196+
}
197+
return 0;
198+
}
199+
200+
private static int expressionNodes(Expr expr, int depth) {
201+
if (depth > MAX_EXPRESSION_DEPTH) {
202+
return MAX_EXPRESSION_NODES + 1;
203+
}
204+
if (expr instanceof CompoundPredicate) {
205+
int nodes = 1;
206+
for (Expr child : expr.getChildren()) {
207+
nodes += expressionNodes(child, depth + 1);
208+
if (nodes > MAX_EXPRESSION_NODES) {
209+
break;
210+
}
211+
}
212+
return nodes;
213+
}
214+
int labels = overlapSize(expr);
215+
// The converter emits a balanced OR tree: N memberships require 2*N-1 nodes.
216+
if (labels > 0) {
217+
int levels = 32 - Integer.numberOfLeadingZeros(labels - 1);
218+
if (labels > MAX_EXPRESSION_NODES / 2 || depth + levels > MAX_EXPRESSION_DEPTH) {
219+
return MAX_EXPRESSION_NODES + 1;
220+
}
221+
return 2 * labels - 1;
222+
}
223+
return 1;
134224
}
135225

136226
private static Plan groupFragments(LanceTableMetadata metadata, List<LanceIndexSegmentInfo> segments,
137-
Map<Long, LanceFragmentInfo> visibleFragments, boolean splitComplementByFragment) {
227+
Map<Long, LanceFragmentInfo> visibleFragments) {
138228
LanceSplitBuilder splits = new LanceSplitBuilder(
139229
metadata.getDatasetUri(), metadata.getVersion(), segments.size());
140230
Set<Long> coveredFragments = new HashSet<>();
@@ -162,17 +252,7 @@ private static Plan groupFragments(LanceTableMetadata metadata, List<LanceIndexS
162252
coveredRows += Math.max(fragment.getPhysicalRows(), 0);
163253
}
164254
if (!fragments.isEmpty()) {
165-
// Complement selectivity is unknown. Preserve fragment-level scheduling so a
166-
// broad NOT cannot funnel all covered data through one BE. Each task retains
167-
// the same segment UUID but owns a disjoint domain, including on fallback.
168-
if (splitComplementByFragment) {
169-
for (Long fragmentId : fragments) {
170-
splits.addIndexSegmentSplit(segment.getUuid(), java.util.Collections.singletonList(fragmentId),
171-
visibleFragments.get(fragmentId).getSchedulingWeight());
172-
}
173-
} else {
174-
splits.addIndexSegmentSplit(segment.getUuid(), fragments, physicalRows);
175-
}
255+
splits.addIndexSegmentSplit(segment.getUuid(), fragments, physicalRows);
176256
}
177257
}
178258
return splits.isEmpty() ? null : new Plan(segments.get(0).getIndexName(), splits, coveredRows);

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -195,7 +195,9 @@ private List<Split> createNormalFragmentSplits(LanceTableMetadata metadata,
195195
} else {
196196
plan = new LanceSplitBuilder(metadata.getDatasetUri(), metadata.getVersion(), 0);
197197
}
198-
plan.addUncoveredFragments(visibleFragments.values(), 1, scalarIndexPlan != null);
198+
// A rejected segment driver must not be rediscovered independently by every
199+
// fragment scanner. Keep the pushed filter, but evaluate it in parallel scans.
200+
plan.addUncoveredFragments(visibleFragments.values(), 1, !lancePushedConjuncts.isEmpty());
199201
return plan.buildSplits();
200202
}
201203

0 commit comments

Comments
 (0)