You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 08a9dbb
Browse filesBrowse the repository at this point in the historyBrowse files
### What problem does this PR solve?
**TL;DR:** Introduce virtual slot ref to eliminate redundant computation
of common sub-expressions
### Problem to solve
Consider the following queries:
```sql
select funcC(funcA(colA)), funcB(funcA(colA)) from table;
```
```sql
select funcA(colA) as sub from table where funcB(funcA(colA)) > 0;
```
```sql
select l2_distance(colA, [10]) as distance from table where l2_distance(colA, [10]) > 0
```
The common characteristic of these SQL statements is that certain
expressions appear multiple times in different places—whether in the
projection, in predicates, or during index computation (e.g., for ANN
index in Q3). These identical repeated expressions are currently
computed multiple times, but they could actually be computed just once.
We introduce **virtual slot ref** to address this issue.
In the storage layer, we implement a `VirtualColumnIterator`. The
behavior of `VirtualColumnIterator` is identical to other
`ColumnIterator`s, except it is not used to read any physical column.
Instead, it is dedicated to reading the result of expressions computed
from the index (for example, the distance returned by an ANN index, or
in the future, the relevance score from a full-text index). Once an
expression result is computed via the index, we use
`VirtualColumnIterator::prepare_materialization` to store the data
source. If a segment does not have the corresponding index, the data
source of the `VirtualColumnIterator` will be a special `ColumnNothing`
type (this is an important design trick that allows virtual slot ref to
elegantly handle the case where a segment does not yet have the index
built).
We also modify `SegmentIterator`. Before processing each block, we first
initialize the positions of the virtual slot ref in the block as
`ColumnNothing`. Before actually returning a block, we check whether the
virtual slot ref have been materialized; if not, we execute the
expressions corresponding to the virtual slot ref (e.g., `l2_distance`
or a `score` function) to generate the actual virtual slot ref, ensuring
that every virtual column in the block returned to the computation layer
has been materialized.
For expression evaluation, we introduce `VirtualSlotRef`, which is
essentially `SlotRef` + `FunctionCall`. When the expression tree
executes a node of this type, it automatically checks whether the
corresponding expression has been materialized: if it has,
`VirtualSlotRef` behaves like a `SlotRef`; if it hasn’t, it behaves like
a `FunctionCall`.
### Modification on planner
Here’s an example to better illustrate the execution of virtual slot
ref:
```sql
select func(colA) from table where func(colA) > 0;
```
For this SQL, our current `ScanNode` is:
```
ScanNode {
predicates: func(colA[#0]) > 0
final projection: func(colA[#0])
final projection tuple id: 1
tuple_id: 0
}
TupleDesc[id=0]{
SlotDesc{id=0, col=colA)}
}
TupleDesc[id=1] {
SlotDesc{id=1, col=null, ..., type=float64)
}
```
After this pr, our plan will become:
```
ScanNode {
predicate: function(colA)[#1] > 0
final projection: function(colA)[#1]
final projection tuple id: 1
tuple_id: 0
}
TupleDesc[id=0]{
SlotDesc{id=0, col="colA")},
SlotDesc{id=1, col=virtual_column_1, expr=function1(colA[#0])}
}
TupleDesc[id=1] {
SlotDesc{id=2, name=virtual_column_1[#1])
}
```
Note that we added a `VirtualSlot` in Tuple 0, and other places that
originally required computing the expression are transformed to
reference this `VirtualSlot`. In this way, redundant computation of
common expressions is eliminated.
### Benchmark
disable the plan rules
```sql
mysql> set disable_nereids_rules='PUSH_DOWN_VIRTUAL_COLUMNS_INTO_OLAP_SCAN';
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT counterid, Count(*) AS hit_count, Count(DISTINCT userid) AS unique_users FROM hits WHERE ( Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) = 'GOOGLE.COM' OR Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) = 'GOOGLE.RU' OR Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) LIKE '%GOOGLE%' ) AND ( Length(Regexp_extract(referer, '^https?://([^/]+)', 1)) > 3 OR Regexp_extract(referer, '^https?://([^/]+)', 1) != ''
OR Regexp_extract(referer, '^https?://([^/]+)', 1) IS NOT NULL ) AND eventdate = '2013-07-15' GROUP BY counterid HAVING hit_count > 100 ORDER BY hit_count DESC LIMIT 20;
+-----------+-----------+--------------+
| counterid | hit_count | unique_users |
+-----------+-----------+--------------+
| 105857 | 1919075 | 1412926 |
| 117917 | 200018 | 50285 |
| 99062 | 114384 | 71408 |
| 1634 | 43839 | 14975 |
| 59 | 31328 | 6668 |
| 114157 | 28852 | 19729 |
| 62 | 22549 | 14130 |
| 1483 | 8425 | 5677 |
| 38 | 5436 | 1805 |
| 1060 | 4043 | 2948 |
| 76221 | 2060 | 1325 |
| 128858 | 1690 | 825 |
| 102847 | 1500 | 350 |
| 89761 | 1419 | 274 |
| 92040 | 1180 | 978 |
| 1089 | 1067 | 961 |
| 2004 | 880 | 698 |
| 1213 | 597 | 219 |
| 77729 | 448 | 108 |
| 71099 | 289 | 70 |
+-----------+-----------+--------------+
20 rows in set (1.50 sec)
```
reopen the rule:
```text
mysql> unset variable disable_nereids_rules;
--------------
unset variable disable_nereids_rules
--------------
Query OK, 0 rows affected (0.00 sec)
mysql> -- 查询 1: 分析从 Google 中获得最多点击的 20 个网站
mysql> SELECT counterid,
-> Count(*) AS hit_count,
-> Count(DISTINCT userid) AS unique_users
-> FROM hits
-> WHERE ( Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) = 'GOOGLE.COM'
-> OR Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) =
-> 'GOOGLE.RU'
-> OR Upper(Regexp_extract(referer, '^https?://([^/]+)', 1)) LIKE
-> '%GOOGLE%' )
-> AND ( Length(Regexp_extract(referer, '^https?://([^/]+)', 1)) > 3
-> OR Regexp_extract(referer, '^https?://([^/]+)', 1) != ''
-> OR Regexp_extract(referer, '^https?://([^/]+)', 1) IS NOT NULL )
-> AND eventdate = '2013-07-15'
-> GROUP BY counterid
-> HAVING hit_count > 100
-> ORDER BY hit_count DESC
-> LIMIT 20;
+-----------+-----------+--------------+
| counterid | hit_count | unique_users |
+-----------+-----------+--------------+
| 105857 | 1919075 | 1412926 |
| 117917 | 200018 | 50285 |
| 99062 | 114384 | 71408 |
| 1634 | 43839 | 14975 |
| 59 | 31328 | 6668 |
| 114157 | 28852 | 19729 |
| 62 | 22549 | 14130 |
| 1483 | 8425 | 5677 |
| 38 | 5436 | 1805 |
| 1060 | 4043 | 2948 |
| 76221 | 2060 | 1325 |
| 128858 | 1690 | 825 |
| 102847 | 1500 | 350 |
| 89761 | 1419 | 274 |
| 92040 | 1180 | 978 |
| 1089 | 1067 | 961 |
| 2004 | 880 | 698 |
| 1213 | 597 | 219 |
| 77729 | 448 | 108 |
| 71099 | 289 | 70 |
+-----------+-----------+--------------+
20 rows in set (0.57 sec)
```
About 300% optimization.
### TODO
In the future, we can leverage virtual slot ref to implement more
functionalities, including:
1. ANN Index
2. Relevance scoring based on full-text indexes
3. Generated Columns (of NOT ALWAYS type)
4. Index-Only Scan (which will require modifying SlotRef computation in
`SegmentIterator` to be pull-based)
5. CSE replace rule on FE is very basic, but enough to use for now. Need
a further modification on
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/PushDownVirtualColumnsIntoOlapScanTest.java
---
Co-authored-by: morrySnow <[email protected]>
0 commit comments