[
https://issues.apache.org/jira/browse/CALCITE-6763?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17911252#comment-17911252
]
Julian Hyde commented on CALCITE-6763:
--------------------------------------
Oops, you're right. 1 is the initial capacity. I now agree that your fix is an
improvement, so +1.
Since this issue is a performance fix, I would like it much more if it had a
benchmark. I would be surprised if your change gives a perceptible change in
running time. {{PriorityQueue.add}} is cheap - {{O(log N)}} - even if initial
capacity is 1.
In a benchmark with a large number of tiles, especially if those tiles have
many different distinct values for {{TileKey.dimensions}}, I think a
partially-ordered data structure would help. A possible data structure is
[class
PartiallyOrderedSet|https://calcite.apache.org/javadocAggregate/org/apache/calcite/util/PartiallyOrderedSet.html].
> Optimize logic to select the tiles with the fewest rows
> --------------------------------------------------------
>
> Key: CALCITE-6763
> URL: https://issues.apache.org/jira/browse/CALCITE-6763
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: xiaochen.zhou
> Priority: Minor
> Labels: pull-request-available
> Attachments: image-2025-01-08-12-39-52-295.png,
> image-2025-01-08-12-40-26-332.png
>
>
> Our current logic using a PriorityQueue to select the tile with the fewest
> rows when multiple tiles are available. However, there are several potential
> issues:
> 1. The PriorityQueue stores all satisfiable tiles. When the number of tiles
> is large, maintaining the heap structure during element insertion has a time
> complexity of O(log n), which also increases memory usage.
> 2. The initial size of the PriorityQueue is difficult to estimate and is
> currently set to 1, causing frequent resizing of the PriorityQueue.
> We can optimize the code by keeping only a single bestCandidate tile to
> improve performance.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
