Gabriel39 opened a new pull request, #69346:
URL: https://github.com/apache/doris/pull/69346
### What problem does this PR solve?
Related PR: #69332 (lance-c dependency upgrade)
Supersedes #69339; targets branch-4.2.
Ordinary SQL against Lance external tables does not use the existing Lance
search path for vector Top-N, and `score()` cannot produce Lance BM25
relevance. Users currently need explicit `vector_search()` /
`full_text_search()` TVFs.
This PR adds automatic rewrites on branch-4.2, reusing the existing
fixed-snapshot search planner, index-segment execution, global candidate merge,
and deferred payload reads. It upgrades lance-c to
`4fafcd64525b274b113208390bbcca86bbbc093b`, as in #69332, and directly uses
`lance_scanner_set_row_addr_allowlist()` introduced by lance-c #96.
### Function and metric coverage
| Doris SQL expression | Lance metric / query | Automatic pushdown in this
PR | SQL value and ordering |
| --- | --- | --- | --- |
| `l2_distance_approximate(v, q)` | `l2` | Yes, ascending Top-N | Euclidean
distance `sqrt(native squared L2)`, smaller is better |
| `inner_product_approximate(v, q)` | `dot` (`dot_product` alias in the TVF)
| Yes, descending Top-N | Inner product `1 - native dot distance`, larger is
better |
| `l2_distance(v, q)` / `inner_product(v, q)` | Mathematically related to
`l2` / `dot` | No; exact functions remain scalar | Exhaustive scalar
evaluation; no automatic ANN substitution |
| `cosine_distance(v, q)` / `cosine_similarity(v, q)` | `cosine` | No; use
the existing `vector_search(metric="cosine", ...)` explicitly | Native cosine
distance is `1 - cosine similarity`; raw TVF distances are ascending |
| No Hamming approximate SQL function in this branch | `hamming` | No;
available through the existing explicit vector TVF for supported binary vectors
| Hamming distance, smaller is better |
| `l1_distance(v, q)` | No L1 metric exposed by the bundled vector-search
API | No | Remains scalar |
| `score()` with `MATCH_ANY` / `MATCH_ALL` / `MATCH_PHRASE` | Prepared BM25
match-OR / match-AND / phrase | Yes, descending Top-N | Native Lance BM25
relevance, larger is better |
This branch has **two** vector SQL functions with the `_approximate` suffix,
and both are covered above. It does not introduce
`cosine_distance_approximate()` or a Hamming approximate function. Native Lance
capabilities and Doris SQL automatic rewriting are separate levels of support:
cosine/Hamming metrics, supported multi-vector queries, and search tuning such
as `nprobes`, `refine_factor` and `ef` remain explicit-TVF capabilities.
The raw `vector_search()` TVF continues to return Lance `_distance`: squared
L2 for `l2`, `1 - dot` for `dot`, cosine distance for `cosine`, and Hamming
distance for `hamming`. The automatic SQL rewrite applies the conversions in
the table; raw TVF output is unchanged. Cosine expressions are deliberately not
rewritten: for example, Doris scalar cosine functions have explicit zero-vector
results, so mathematical equivalence on ordinary vectors alone does not
establish full semantic equivalence.
BM25 values are computed from Lance's stored analyzer/index and
pinned-dataset scoring statistics. This supports the SQL usage pattern used by
Doris internal tables, but does not promise identical numeric scores or
tokenization to a separately indexed Doris internal table. Fuzzy BM25,
multi-column boolean `SEARCH()` expressions, custom analyzer overrides, and
arbitrary score predicates are outside this automatic rewrite.
### Approximate versus scalar semantics (including NULL / NaN)
Calling an `_approximate` function in an eligible Top-N opts into the native
Lance search candidate contract. This PR does not add a separate session switch
or scan all stored vectors merely to reproduce scalar validation.
| Input / behavior | Existing scalar execution (including exact functions) |
Eligible native approximate Top-N |
| --- | --- | --- |
| Ordinary non-NULL finite Float32 vectors | Exhaustive scalar distances |
Native candidate retrieval, potentially approximate with a compatible index |
| Stored NULL vector | Scalar distance raises a NULL-input error | Native
search excludes that vector |
| Stored vector producing a NaN distance | Scalar distance can return NaN
and Doris Top-N can retain the row | Native search excludes NaN distances,
including a single-row/all-NaN dataset |
| NULL element inside a stored vector | Scalar distance raises a
NULL-element error | Unsupported input domain: callers must ensure vector
elements contain no NULLs; native kernels do not reproduce scalar element-NULL
validation |
| Exact `l2_distance()` / `inner_product()` | Existing scalar evaluation |
Never rewritten by this rule |
| Projection containing a non-movable expression such as `assert_true()` |
Evaluation/errors remain before Top-N | Rewrite is skipped to avoid suppressing
evaluation on pruned rows |
For example, for rows `(1, NULL)` and `(2, [1,0])`, a native approximate
search can return only row 2; the corresponding scalar distance query raises an
error. For a dataset containing only `[NaN,0]`, native approximate search
returns no candidates whereas scalar Top-N can retain its NaN-valued row. Fewer
than LIMIT rows is therefore possible when vectors do not belong to the native
candidate domain. These are deliberate, documented semantics of opting into
provider-native approximate search, not claims that the old scalar NULL/NaN
behavior is preserved. Use exact functions when scalar validation and row
eligibility are required.
### SQL examples and behavior changes
The examples assume a Lance table with a three-dimensional Float32 embedding
whose elements contain no NULLs, and a supported full-text index on `body`.
#### 1. Approximate vector Top-N
```sql
SELECT doc_id,
l2_distance_approximate(embedding, [0.1, 0.2, 0.3]) AS distance
FROM lance_catalog.docs.documents
WHERE tenant_id = 7
ORDER BY distance ASC
LIMIT 10 OFFSET 5;
```
Before: ordinary Lance scanning evaluates the scalar distance and Doris
performs Top-N; this SQL does not request native Lance vector search.
After: the optimizer creates a native Lance L2 search with the original
scalar predicate applied before candidate selection. Each search split requests
15 candidates with offset 0; Doris merges them and applies the final global
`OFFSET 5 LIMIT 10`. Compatible Lance vector indexes can serve the approximate
search through the existing search planner. Candidate selection may therefore
be approximate rather than an exhaustive scalar ranking.
The SQL result remains Euclidean distance: Lance's squared L2 result is
converted with `CAST(sqrt(_distance) AS FLOAT)`.
Inner-product queries use the corresponding descending order:
```sql
SELECT doc_id,
inner_product_approximate(embedding, [0.1, 0.2, 0.3]) AS similarity
FROM lance_catalog.docs.documents
WHERE tenant_id = 7
ORDER BY similarity DESC
LIMIT 10;
```
This becomes native Lance dot search. The projection converts Lance dot
distance with `1.0f - _distance`, so the SQL output remains an inner-product
similarity and higher is better.
#### 2. BM25 full-text Top-N
```sql
SELECT doc_id, score() AS relevance
FROM lance_catalog.docs.documents
WHERE body MATCH_ANY 'database search'
AND tenant_id = 7
ORDER BY relevance DESC
LIMIT 10;
```
Before: `score()` on this Lance external scan is unsupported.
After: one top-level MATCH predicate becomes a native prepared Lance
full-text query, `score()` reads its generated BM25 score, and Doris merges the
highest-scoring candidates. The native prepared query preserves the
dataset-wide scoring context across index segments and row-ID filtering.
- `MATCH_ANY` maps to a match query with OR.
- `MATCH_ALL` maps to a match query with AND.
- `MATCH_PHRASE` maps to a phrase query using the stored analyzer and
position information.
- A lower score bound such as `AND score() >= 0.5` is supported as a
residual over the generated score. Upper bounds and other score predicates are
rejected because filtering a pruned Top-K with those predicates could lose
valid results.
#### 3. Scalar WHERE to native row-ID prefilter
For the scalar predicates in the examples, the execution path is:
```text
Bound Lance snapshot + validated Substrait predicate
-> row-ID-only native scan (no user-column projection)
-> native UINT64 _rowid allowlist
-> vector / prepared full-text search
-> Doris global Top-N and final projection
```
The candidate scanner and search scanner use the same pinned dataset
snapshot. A query-local cache shares the candidate list across search readers
using the dataset URI, version, and filter as its key. An empty allowlist
selects zero rows.
The list is capped at 65,536 IDs. Broader predicates discard the entire
partial list and retain the complete native Substrait prefilter on the search
scanner. This bounds the C++ candidate list and preserves correctness. Profile
counters expose prefilter time, candidate count, cache hits, and fallback count.
### ACL / EXISTS example and the remaining boundary
```sql
SELECT d.doc_id,
d.title,
l2_distance_approximate(d.embedding, [0.1, 0.2, 0.3]) AS distance
FROM lance_catalog.docs.documents d
WHERE EXISTS (
SELECT 1
FROM internal.app.document_acl a
WHERE a.doc_id = d.doc_id
AND a.user_id = 1001
)
ORDER BY distance ASC, d.doc_id ASC
LIMIT 10;
```
This query **does not receive automatic Lance Top-N pushdown in this PR**.
It contains an ACL semi-join and a secondary sort key, outside the
direct-scan/single-key rewrite. It retains the existing join/filter and
scalar-distance/global-Top-N execution. Using exact `l2_distance()` instead
likewise remains scalar.
The native row-ID allowlist added here is produced from fully pushable
predicates on the same pinned Lance dataset. It does **not** translate an ACL
table's business `doc_id` values into Lance `_rowid`, and it does not consume
dynamically produced semi-join IDs. Supporting that scenario requires a
separate `doc_id -> native _rowid` lookup plus a join/runtime-filter handoff,
with ACL filtering before candidate pruning. Pushing an unfiltered Top-K below
EXISTS could miss the nearest authorized documents, so this PR deliberately
avoids that rewrite.
### Scope and compatibility
- Automatic rewriting requires a direct Lance scan, an optional filter, a
projection, and a single search ordering key with LIMIT. It does not rewrite
across JOIN/EXISTS, add secondary sort keys, or support the internal-table
`SEARCH()` DSL.
- Vector rewriting supports physical Float32 fixed-size-list vectors and
constant query arrays. Exact `l2_distance()`, reversed vector ordering,
incompatible vector types, and vector queries with unsupported residual
predicates keep scalar execution.
- BM25 requires one supported top-level MATCH on a direct string column, a
literal query, the stored analyzer, and `ORDER BY score() DESC`. Remaining
scalar predicates must be fully convertible by the existing Lance predicate
converter. Unsupported scored-query shapes fail explicitly rather than silently
selecting incorrect candidates.
- The rewrite preserves bound snapshot/version metadata and output
expression IDs, retains column pruning, and disables SQL result caching for
rewritten searches.
- Existing explicit search TVF SQL-filter behavior is preserved.
### Validation
- branch-4.2 FE production and test compilation completed. The
non-movable-projection counterexample was observed failing before the fix; the
final focused suite passed all 128 tests, including 14 optimizer tests.
- FE Checkstyle passed.
- Changed BE production and test translation units passed C++ syntax checks;
all affected C++ files passed clang-format 16 checks.
- Dependency download/MD5 and Foyer patch lifecycle tests passed.
- Reused the exact pinned lance-c revision rebuilt with the Foyer patch;
native runtime smoke tests against that library passed for high-bit UINT64 row
IDs, vector allowlists, empty allowlists, and prepared FTS allowlists with
unchanged BM25 scores.
- Added BE tests for query-local cache reuse, empty masks, the broad-filter
fallback retaining the nearest row, and native NULL-vector/NaN-distance
exclusion for both L2 and dot. Added an external-table regression suite
comparing automatic SQL with explicit TVFs and scalar distance values.
- Full BE unit-test execution and cluster regression execution remain for
CI; they were not run locally.
### Release note
Support automatic native Lance search for eligible approximate vector Top-N
and MATCH/BM25 SQL on Lance external tables.
### Check List (For Author)
- Test
- [x] Regression test added (execution pending CI)
- [x] Unit Test added (FE passed; BE execution pending CI)
- [x] Manual native API smoke tests
- Behavior changed:
- [x] Yes. Eligible approximate vector queries use native candidate
semantics (including the NULL/NaN differences above); eligible scored MATCH
queries become supported.
- Does this need documentation?
- [x] Yes. The SQL forms and current boundaries are described above;
user documentation should accompany the feature release.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label
--
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]
