You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "Tan-JiaLiang (via GitHub)" <gi...@apache.org> on 2025/08/05 07:14:20 UTC
[PR] [core] Support TopN pushdown for append-only table [paimon]
Tan-JiaLiang opened a new pull request, #6028:
URL: https://github.com/apache/paimon/pull/6028
<!-- Please specify the module before the PR name: [core] ... or [flink] ... -->
### Purpose
<!-- Linking this pull request to the issue -->
<!-- What is the purpose of the change -->
1. Support the TopN pushdown in the core module.
2. Support the range-bitmap file index for topk/bottomk evaluation.
3. Currently, only append-only table are supported, deletion-vector table will be supported in the future.
This is the pre-processing PR that supports the TopN pushdown in other engines, e.g. Apache Spark.
Same as data filter, topn filter will filter the data as much as possible, but it is not guaranteed that it is a complete filter.
### Tests
<!-- List UT and IT cases to verify this change -->
### API and Format
<!-- Does this change affect API or storage format -->
### Documentation
<!-- Does this change introduce a new feature -->
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3177589448
@Tan-JiaLiang Can you provide some benchmark? How much performance has this PR improved.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3178989361
> After #6060.
>
> This is the Top1 benchmark based on the range-bitmap file index.
>
> ```
> Running benchmark: topn
> Running case: without-index-300-1
> Stopped after 1 iterations, 502 ms
> Running case: with-index-300-1
> Stopped after 1 iterations, 20 ms
>
> OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
> Apple M4 Pro
> topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------
> OPERATORTEST_topn_without-index-300-1 502 / 502 1991.7 502.1 1.0X
> OPERATORTEST_topn_with-index-300-1 21 / 21 48223.6 20.7 24.2X
>
>
>
>
> Running benchmark: topn
> Running case: without-index-3000-1
> Stopped after 1 iterations, 483 ms
> Running case: with-index-3000-1
> Stopped after 1 iterations, 19 ms
>
> OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
> Apple M4 Pro
> topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------
> OPERATORTEST_topn_without-index-3000-1 484 / 484 2066.9 483.8 1.0X
> OPERATORTEST_topn_with-index-3000-1 20 / 20 50313.5 19.9 24.3X
>
>
>
>
> Running benchmark: topn
> Running case: without-index-30000-1
> Stopped after 1 iterations, 495 ms
> Running case: with-index-30000-1
> Stopped after 1 iterations, 18 ms
>
> OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
> Apple M4 Pro
> topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------
> OPERATORTEST_topn_without-index-30000-1 496 / 496 2016.4 495.9 1.0X
> OPERATORTEST_topn_with-index-30000-1 19 / 19 53724.8 18.6 26.6X
>
>
>
>
> Running benchmark: topn
> Running case: without-index-300000-1
> Stopped after 1 iterations, 511 ms
> Running case: with-index-300000-1
> Stopped after 1 iterations, 19 ms
>
> OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
> Apple M4 Pro
> topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------
> OPERATORTEST_topn_without-index-300000-1 512 / 512 1953.7 511.8 1.0X
> OPERATORTEST_topn_with-index-300000-1 19 / 19 52073.4 19.2 26.7X
>
>
>
>
> Running benchmark: topn
> Running case: without-index-3000000-1
> Stopped after 1 iterations, 516 ms
> Running case: with-index-3000000-1
> Stopped after 1 iterations, 19 ms
>
> OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
> Apple M4 Pro
> topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------
> OPERATORTEST_topn_without-index-3000000-1 517 / 517 1935.1 516.8 1.0X
> OPERATORTEST_topn_with-index-3000000-1 19 / 19 52186.5 19.2 27.0X
> ```
This result looks amazing!
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3187892323
> Isn't this just max or min col?
@Zouxxyy
I just roughly thought about it. We might be handle all the TopN case(not only N=1).
This is what I can think of for the moment.
We needs min/max/null_count stats. Also, the stats maybe not exists. And It can not fit for deletion-vector table.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3155912726
> the range-bitmap file index is also marks the row position, so there is no false positive problem
> TopN filter can be divided into Local TopN Filter and Global TopN Filter
Got it, Thank you! @Tan-JiaLiang Without filter looks great!
As for with where condiction, like `where id > 10 order by c limit 100`, if after apply file index & filter we get 100 records, but if there are false positives (by filter), the result may wrong. So I feel that if there are where condictions, they must be completely filters.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3178022310
The following benchmarks are presented in tables with the following characteristics:
- using Apache Parquet as the table format
- 16 columns
- 1,000,000 rows
- cardinality values of 300, 3,000, 30,000, 300,000 and 3,000,000
This is the Top1 benchmark base the range-bitmap file index.
```text
Running benchmark: topn
Running case: without-index-300-1
Stopped after 1 iterations, 481 ms
Running case: with-index-300-1
Stopped after 1 iterations, 16 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-300-1 482 / 482 2075.7 481.8 1.0X
OPERATORTEST_topn_with-index-300-1 17 / 17 59512.6 16.8 28.7X
Running benchmark: topn
Running case: without-index-3000-1
Stopped after 1 iterations, 478 ms
Running case: with-index-3000-1
Stopped after 1 iterations, 17 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-3000-1 479 / 479 2089.7 478.5 1.0X
OPERATORTEST_topn_with-index-3000-1 18 / 18 56874.2 17.6 27.2X
Running benchmark: topn
Running case: without-index-30000-1
Stopped after 1 iterations, 495 ms
Running case: with-index-30000-1
Stopped after 1 iterations, 255 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-30000-1 496 / 496 2016.7 495.9 1.0X
OPERATORTEST_topn_with-index-30000-1 255 / 255 3919.6 255.1 1.9X
Running benchmark: topn
Running case: without-index-300000-1
Stopped after 1 iterations, 511 ms
Running case: with-index-300000-1
Stopped after 1 iterations, 245 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-300000-1 512 / 512 1954.4 511.7 1.0X
OPERATORTEST_topn_with-index-300000-1 246 / 246 4072.5 245.5 2.1X
Running benchmark: topn
Running case: without-index-3000000-1
Stopped after 1 iterations, 522 ms
Running case: with-index-3000000-1
Stopped after 1 iterations, 244 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-3000000-1 522 / 522 1914.8 522.2 1.0X
OPERATORTEST_topn_with-index-3000000-1 245 / 245 4089.7 244.5 2.1X
```
This is the EQUALS benchmark base the range-bitmap file index.
```text
Running benchmark: equals
Running case: without-index-300
Stopped after 5 iterations, 2379 ms
Running case: with-index-300
Stopped after 5 iterations, 2516 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
equals: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_equals_without-index-300 466 / 476 2147.9 465.6 1.0X
OPERATORTEST_equals_with-index-300 485 / 503 2063.3 484.6 1.0X
Running benchmark: equals
Running case: without-index-3000
Stopped after 5 iterations, 2420 ms
Running case: with-index-3000
Stopped after 5 iterations, 2636 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
equals: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_equals_without-index-3000 472 / 484 2120.8 471.5 1.0X
OPERATORTEST_equals_with-index-3000 519 / 527 1925.8 519.3 0.9X
Running benchmark: equals
Running case: without-index-30000
Stopped after 5 iterations, 2513 ms
Running case: with-index-30000
Stopped after 5 iterations, 1347 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
equals: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_equals_without-index-30000 466 / 503 2144.8 466.2 1.0X
OPERATORTEST_equals_with-index-30000 243 / 269 4121.3 242.6 1.9X
Running benchmark: equals
Running case: without-index-300000
Stopped after 5 iterations, 2502 ms
Running case: with-index-300000
Stopped after 5 iterations, 60 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
equals: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_equals_without-index-300000 465 / 501 2149.0 465.3 1.0X
OPERATORTEST_equals_with-index-300000 12 / 12 85956.2 11.6 40.0X
Running benchmark: equals
Running case: without-index-3000000
Stopped after 5 iterations, 2526 ms
Running case: with-index-3000000
Stopped after 5 iterations, 168 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
equals: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_equals_without-index-3000000 470 / 505 2126.9 470.2 1.0X
OPERATORTEST_equals_with-index-3000000 30 / 34 33297.0 30.0 15.7X
```
This is the RANGE benchmark base the range-bitmap file index.
```text
Running benchmark: between
Running case: without-index-300-0-100
Stopped after 5 iterations, 2409 ms
Running case: with-index-300-0-100
Stopped after 5 iterations, 2464 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
between: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_between_without-index-300-0-100 469 / 482 2130.8 469.3 1.0X
OPERATORTEST_between_with-index-300-0-100 482 / 493 2074.2 482.1 1.0X
Running benchmark: between
Running case: without-index-3000-0-100
Stopped after 5 iterations, 2412 ms
Running case: with-index-3000-0-100
Stopped after 5 iterations, 2533 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
between: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_between_without-index-3000-0-100 475 / 483 2106.4 474.7 1.0X
OPERATORTEST_between_with-index-3000-0-100 489 / 507 2044.2 489.2 1.0X
Running benchmark: between
Running case: without-index-30000-0-100
Stopped after 5 iterations, 2458 ms
Running case: with-index-30000-0-100
Stopped after 5 iterations, 2598 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
between: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_between_without-index-30000-0-100 475 / 492 2103.6 475.4 1.0X
OPERATORTEST_between_with-index-30000-0-100 507 / 520 1974.2 506.5 0.9X
Running benchmark: between
Running case: without-index-300000-0-100
Stopped after 5 iterations, 2514 ms
Running case: with-index-300000-0-100
Stopped after 5 iterations, 2563 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
between: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_between_without-index-300000-0-100 467 / 503 2142.8 466.7 1.0X
OPERATORTEST_between_with-index-300000-0-100 502 / 513 1992.0 502.0 0.9X
Running benchmark: between
Running case: without-index-3000000-0-100
Stopped after 5 iterations, 1466 ms
Running case: with-index-3000000-0-100
Stopped after 5 iterations, 1421 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
between: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_between_without-index-3000000-0-100 269 / 293 3713.3 269.3 1.0X
OPERATORTEST_between_with-index-3000000-0-100 251 / 284 3990.3 250.6 1.1X
```
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3178199326
After https://github.com/apache/paimon/pull/6060.
This is the Top1 benchmark based on the range-bitmap file index.
```text
Running benchmark: topn
Running case: without-index-300-1
Stopped after 1 iterations, 502 ms
Running case: with-index-300-1
Stopped after 1 iterations, 20 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-300-1 502 / 502 1991.7 502.1 1.0X
OPERATORTEST_topn_with-index-300-1 21 / 21 48223.6 20.7 24.2X
Running benchmark: topn
Running case: without-index-3000-1
Stopped after 1 iterations, 483 ms
Running case: with-index-3000-1
Stopped after 1 iterations, 19 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-3000-1 484 / 484 2066.9 483.8 1.0X
OPERATORTEST_topn_with-index-3000-1 20 / 20 50313.5 19.9 24.3X
Running benchmark: topn
Running case: without-index-30000-1
Stopped after 1 iterations, 495 ms
Running case: with-index-30000-1
Stopped after 1 iterations, 18 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-30000-1 496 / 496 2016.4 495.9 1.0X
OPERATORTEST_topn_with-index-30000-1 19 / 19 53724.8 18.6 26.6X
Running benchmark: topn
Running case: without-index-300000-1
Stopped after 1 iterations, 511 ms
Running case: with-index-300000-1
Stopped after 1 iterations, 19 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-300000-1 512 / 512 1953.7 511.8 1.0X
OPERATORTEST_topn_with-index-300000-1 19 / 19 52073.4 19.2 26.7X
Running benchmark: topn
Running case: without-index-3000000-1
Stopped after 1 iterations, 516 ms
Running case: with-index-3000000-1
Stopped after 1 iterations, 19 ms
OpenJDK 64-Bit Server VM 1.8.0_442-b06 on Mac OS X 15.6
Apple M4 Pro
topn: Best/Avg Time(ms) Row Rate(K/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_topn_without-index-3000000-1 517 / 517 1935.1 516.8 1.0X
OPERATORTEST_topn_with-index-3000000-1 19 / 19 52186.5 19.2 27.0X
```
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3187824619
> > @Tan-JiaLiang If it's only Top1, can our minmax stats also play a significant role? Save a lot of files during the planning phase.
>
> Very good suggestion! Maybe it not only siutable for Top1. I need to be considered in more detail, I think we can do it in another PR.
Isn't this just max or min col?
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2281254691
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,63 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[AppendOnlyFileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
Review Comment:
line 118-121 can be removed
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi closed pull request #6028: [core] Support TopN pushdown for append-only table
URL: https://github.com/apache/paimon/pull/6028
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3162591791
Hi @Zouxxyy, Do you have time to review this PR? Especially at the Spark implementations.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2268511446
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/FileIndexPredicate.java:
##########
@@ -168,4 +189,39 @@ public FileIndexResult visit(CompoundPredicate predicate) {
}
}
}
+
+ /** TopN test worker. */
+ private static class FileIndexTopNTest implements TopNVisitor<FileIndexResult> {
+
+ private final Set<FileIndexReader> readers;
+ private final FileIndexResult result;
+
+ public FileIndexTopNTest(Set<FileIndexReader> readers, FileIndexResult result) {
+ this.readers = readers;
+ this.result = result;
+ }
+
+ @Override
+ public FileIndexResult visit(TopN topN) {
+ for (FileIndexReader reader : readers) {
+ FileIndexResult ret = reader.visitTopN(topN, result);
+ if (!REMAIN.equals(ret)) {
+ ret.remain();
Review Comment:
The call to `ret.remain()` appears to be a side effect that doesn't use the return value. This should likely be checking the return value or this line may be unnecessary if `remain()` is meant to be called for side effects only.
```suggestion
```
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,63 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[AppendOnlyFileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = orders.head.expression() match {
+ case nr: NamedReference => nr.fieldNames.mkString(".")
+ case _ => return false
+ }
+
+ val rowType = table.rowType()
+ if (rowType.notContainsField(fieldName)) {
+ return false
+ }
+
+ val field = rowType.getField(fieldName)
+ val ref = new FieldRef(field.id(), field.name(), field.`type`())
+
+ val nullOrdering = order.nullOrdering() match {
+ case expressions.NullOrdering.NULLS_LAST => NullOrdering.NULLS_LAST
+ case expressions.NullOrdering.NULLS_FIRST => NullOrdering.NULLS_FIRST
+ case _ => return false
+ }
+
+ val direction = order.direction() match {
+ case expressions.SortDirection.DESCENDING => SortDirection.DESCENDING
+ case expressions.SortDirection.ASCENDING => SortDirection.ASCENDING
+ case _ => return false
+ }
+
+ val sort = new SortValue(ref, direction, nullOrdering)
+ pushDownTopN = Some(new TopN(Collections.singletonList(sort), limit))
+
+ // just make the best effort to push down TopN
+ false
Review Comment:
The pushDownTopN assignment should check if the TopN was successfully created and validated before setting it. Consider validating the TopN construction and only setting it if valid, or return true to indicate successful pushdown.
```suggestion
val topN = new TopN(Collections.singletonList(sort), limit)
// Validate TopN before assignment (assuming TopN has a valid() or isValid() method, otherwise just assign)
// If TopN has a validation method, use it. Otherwise, assume construction is always valid.
// For demonstration, let's assume TopN has a valid() method. If not, remove the check.
if (topN.isValid()) {
pushDownTopN = Some(topN)
true
} else {
false
}
```
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/BitSliceIndexBitmap.java:
##########
@@ -151,7 +151,84 @@ public RoaringBitmap32 gte(int code) {
return gt(code - 1);
}
+ public RoaringBitmap32 topK(int k, @Nullable RoaringBitmap32 foundSet) {
+ if (k == 0 || (foundSet != null && foundSet.isEmpty())) {
+ return new RoaringBitmap32();
+ }
+
+ if (k < 0) {
+ throw new IllegalArgumentException("the k param can not be negative in topK, k=" + k);
+ }
+
+ RoaringBitmap32 g = new RoaringBitmap32();
+ RoaringBitmap32 e = isNotNull(foundSet);
+ if (e.getCardinality() <= k) {
+ return e;
+ }
+
+ loadSlices(0, slices.length);
+ for (int i = slices.length - 1; i >= 0; i--) {
+ RoaringBitmap32 x = RoaringBitmap32.or(g, RoaringBitmap32.and(e, getSlice(i)));
+ long n = x.getCardinality();
+ if (n > k) {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ } else if (n < k) {
+ g = x;
+ e = RoaringBitmap32.andNot(e, getSlice(i));
+ } else {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ break;
+ }
+ }
+
+ // only k results should be returned
+ RoaringBitmap32 f = RoaringBitmap32.or(g, e);
+ f.remove(e, f.getCardinality() - k);
Review Comment:
The `remove` method call could result in removing more elements than intended if `f.getCardinality() - k` is negative. Add a check to ensure the calculation is non-negative before calling remove.
```suggestion
f.remove(e, Math.max(0, f.getCardinality() - k));
```
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/BitSliceIndexBitmap.java:
##########
@@ -151,7 +151,84 @@ public RoaringBitmap32 gte(int code) {
return gt(code - 1);
}
+ public RoaringBitmap32 topK(int k, @Nullable RoaringBitmap32 foundSet) {
+ if (k == 0 || (foundSet != null && foundSet.isEmpty())) {
+ return new RoaringBitmap32();
+ }
+
+ if (k < 0) {
+ throw new IllegalArgumentException("the k param can not be negative in topK, k=" + k);
+ }
+
+ RoaringBitmap32 g = new RoaringBitmap32();
+ RoaringBitmap32 e = isNotNull(foundSet);
+ if (e.getCardinality() <= k) {
+ return e;
+ }
+
+ loadSlices(0, slices.length);
+ for (int i = slices.length - 1; i >= 0; i--) {
+ RoaringBitmap32 x = RoaringBitmap32.or(g, RoaringBitmap32.and(e, getSlice(i)));
+ long n = x.getCardinality();
+ if (n > k) {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ } else if (n < k) {
+ g = x;
+ e = RoaringBitmap32.andNot(e, getSlice(i));
+ } else {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ break;
+ }
+ }
+
+ // only k results should be returned
+ RoaringBitmap32 f = RoaringBitmap32.or(g, e);
+ f.remove(e, f.getCardinality() - k);
+ return f;
+ }
+
+ public RoaringBitmap32 bottomK(int k, @Nullable RoaringBitmap32 foundSet) {
+ if (k == 0 || (foundSet != null && foundSet.isEmpty())) {
+ return new RoaringBitmap32();
+ }
+
+ if (k < 0) {
+ throw new IllegalArgumentException(
+ "the k param can not be negative in bottomK, k=" + k);
+ }
+
+ RoaringBitmap32 g = new RoaringBitmap32();
+ RoaringBitmap32 e = isNotNull(foundSet);
+ if (e.getCardinality() <= k) {
+ return e;
+ }
+
+ loadSlices(0, slices.length);
+ for (int i = slices.length - 1; i >= 0; i--) {
+ RoaringBitmap32 x = RoaringBitmap32.or(g, RoaringBitmap32.andNot(e, getSlice(i)));
+ long n = x.getCardinality();
+ if (n > k) {
+ e = RoaringBitmap32.andNot(e, getSlice(i));
+ } else if (n < k) {
+ g = x;
+ e = RoaringBitmap32.and(e, getSlice(i));
+ } else {
+ e = RoaringBitmap32.andNot(e, getSlice(i));
+ break;
+ }
+ }
+
+ // only k results should be returned
+ RoaringBitmap32 f = RoaringBitmap32.or(g, e);
+ f.remove(e, f.getCardinality() - k);
Review Comment:
Similar to topK, the `remove` method call in bottomK could result in removing more elements than intended if `f.getCardinality() - k` is negative. Add a check to ensure the calculation is non-negative before calling remove.
```suggestion
f.remove(e, Math.max(0, f.getCardinality() - k));
```
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3193514748
Hi @Tan-JiaLiang , maybe we can have a separate PR to finish Top1 based on min/max statistics. And then, this PR can rebase merged master.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi merged PR #6028:
URL: https://github.com/apache/paimon/pull/6028
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3186752764
Also document TopN optimization in `/append-table/query-performance`.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3155097110
@Zouxxyy Thank you for raising this question. Others are also welcome to ask questions at any time.
I would like to answer this question based on my understanding and discuss the validity of this PR.
1. In the current design, there is one DataFile per FileIndex, so perform topk/bottomk by the FileIndex is applied to a single DataFile.
2. Like the deletion-vector, the range-bitmap file index is also marks the row position, so there is no false positive problem.
3. As with the WHERE condition, we should not fully pushdown the TopN predicate, because the file index may not exist in runtime even if the index has been set in the properties. If the FileIndex exists, at most N records will be returned by a single DataFile; if not, the entire DataFile will be read.
4. After reading all the DataFiles, the egine will perform Global TopN filtering and return the results.
In shorts, in my opinion, TopN filter can be divided into Local TopN Filter and Global TopN Filter, and the FileIndex can make the Local TopN FIlter's work better, because we can pushdown the FileIndex result to filter the Parquet file's Rowgroup and Page.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2269130818
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/BitSliceIndexBitmap.java:
##########
@@ -151,7 +151,84 @@ public RoaringBitmap32 gte(int code) {
return gt(code - 1);
}
+ public RoaringBitmap32 topK(int k, @Nullable RoaringBitmap32 foundSet) {
+ if (k == 0 || (foundSet != null && foundSet.isEmpty())) {
+ return new RoaringBitmap32();
+ }
+
+ if (k < 0) {
+ throw new IllegalArgumentException("the k param can not be negative in topK, k=" + k);
+ }
+
+ RoaringBitmap32 g = new RoaringBitmap32();
+ RoaringBitmap32 e = isNotNull(foundSet);
+ if (e.getCardinality() <= k) {
+ return e;
+ }
+
+ loadSlices(0, slices.length);
+ for (int i = slices.length - 1; i >= 0; i--) {
+ RoaringBitmap32 x = RoaringBitmap32.or(g, RoaringBitmap32.and(e, getSlice(i)));
+ long n = x.getCardinality();
+ if (n > k) {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ } else if (n < k) {
+ g = x;
+ e = RoaringBitmap32.andNot(e, getSlice(i));
+ } else {
+ e = RoaringBitmap32.and(e, getSlice(i));
+ break;
+ }
+ }
+
+ // only k results should be returned
+ RoaringBitmap32 f = RoaringBitmap32.or(g, e);
+ f.remove(e, f.getCardinality() - k);
Review Comment:
RoaringBitmap32#remove will return directly if the `f.getCardinality() - k` is negative.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3187611856
> @Tan-JiaLiang If it's only Top1, can our minmax stats also play a significant role? Save a lot of files during the planning phase.
Very good suggestion! Maybe it not only siutable for Top1. I need to be considered in more detail, I think we can do it in another PR.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2267146908
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,57 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[FileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = order.expression().asInstanceOf[NamedReference].fieldNames().mkString(".")
+ val rowType = table.rowType()
+ if (rowType.notContainsField(fieldName)) {
+ return false
+ }
+
+ val field = rowType.getField(fieldName)
+ val ref = new FieldRef(field.id(), field.name(), field.`type`())
+
+ val nullOrdering = order.nullOrdering() match {
+ case expressions.NullOrdering.NULLS_LAST => NullOrdering.NULLS_LAST
+ case _ => NullOrdering.NULLS_FIRST
Review Comment:
match all types otherwise return false
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3157511488
> If any where condition does not fully pushdown and we got the TopN condition, I think this is the engine bug.
I see, maybe we can also manually set the pushed topk filter to empty when we find "post scan filter is not empry" when integrating with spark paimon in the next step.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3154160916
Hi @Tan-JiaLiang , Can you have a full POC with Spark implementations?
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3154572083
> Same as the data filter, the topn filter will filter the data as much as possible, but it is not guaranteed that it is a complete filter
Just curious about what this means. For example, if we use `order by c limit 100`, then after file index filter we get 100 records, but there may be false positives, how can we ensure that there are at least 100 records after spark's filter?
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Zouxxyy (via GitHub)" <gi...@apache.org>.
Zouxxyy commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2267126681
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonBaseScan.scala:
##########
@@ -128,7 +128,22 @@ abstract class PaimonBaseScan(
} else {
""
}
- s"PaimonScan: [${table.name}]" + pushedFiltersStr +
+ val pushedTopNFilterStr = pushDownTopN
+ .map(
+ topN => {
+ val ordersStr = topN
Review Comment:
we can add a toString in topN
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,57 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[FileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = order.expression().asInstanceOf[NamedReference].fieldNames().mkString(".")
+ val rowType = table.rowType()
+ if (rowType.notContainsField(fieldName)) {
+ return false
+ }
+
+ val field = rowType.getField(fieldName)
+ val ref = new FieldRef(field.id(), field.name(), field.`type`())
+
+ val nullOrdering = order.nullOrdering() match {
+ case expressions.NullOrdering.NULLS_LAST => NullOrdering.NULLS_LAST
+ case _ => NullOrdering.NULLS_FIRST
Review Comment:
match all types otherwise exception
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,57 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[FileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = order.expression().asInstanceOf[NamedReference].fieldNames().mkString(".")
Review Comment:
```scala
val fieldName = orders.head.expression() match {
case nr: NamedReference => nr.fieldNames.mkString(".")
case _ => return false
}
```
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,57 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[FileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = order.expression().asInstanceOf[NamedReference].fieldNames().mkString(".")
+ val rowType = table.rowType()
+ if (rowType.notContainsField(fieldName)) {
+ return false
+ }
+
+ val field = rowType.getField(fieldName)
+ val ref = new FieldRef(field.id(), field.name(), field.`type`())
+
+ val nullOrdering = order.nullOrdering() match {
+ case expressions.NullOrdering.NULLS_LAST => NullOrdering.NULLS_LAST
+ case _ => NullOrdering.NULLS_FIRST
+ }
+
+ val direction = order.direction() match {
+ case expressions.SortDirection.DESCENDING => SortDirection.DESCENDING
+ case _ => SortDirection.ASCENDING
+ }
+
+ val sort = new SortValue(ref, direction, nullOrdering)
+ pushDownTopN = Some(new TopN(Collections.singletonList(sort), limit))
+
+ // just make the best effort to push down TopN
+ false
+ }
+
+ override def isPartiallyPushed: Boolean = super.isPartiallyPushed
Review Comment:
is this needed?
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2275236164
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/FileIndexPredicate.java:
##########
@@ -83,6 +88,22 @@ public FileIndexResult evaluate(@Nullable Predicate predicate) {
return result;
}
+ public FileIndexResult evaluate(@Nullable TopN topN, FileIndexResult result) {
Review Comment:
evaluateTopN
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/FileIndexPredicate.java:
##########
@@ -83,6 +88,22 @@ public FileIndexResult evaluate(@Nullable Predicate predicate) {
return result;
}
+ public FileIndexResult evaluate(@Nullable TopN topN, FileIndexResult result) {
+ if (topN == null || !result.remain()) {
+ return result;
+ }
+
+ // for now we only support single column.
+ List<SortValue> orders = topN.orders();
+ if (orders.size() != 1) {
+ return result;
+ }
+
+ String requiredName = orders.get(0).field().name();
+ Set<FileIndexReader> readers = reader.readColumnIndex(requiredName);
+ return new FileIndexTopNTest(readers, result).test(topN);
Review Comment:
Don't need to introduce `FileIndexTopNTest`. Just introduce a static method `evaluateTopN(Set<FileIndexReader> readers, , FileIndexResult result)`.
##########
paimon-common/src/main/java/org/apache/paimon/predicate/TopNVisitor.java:
##########
@@ -0,0 +1,25 @@
+/*
+ * 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.
+ */
+
+package org.apache.paimon.predicate;
+
+/** A visitor to visit {@link TopN}. */
+public interface TopNVisitor<T> {
Review Comment:
Don't need to introduce this interface.
##########
paimon-core/src/main/java/org/apache/paimon/io/FileIndexEvaluator.java:
##########
@@ -36,40 +37,62 @@ public static FileIndexResult evaluate(
FileIO fileIO,
TableSchema dataSchema,
List<Predicate> dataFilter,
+ TopN topN,
DataFilePathFactory dataFilePathFactory,
DataFileMeta file)
throws IOException {
- if (dataFilter != null && !dataFilter.isEmpty()) {
+ FileIndexResult result = FileIndexResult.REMAIN;
+ if ((dataFilter == null || dataFilter.isEmpty()) && topN == null) {
+ return result;
+ }
+
+ FileIndexPredicate predicate = null;
+ try {
byte[] embeddedIndex = file.embeddedIndex();
if (embeddedIndex != null) {
- try (FileIndexPredicate predicate =
- new FileIndexPredicate(embeddedIndex, dataSchema.logicalRowType())) {
- return predicate.evaluate(
- PredicateBuilder.and(dataFilter.toArray(new Predicate[0])));
+ predicate = new FileIndexPredicate(embeddedIndex, dataSchema.logicalRowType());
+ } else {
+ List<String> indexFiles =
+ file.extraFiles().stream()
+ .filter(
+ name ->
+ name.endsWith(
+ DataFilePathFactory.INDEX_PATH_SUFFIX))
+ .collect(Collectors.toList());
+ if (indexFiles.isEmpty()) {
+ return result;
}
- }
-
- List<String> indexFiles =
- file.extraFiles().stream()
- .filter(name -> name.endsWith(DataFilePathFactory.INDEX_PATH_SUFFIX))
- .collect(Collectors.toList());
- if (!indexFiles.isEmpty()) {
if (indexFiles.size() > 1) {
throw new RuntimeException(
"Found more than one index file for one data file: "
+ String.join(" and ", indexFiles));
}
- // go to file index check
- try (FileIndexPredicate predicate =
+ predicate =
new FileIndexPredicate(
dataFilePathFactory.toAlignedPath(indexFiles.get(0), file),
fileIO,
- dataSchema.logicalRowType())) {
- return predicate.evaluate(
- PredicateBuilder.and(dataFilter.toArray(new Predicate[0])));
- }
+ dataSchema.logicalRowType());
+ }
+
+ // data filter
+ if (dataFilter != null && !dataFilter.isEmpty()) {
+ result =
+ predicate.evaluate(
+ PredicateBuilder.and(dataFilter.toArray(new Predicate[0])));
+ }
+
+ // todo: We need to do more if the index filter supports pushdown.
+ // e.g. All pushdown index filters must exist and be evaluated.
+ // topN filter
+ if (dataFilter == null && topN != null) {
Review Comment:
You may need to use if else?
##########
paimon-core/src/main/java/org/apache/paimon/io/FileIndexEvaluator.java:
##########
@@ -36,40 +37,62 @@ public static FileIndexResult evaluate(
FileIO fileIO,
TableSchema dataSchema,
List<Predicate> dataFilter,
+ TopN topN,
DataFilePathFactory dataFilePathFactory,
DataFileMeta file)
throws IOException {
- if (dataFilter != null && !dataFilter.isEmpty()) {
+ FileIndexResult result = FileIndexResult.REMAIN;
+ if ((dataFilter == null || dataFilter.isEmpty()) && topN == null) {
Review Comment:
Introduce a isNullOrEmpty in ListUtils, and use it.
##########
paimon-common/src/main/java/org/apache/paimon/utils/RoaringBitmap32.java:
##########
@@ -105,6 +106,22 @@ public boolean intersects(long minimum, long supremum) {
return roaringBitmap.intersects(minimum, supremum);
}
+ public RoaringBitmap32 limit(int k) {
+ return new RoaringBitmap32(roaringBitmap.limit(k));
+ }
+
+ public void remove(RoaringBitmap32 from, long n) {
Review Comment:
This method name is very confusing. Just introduce a private method in `BitSliceIndexBitmap`.
##########
paimon-core/src/main/java/org/apache/paimon/io/FileIndexEvaluator.java:
##########
@@ -36,40 +37,62 @@ public static FileIndexResult evaluate(
FileIO fileIO,
TableSchema dataSchema,
List<Predicate> dataFilter,
+ TopN topN,
DataFilePathFactory dataFilePathFactory,
DataFileMeta file)
throws IOException {
- if (dataFilter != null && !dataFilter.isEmpty()) {
+ FileIndexResult result = FileIndexResult.REMAIN;
+ if ((dataFilter == null || dataFilter.isEmpty()) && topN == null) {
+ return result;
+ }
+
+ FileIndexPredicate predicate = null;
+ try {
byte[] embeddedIndex = file.embeddedIndex();
if (embeddedIndex != null) {
- try (FileIndexPredicate predicate =
- new FileIndexPredicate(embeddedIndex, dataSchema.logicalRowType())) {
- return predicate.evaluate(
- PredicateBuilder.and(dataFilter.toArray(new Predicate[0])));
+ predicate = new FileIndexPredicate(embeddedIndex, dataSchema.logicalRowType());
+ } else {
+ List<String> indexFiles =
+ file.extraFiles().stream()
+ .filter(
+ name ->
+ name.endsWith(
+ DataFilePathFactory.INDEX_PATH_SUFFIX))
+ .collect(Collectors.toList());
+ if (indexFiles.isEmpty()) {
+ return result;
}
- }
-
- List<String> indexFiles =
- file.extraFiles().stream()
- .filter(name -> name.endsWith(DataFilePathFactory.INDEX_PATH_SUFFIX))
- .collect(Collectors.toList());
- if (!indexFiles.isEmpty()) {
if (indexFiles.size() > 1) {
throw new RuntimeException(
"Found more than one index file for one data file: "
+ String.join(" and ", indexFiles));
}
- // go to file index check
- try (FileIndexPredicate predicate =
+ predicate =
new FileIndexPredicate(
dataFilePathFactory.toAlignedPath(indexFiles.get(0), file),
fileIO,
- dataSchema.logicalRowType())) {
- return predicate.evaluate(
- PredicateBuilder.and(dataFilter.toArray(new Predicate[0])));
- }
+ dataSchema.logicalRowType());
+ }
+
+ // data filter
+ if (dataFilter != null && !dataFilter.isEmpty()) {
Review Comment:
isNullOrEmpty
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3157267114
Thanks @Zouxxyy, I think I should provide more of an explanation.
> where id > 10 order by c limit 100
For this condition, because of the sub condition `where id > 10` does not fully pushdown, we can not get the condition `order by c limit 100` by engine(like Apache Spark). If any where condition does not fully pushdown and we got the TopN condition, I think this is the engine bug.
On this PR, I just support `order by c limit 100` pushdown and without any other where condition(This is because the WHERE condition is not fully pushed down on Apache Paimon, except for the partition key).
For example, we have a table name T.
```sql
CREATE TABLE T (
id INT,
name STRING,
age INT,
class_id INT,
score INT,
dt STRING
) PARTITIONED BY(dt)
```
On this case we can get the TopN predicate from the engine.
```sql
SELECT id, name, age
FROM T
ORDER BY score DESC
LIMIT 10
```
And this case can not. Because of Apache Paimon not fully pushdown the where condition currently.
```sql
SELECT id, name, age
FROM T
WHERE class_id = 10
ORDER BY score DESC
LIMIT 10
```
But on this case, because partition key can fully pushdown on engine, so we can get the TopN predicate on this example.
```sql
SELECT id, name, age
FROM T
WHERE dt = '20250806'
ORDER BY score DESC
LIMIT 10
```
When we get the TopN predicate on the SQL plan phase, we will try to load the file index during the execution phase. If it exists, we will evaluate it and push the result down into the DataFile. Otherwise, we will read the entire DataFile.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3178003102
> @Tan-JiaLiang Can you provide some benchmark? How much performance has this PR improved.
Hi, @JingsongLi
Originally, I had planned to split the PRs to support the TopN pushdown(I think I should create some tasks in issues next time.), as this requires changes to several modules.
For example:
1. Support TopN in the paimon-core module.
2. Apache Parquet format support pushdown the TopN result.
3. Add the range-bitmap pushdown benchmark.
4. Support the Apache Spark TopN pushdown.
I think this PR can cover points 1, 3 and 4. And I would like to discuss Parquet pushing down the TopN result in a separate PR.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2269126518
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/FileIndexPredicate.java:
##########
@@ -168,4 +189,39 @@ public FileIndexResult visit(CompoundPredicate predicate) {
}
}
}
+
+ /** TopN test worker. */
+ private static class FileIndexTopNTest implements TopNVisitor<FileIndexResult> {
+
+ private final Set<FileIndexReader> readers;
+ private final FileIndexResult result;
+
+ public FileIndexTopNTest(Set<FileIndexReader> readers, FileIndexResult result) {
+ this.readers = readers;
+ this.result = result;
+ }
+
+ @Override
+ public FileIndexResult visit(TopN topN) {
+ for (FileIndexReader reader : readers) {
+ FileIndexResult ret = reader.visitTopN(topN, result);
+ if (!REMAIN.equals(ret)) {
+ ret.remain();
Review Comment:
We need to trigger the calculation immediately. Because the FileIndexEvaluator#evaluate will close the FileIndexPredicate.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3186704342
@Tan-JiaLiang If it's only Top1, can our minmax stats also play a significant role? Save a lot of files during the planning phase.
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on PR #6028:
URL: https://github.com/apache/paimon/pull/6028#issuecomment-3193735476
> Hi @Tan-JiaLiang , maybe we can have a separate PR to finish Top1 based on min/max statistics, this is a more general optimization. And then, this PR can rebase merged master.
Hi @JingsongLi , I will open another PR to finish it.
Besides, the CI failed and It seems to be a network issue. Can you help to trigger the CI again?
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Support TopN pushdown for append-only table [paimon]
Posted by "Tan-JiaLiang (via GitHub)" <gi...@apache.org>.
Tan-JiaLiang commented on code in PR #6028:
URL: https://github.com/apache/paimon/pull/6028#discussion_r2268493105
##########
paimon-spark/paimon-spark-common/src/main/scala/org/apache/paimon/spark/PaimonScanBuilder.scala:
##########
@@ -90,6 +97,57 @@ class PaimonScanBuilder(table: InnerTable)
false
}
+ override def pushTopN(orders: Array[SortOrder], limit: Int): Boolean = {
+ if (hasPostScanPredicates) {
+ return false
+ }
+
+ if (!table.isInstanceOf[FileStoreTable]) {
+ return false
+ }
+
+ val coreOptions = CoreOptions.fromMap(table.options())
+ if (coreOptions.deletionVectorsEnabled()) {
+ return false
+ }
+
+ if (orders.length != 1) {
+ return false
+ }
+
+ val order = orders(0)
+ if (!order.expression().isInstanceOf[NamedReference]) {
+ return false
+ }
+
+ val fieldName = order.expression().asInstanceOf[NamedReference].fieldNames().mkString(".")
+ val rowType = table.rowType()
+ if (rowType.notContainsField(fieldName)) {
+ return false
+ }
+
+ val field = rowType.getField(fieldName)
+ val ref = new FieldRef(field.id(), field.name(), field.`type`())
+
+ val nullOrdering = order.nullOrdering() match {
+ case expressions.NullOrdering.NULLS_LAST => NullOrdering.NULLS_LAST
+ case _ => NullOrdering.NULLS_FIRST
+ }
+
+ val direction = order.direction() match {
+ case expressions.SortDirection.DESCENDING => SortDirection.DESCENDING
+ case _ => SortDirection.ASCENDING
+ }
+
+ val sort = new SortValue(ref, direction, nullOrdering)
+ pushDownTopN = Some(new TopN(Collections.singletonList(sort), limit))
+
+ // just make the best effort to push down TopN
+ false
+ }
+
+ override def isPartiallyPushed: Boolean = super.isPartiallyPushed
Review Comment:
Yes, see https://github.com/apache/paimon/actions/runs/16897561817/job/47870152334?pr=6028
--
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: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org