You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "xuzifu666 (via GitHub)" <gi...@apache.org> on 2026/05/20 12:24:00 UTC
[PR] [common] Introduce RTreeFileIndex for query optimization [paimon]
xuzifu666 opened a new pull request, #7919:
URL: https://github.com/apache/paimon/pull/7919
### Purpose
Paimon currently does not support rtree indexes. Refer to this paper https://postgis.net/docs/support/rtree.pdf for implementation instructions on how to implement this index.
The following are the relevant benchmark test results:
### Hardware Configuration
- **CPU**: MacBook Pro (M-series processor)
- **Memory**: 16GB LPDDR5
- **Operating System**: macOS 14.x
### Software Configuration
- **Java Version**: OpenJDK 11+
- **Build**: Maven 3.8.x
-
### Test Parameters
- **Warmup Iterations**: 3
- **Benchmark Iterations**: 10
- **Query Count**: 1000-10000 queries
- **Random Seed**: 42 (for reproducibility)
**Query Performance (10,000 queries)**
```
R-Tree: 0.47 µs per query
Linear Scan: 464.41 µs per query
Speedup: 985.58×
Average results per query: 20 records
```
**Analysis by Dataset Size**
<!DOCTYPE html>
Dataset Size | R-Tree (µs) | Linear Scan (µs) | Speedup | Query Selectivity
-- | -- | -- | -- | --
1K | 0.20 | 14.90 | 75× | 2%
10K | 0.12 | 50.24 | 403× | 2%
100K | 0.35 | 492.44 | 1407× | 2%
1M | 0.39 | 495.25 | 1279× | 2%
<!DOCTYPE html>
Query Type | Area Size | R-Tree (µs) | Linear Scan (µs) | Speedup | Selectivity
-- | -- | -- | -- | -- | --
Small | 500×500 | 0.22 | 366.27 | 1684× | 0.02%
Medium | 1500×1500 | 0.21 | 400.52 | 1899× | 0.02%
Large | 5000×5000 | 0.28 | 556.48 | 1997× | 0.03%
**Point Query vs Range Query**
Search Performance on 100K Dataset:
```
Point queries (1000): 303.76 µs/query (with warmup optimization)
Range queries (100): 357.04 µs/query
Linear scan (100 scans): 65170.62 µs/scan
```
Improvement vs Linear Scan:
Point query: 214× speedup
Range query: 182× speedup
Sequential Data Access Pattern
```
1M grid data (1000×1000 points)
Average query time: 1.54 µs
Results returned: 30 records
Performance Characteristics:
- First query: 8.38 µs (cache warmup)
- Subsequent queries: 0.67-0.88 µs (steady state)
```
### Tests
# Run comparison benchmark
java -cp paimon-common/target/test-classes:paimon-common/target/classes \
org.apache.paimon.fileindex.rtree.RTreeVsLinearScanBenchmark
# Run detailed benchmark
java -cp paimon-common/target/test-classes:paimon-common/target/classes \
org.apache.paimon.fileindex.rtree.RTreeBenchmark
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "xuzifu666 (via GitHub)" <gi...@apache.org>.
xuzifu666 commented on PR #7919:
URL: https://github.com/apache/paimon/pull/7919#issuecomment-4514611557
> Thanks for the update. I found two blocking correctness/contract issues in the current head (`a4143bf63109`).
>
> 1. `RTreeFileIndexWriter` does not accept the object type passed by the real file-index write path for `ARRAY<DOUBLE>` columns. `DataFileIndexWriter.FileIndexMaintainer.write()` calls `fileIndexWriter.writeRecord(getter.getFieldOrNull(row))`, so an array field is passed as Paimon's `InternalArray` implementation, e.g. `GenericArray` / binary array, not as `double[]` or `java.util.List`. However, `RTreeFileIndexWriter.extractPoint()` only handles `List` and `double[]`. A normal write through the file-index path can therefore fail with:
> ```
> Cannot extract point from: org.apache.paimon.data.GenericArray
> ```
> 2. Production deserialization still loses the leaf flag for non-root nodes. `RTreeFileIndexReader.deserializeNode()` only calls `node.setLeaf(isLeaf)` for the root. Child nodes are always created with `new RTreeNode(..., false)`, and the recursive call does not update their serialized `isLeaf` value. As a result, leaf children under an internal node remain `isLeaf=false`; after serializing a multi-level tree with `RTreeFileIndexWriter` and reading it back with `RTreeFileIndex.createReader()`, an equality query for an existing point can return `SKIP`.
>
> I reproduced both with a small contract test:
>
> * `writer.writeRecord(new GenericArray(new double[] {1.0, 2.0}))` throws from `RTreeFileIndexWriter.extractPoint()`.
> * Writing 200 points, serializing with `RTreeFileIndexWriter`, deserializing with the production `RTreeFileIndexReader`, and querying `[50.0, 50.0]` returns no match.
>
> The existing tests pass because they mostly call `writer.write(new double[] {...})` directly, bypassing `FileIndexWriter.writeRecord()`, and `RTreeSerializationTest` uses its own test deserializer that constructs nodes with the serialized `isLeaf` flag, bypassing the production reader bug.
>
> Please fix these before merge:
>
> 1. Make the writer handle Paimon's `InternalArray` for `ARRAY<DOUBLE>` values, and check whether reader literals need the same treatment.
> 2. Preserve `isLeaf` for every node during production deserialization, not only the root.
> 3. Add regression coverage through the real `FileIndexWriter.writeRecord()` / `RTreeFileIndex.createReader()` path.
Thank you for the suggestion！I made relevant changes, PTAL @leaves12138
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #7919:
URL: https://github.com/apache/paimon/pull/7919#discussion_r3278317535
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTree.java:
##########
@@ -0,0 +1,212 @@
+/*
+ * 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.fileindex.rtree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** R-Tree spatial index implementation. */
+public class RTree {
+ private RTreeNode root;
+ private final int dimensions;
+ private final int minEntries;
+ private final int maxEntries;
+ private int size;
+
+ public RTree(int dimensions, int maxEntries) {
+ this.dimensions = dimensions;
+ this.maxEntries = maxEntries;
+ this.minEntries = Math.max(2, maxEntries / 2);
+ this.root = new RTreeNode(dimensions, maxEntries, true);
+ this.size = 0;
+ }
+
+ public int getDimensions() {
+ return dimensions;
+ }
+
+ public int getMinEntries() {
+ return minEntries;
+ }
+
+ public int getMaxEntries() {
+ return maxEntries;
+ }
+
+ public RTreeNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(RTreeNode newRoot) {
+ this.root = newRoot;
+ }
+
+ public void setSize(int newSize) {
+ this.size = newSize;
+ }
+
+ public int getSize() {
+ return size;
+ }
+
+ public void insert(double[] point, int rowId) {
+ BoundingBox pointBox = BoundingBox.fromPoint(point);
+ insert(pointBox, rowId, root);
+ size++;
+ }
+
+ private void insert(BoundingBox bbox, int rowId, RTreeNode node) {
+ if (node.isLeaf()) {
+ node.addLeafEntry(new LeafEntry(rowId, bbox));
+
+ if (node.canSplit()) {
+ splitNode(node);
+ }
+ } else {
+ RTreeNode bestChild = chooseBestChild(node, bbox);
+ insert(bbox, rowId, bestChild);
+
+ if (bestChild.canSplit()) {
+ splitNode(bestChild);
+ }
+ node.getBoundingBox().expand(bbox);
+ }
+ }
+
+ private RTreeNode chooseBestChild(RTreeNode node, BoundingBox bbox) {
+ RTreeNode best = null;
+ double minExpansion = Double.POSITIVE_INFINITY;
+ double minArea = Double.POSITIVE_INFINITY;
+
+ for (RTreeNode child : node.getChildren()) {
+ double expansion = child.getBoundingBox().getExpansionArea(bbox);
+ double area = child.getBoundingBox().getArea();
+
+ if (expansion < minExpansion || (expansion == minExpansion && area < minArea)) {
+ minExpansion = expansion;
+ minArea = area;
+ best = child;
+ }
+ }
+
+ if (best == null) {
+ throw new IllegalStateException("No child found in non-leaf node");
+ }
+ return best;
+ }
+
+ private void splitNode(RTreeNode node) {
+ if (node.isLeaf()) {
+ splitLeafNode(node);
+ } else {
+ splitInternalNode(node);
+ }
+ }
+
+ private void splitLeafNode(RTreeNode node) {
+ List<LeafEntry> entries = new ArrayList<>(node.getLeafEntries());
+ node.getLeafRowIds().clear();
+ node.getLeafEntries().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, true);
+
+ int mid = entries.size() / 2;
+ for (int i = 0; i < mid; i++) {
+ node.addLeafEntry(entries.get(i));
+ }
+ for (int i = mid; i < entries.size(); i++) {
+ newNode.addLeafEntry(entries.get(i));
+ }
+
+ if (node == root) {
+ RTreeNode newRoot = new RTreeNode(dimensions, maxEntries, false);
+ newRoot.addChild(node);
+ newRoot.addChild(newNode);
+ root = newRoot;
+ } else {
+ adjustParent(node, newNode);
+ }
+ }
+
+ private void splitInternalNode(RTreeNode node) {
+ List<RTreeNode> children = new ArrayList<>(node.getChildren());
+ node.getChildren().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, false);
+
+ int mid = children.size() / 2;
+ for (int i = 0; i < mid; i++) {
+ node.addChild(children.get(i));
+ }
+ for (int i = mid; i < children.size(); i++) {
+ newNode.addChild(children.get(i));
+ }
+
+ if (node == root) {
+ RTreeNode newRoot = new RTreeNode(dimensions, maxEntries, false);
+ newRoot.addChild(node);
+ newRoot.addChild(newNode);
+ root = newRoot;
+ } else {
+ adjustParent(node, newNode);
+ }
+ }
+
+ private void adjustParent(RTreeNode node, RTreeNode newNode) {
+ RTreeNode parent = node.getParent();
+ if (parent == null) {
+ return;
+ }
+
+ parent.addChild(newNode);
+
+ if (parent.canSplit()) {
+ splitNode(parent);
+ }
+ }
+
+ public List<Integer> search(BoundingBox searchBox) {
+ List<Integer> results = new ArrayList<>();
+ search(searchBox, root, results);
+ return results;
+ }
+
+ private void search(BoundingBox searchBox, RTreeNode node, List<Integer> results) {
+ if (!node.getBoundingBox().intersects(searchBox)) {
+ return;
+ }
+
+ if (node.isLeaf()) {
+ for (Integer rowId : node.getLeafRowIds()) {
+ results.add(rowId);
Review Comment:
Directly joined without checking if entry.bbox intersects with searchBox
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTree.java:
##########
@@ -0,0 +1,212 @@
+/*
+ * 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.fileindex.rtree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** R-Tree spatial index implementation. */
+public class RTree {
+ private RTreeNode root;
+ private final int dimensions;
+ private final int minEntries;
+ private final int maxEntries;
+ private int size;
+
+ public RTree(int dimensions, int maxEntries) {
+ this.dimensions = dimensions;
+ this.maxEntries = maxEntries;
+ this.minEntries = Math.max(2, maxEntries / 2);
+ this.root = new RTreeNode(dimensions, maxEntries, true);
+ this.size = 0;
+ }
+
+ public int getDimensions() {
+ return dimensions;
+ }
+
+ public int getMinEntries() {
+ return minEntries;
+ }
+
+ public int getMaxEntries() {
+ return maxEntries;
+ }
+
+ public RTreeNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(RTreeNode newRoot) {
+ this.root = newRoot;
+ }
+
+ public void setSize(int newSize) {
+ this.size = newSize;
+ }
+
+ public int getSize() {
+ return size;
+ }
+
+ public void insert(double[] point, int rowId) {
+ BoundingBox pointBox = BoundingBox.fromPoint(point);
+ insert(pointBox, rowId, root);
+ size++;
+ }
+
+ private void insert(BoundingBox bbox, int rowId, RTreeNode node) {
+ if (node.isLeaf()) {
+ node.addLeafEntry(new LeafEntry(rowId, bbox));
+
+ if (node.canSplit()) {
+ splitNode(node);
+ }
+ } else {
+ RTreeNode bestChild = chooseBestChild(node, bbox);
+ insert(bbox, rowId, bestChild);
+
+ if (bestChild.canSplit()) {
+ splitNode(bestChild);
+ }
+ node.getBoundingBox().expand(bbox);
+ }
+ }
+
+ private RTreeNode chooseBestChild(RTreeNode node, BoundingBox bbox) {
+ RTreeNode best = null;
+ double minExpansion = Double.POSITIVE_INFINITY;
+ double minArea = Double.POSITIVE_INFINITY;
+
+ for (RTreeNode child : node.getChildren()) {
+ double expansion = child.getBoundingBox().getExpansionArea(bbox);
+ double area = child.getBoundingBox().getArea();
+
+ if (expansion < minExpansion || (expansion == minExpansion && area < minArea)) {
+ minExpansion = expansion;
+ minArea = area;
+ best = child;
+ }
+ }
+
+ if (best == null) {
+ throw new IllegalStateException("No child found in non-leaf node");
+ }
+ return best;
+ }
+
+ private void splitNode(RTreeNode node) {
+ if (node.isLeaf()) {
+ splitLeafNode(node);
+ } else {
+ splitInternalNode(node);
+ }
+ }
+
+ private void splitLeafNode(RTreeNode node) {
+ List<LeafEntry> entries = new ArrayList<>(node.getLeafEntries());
+ node.getLeafRowIds().clear();
+ node.getLeafEntries().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, true);
+
+ int mid = entries.size() / 2;
Review Comment:
This completely disregards spatial location. The correct R-Tree splitting should minimize the MBR overlap between two result nodes, otherwise a large number of nodes will "intersect" during queries, degenerating into linear scans.
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTreeFileIndexReader.java:
##########
@@ -0,0 +1,141 @@
+/*
+ * 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.fileindex.rtree;
+
+import org.apache.paimon.fileindex.FileIndexReader;
+import org.apache.paimon.fileindex.FileIndexResult;
+import org.apache.paimon.fs.SeekableInputStream;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.predicate.FieldRef;
+import org.apache.paimon.utils.RoaringBitmap32;
+
+import java.io.DataInputStream;
+import java.io.IOException;
+import java.util.List;
+
+/** Reader for R-Tree file index. */
+public class RTreeFileIndexReader extends FileIndexReader {
+
+ private final SeekableInputStream stream;
+ private final int start;
+ private final Options options;
+ private RTree rtree;
+ private int dimensions;
+ private int maxEntries;
+ private int treeSize;
+
+ public RTreeFileIndexReader(SeekableInputStream stream, int start, Options options)
+ throws IOException {
+ this.stream = stream;
+ this.start = start;
+ this.options = options;
+ deserializeRTree();
+ }
+
+ private void deserializeRTree() throws IOException {
+ stream.seek(start);
+ DataInputStream dis = new DataInputStream(stream);
+
+ this.dimensions = dis.readInt();
+ this.maxEntries = dis.readInt();
+ this.treeSize = dis.readInt();
+
+ this.rtree = new RTree(dimensions, maxEntries);
+
+ if (treeSize > 0) {
+ deserializeNodes(dis, rtree);
+ }
+ }
+
+ private void deserializeNodes(DataInputStream dis, RTree tree) throws IOException {
+ RTreeNode root = tree.getRoot();
+ deserializeNode(dis, root, true);
+ }
+
+ private void deserializeNode(DataInputStream dis, RTreeNode node, boolean isRoot)
+ throws IOException {
+ boolean isLeaf = dis.readBoolean();
+ int entryCount = dis.readInt();
+
+ BoundingBox bbox = BoundingBox.deserialize(dis, dimensions);
+ node.getBoundingBox().expand(bbox);
+
+ if (isLeaf) {
+ for (int i = 0; i < entryCount; i++) {
+ int rowId = dis.readInt();
+ BoundingBox entryBbox = BoundingBox.deserialize(dis, dimensions);
+ node.addLeafEntry(new LeafEntry(rowId, entryBbox));
+ }
+ } else {
+ for (int i = 0; i < entryCount; i++) {
+ RTreeNode child = new RTreeNode(dimensions, maxEntries, false);
+ node.addChild(child);
Review Comment:
RTreeNode.isLeaf is final. When the RTree constructor creates root, isLeaf=true. However, during deserialization, if the root of the tree is an internal node, the deserialization code will add children to the node with isLeaf=true. Afterwards, when searching, node. isLeaf() returns true and will look for leafRowIds instead of recursive children. The deserialized tree cannot be queried correctly at all.
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTreeFileIndex.java:
##########
@@ -0,0 +1,58 @@
+/*
+ * 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.fileindex.rtree;
+
+import org.apache.paimon.fileindex.FileIndexReader;
+import org.apache.paimon.fileindex.FileIndexWriter;
+import org.apache.paimon.fileindex.FileIndexer;
+import org.apache.paimon.fs.SeekableInputStream;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.types.DataType;
+
+/** The implementation of R-Tree file index. */
+public class RTreeFileIndex implements FileIndexer {
Review Comment:
As a File Index, all data is already known at the time of writing, and the quality of the tree constructed by inserting each item is much lower than that of STR (Sort Tile Recursive) bulk loading
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "xuzifu666 (via GitHub)" <gi...@apache.org>.
xuzifu666 commented on PR #7919:
URL: https://github.com/apache/paimon/pull/7919#issuecomment-4504851433
@JingsongLi Thank you for the review! Your comments are very helpful, and I will refine them based on these issues.
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "xuzifu666 (via GitHub)" <gi...@apache.org>.
xuzifu666 commented on code in PR #7919:
URL: https://github.com/apache/paimon/pull/7919#discussion_r3279729702
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTree.java:
##########
@@ -0,0 +1,212 @@
+/*
+ * 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.fileindex.rtree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** R-Tree spatial index implementation. */
+public class RTree {
+ private RTreeNode root;
+ private final int dimensions;
+ private final int minEntries;
+ private final int maxEntries;
+ private int size;
+
+ public RTree(int dimensions, int maxEntries) {
+ this.dimensions = dimensions;
+ this.maxEntries = maxEntries;
+ this.minEntries = Math.max(2, maxEntries / 2);
+ this.root = new RTreeNode(dimensions, maxEntries, true);
+ this.size = 0;
+ }
+
+ public int getDimensions() {
+ return dimensions;
+ }
+
+ public int getMinEntries() {
+ return minEntries;
+ }
+
+ public int getMaxEntries() {
+ return maxEntries;
+ }
+
+ public RTreeNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(RTreeNode newRoot) {
+ this.root = newRoot;
+ }
+
+ public void setSize(int newSize) {
+ this.size = newSize;
+ }
+
+ public int getSize() {
+ return size;
+ }
+
+ public void insert(double[] point, int rowId) {
+ BoundingBox pointBox = BoundingBox.fromPoint(point);
+ insert(pointBox, rowId, root);
+ size++;
+ }
+
+ private void insert(BoundingBox bbox, int rowId, RTreeNode node) {
+ if (node.isLeaf()) {
+ node.addLeafEntry(new LeafEntry(rowId, bbox));
+
+ if (node.canSplit()) {
+ splitNode(node);
+ }
+ } else {
+ RTreeNode bestChild = chooseBestChild(node, bbox);
+ insert(bbox, rowId, bestChild);
+
+ if (bestChild.canSplit()) {
+ splitNode(bestChild);
+ }
+ node.getBoundingBox().expand(bbox);
+ }
+ }
+
+ private RTreeNode chooseBestChild(RTreeNode node, BoundingBox bbox) {
+ RTreeNode best = null;
+ double minExpansion = Double.POSITIVE_INFINITY;
+ double minArea = Double.POSITIVE_INFINITY;
+
+ for (RTreeNode child : node.getChildren()) {
+ double expansion = child.getBoundingBox().getExpansionArea(bbox);
+ double area = child.getBoundingBox().getArea();
+
+ if (expansion < minExpansion || (expansion == minExpansion && area < minArea)) {
+ minExpansion = expansion;
+ minArea = area;
+ best = child;
+ }
+ }
+
+ if (best == null) {
+ throw new IllegalStateException("No child found in non-leaf node");
+ }
+ return best;
+ }
+
+ private void splitNode(RTreeNode node) {
+ if (node.isLeaf()) {
+ splitLeafNode(node);
+ } else {
+ splitInternalNode(node);
+ }
+ }
+
+ private void splitLeafNode(RTreeNode node) {
+ List<LeafEntry> entries = new ArrayList<>(node.getLeafEntries());
+ node.getLeafRowIds().clear();
+ node.getLeafEntries().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, true);
+
+ int mid = entries.size() / 2;
+ for (int i = 0; i < mid; i++) {
+ node.addLeafEntry(entries.get(i));
+ }
+ for (int i = mid; i < entries.size(); i++) {
+ newNode.addLeafEntry(entries.get(i));
+ }
+
+ if (node == root) {
+ RTreeNode newRoot = new RTreeNode(dimensions, maxEntries, false);
+ newRoot.addChild(node);
+ newRoot.addChild(newNode);
+ root = newRoot;
+ } else {
+ adjustParent(node, newNode);
+ }
+ }
+
+ private void splitInternalNode(RTreeNode node) {
+ List<RTreeNode> children = new ArrayList<>(node.getChildren());
+ node.getChildren().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, false);
+
+ int mid = children.size() / 2;
+ for (int i = 0; i < mid; i++) {
+ node.addChild(children.get(i));
+ }
+ for (int i = mid; i < children.size(); i++) {
+ newNode.addChild(children.get(i));
+ }
+
+ if (node == root) {
+ RTreeNode newRoot = new RTreeNode(dimensions, maxEntries, false);
+ newRoot.addChild(node);
+ newRoot.addChild(newNode);
+ root = newRoot;
+ } else {
+ adjustParent(node, newNode);
+ }
+ }
+
+ private void adjustParent(RTreeNode node, RTreeNode newNode) {
+ RTreeNode parent = node.getParent();
+ if (parent == null) {
+ return;
+ }
+
+ parent.addChild(newNode);
+
+ if (parent.canSplit()) {
+ splitNode(parent);
+ }
+ }
+
+ public List<Integer> search(BoundingBox searchBox) {
+ List<Integer> results = new ArrayList<>();
+ search(searchBox, root, results);
+ return results;
+ }
+
+ private void search(BoundingBox searchBox, RTreeNode node, List<Integer> results) {
+ if (!node.getBoundingBox().intersects(searchBox)) {
+ return;
+ }
+
+ if (node.isLeaf()) {
+ for (Integer rowId : node.getLeafRowIds()) {
+ results.add(rowId);
Review Comment:
Changed as:
1. Enhanced ```RTree.java``` search() method:
a. Leaf nodes: Added per-entry checking entry.getBbox().intersects(searchBox)
b. Previously only checked node.getBoundingBox().intersects()
2. LeafEntry structure: Stores rowId + bbox for precision verification
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTreeFileIndex.java:
##########
@@ -0,0 +1,58 @@
+/*
+ * 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.fileindex.rtree;
+
+import org.apache.paimon.fileindex.FileIndexReader;
+import org.apache.paimon.fileindex.FileIndexWriter;
+import org.apache.paimon.fileindex.FileIndexer;
+import org.apache.paimon.fs.SeekableInputStream;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.types.DataType;
+
+/** The implementation of R-Tree file index. */
+public class RTreeFileIndex implements FileIndexer {
Review Comment:
My current alternative is:
1. Implemented STRBulkLoader (Sort-Tile-Recursive algorithm):
a. Sort entries by current dimension
b. Partition into vertical tiles (~maxEntries per tile)
c. Recursively process each tile with next dimension
d. Build tree bottom-up
2. Enhanced RTreeFileIndexWriter:
a. write() method: Collect entries into list
b. serializedBytes(): Use STRBulkLoader for batch tree construction
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi closed pull request #7919: [common] Introduce RTreeFileIndex for query optimization
URL: https://github.com/apache/paimon/pull/7919
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "leaves12138 (via GitHub)" <gi...@apache.org>.
leaves12138 commented on PR #7919:
URL: https://github.com/apache/paimon/pull/7919#issuecomment-4509237840
Thanks for the update. I found two blocking correctness/contract issues in the current head (`a4143bf63109`).
1. `RTreeFileIndexWriter` does not accept the object type passed by the real file-index write path for `ARRAY<DOUBLE>` columns. `DataFileIndexWriter.FileIndexMaintainer.write()` calls `fileIndexWriter.writeRecord(getter.getFieldOrNull(row))`, so an array field is passed as Paimon's `InternalArray` implementation, e.g. `GenericArray` / binary array, not as `double[]` or `java.util.List`. However, `RTreeFileIndexWriter.extractPoint()` only handles `List` and `double[]`. A normal write through the file-index path can therefore fail with:
```text
Cannot extract point from: org.apache.paimon.data.GenericArray
```
2. Production deserialization still loses the leaf flag for non-root nodes. `RTreeFileIndexReader.deserializeNode()` only calls `node.setLeaf(isLeaf)` for the root. Child nodes are always created with `new RTreeNode(..., false)`, and the recursive call does not update their serialized `isLeaf` value. As a result, leaf children under an internal node remain `isLeaf=false`; after serializing a multi-level tree with `RTreeFileIndexWriter` and reading it back with `RTreeFileIndex.createReader()`, an equality query for an existing point can return `SKIP`.
I reproduced both with a small contract test:
- `writer.writeRecord(new GenericArray(new double[] {1.0, 2.0}))` throws from `RTreeFileIndexWriter.extractPoint()`.
- Writing 200 points, serializing with `RTreeFileIndexWriter`, deserializing with the production `RTreeFileIndexReader`, and querying `[50.0, 50.0]` returns no match.
The existing tests pass because they mostly call `writer.write(new double[] {...})` directly, bypassing `FileIndexWriter.writeRecord()`, and `RTreeSerializationTest` uses its own test deserializer that constructs nodes with the serialized `isLeaf` flag, bypassing the production reader bug.
Please fix these before merge:
1. Make the writer handle Paimon's `InternalArray` for `ARRAY<DOUBLE>` values, and check whether reader literals need the same treatment.
2. Preserve `isLeaf` for every node during production deserialization, not only the root.
3. Add regression coverage through the real `FileIndexWriter.writeRecord()` / `RTreeFileIndex.createReader()` path.
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "xuzifu666 (via GitHub)" <gi...@apache.org>.
xuzifu666 commented on PR #7919:
URL: https://github.com/apache/paimon/pull/7919#issuecomment-4523781764
Currently all comments should have be addressed in my view, could you help to review it again when you have a time~ @JingsongLi
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "xuzifu666 (via GitHub)" <gi...@apache.org>.
xuzifu666 commented on code in PR #7919:
URL: https://github.com/apache/paimon/pull/7919#discussion_r3279728543
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTreeFileIndexReader.java:
##########
@@ -0,0 +1,141 @@
+/*
+ * 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.fileindex.rtree;
+
+import org.apache.paimon.fileindex.FileIndexReader;
+import org.apache.paimon.fileindex.FileIndexResult;
+import org.apache.paimon.fs.SeekableInputStream;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.predicate.FieldRef;
+import org.apache.paimon.utils.RoaringBitmap32;
+
+import java.io.DataInputStream;
+import java.io.IOException;
+import java.util.List;
+
+/** Reader for R-Tree file index. */
+public class RTreeFileIndexReader extends FileIndexReader {
+
+ private final SeekableInputStream stream;
+ private final int start;
+ private final Options options;
+ private RTree rtree;
+ private int dimensions;
+ private int maxEntries;
+ private int treeSize;
+
+ public RTreeFileIndexReader(SeekableInputStream stream, int start, Options options)
+ throws IOException {
+ this.stream = stream;
+ this.start = start;
+ this.options = options;
+ deserializeRTree();
+ }
+
+ private void deserializeRTree() throws IOException {
+ stream.seek(start);
+ DataInputStream dis = new DataInputStream(stream);
+
+ this.dimensions = dis.readInt();
+ this.maxEntries = dis.readInt();
+ this.treeSize = dis.readInt();
+
+ this.rtree = new RTree(dimensions, maxEntries);
+
+ if (treeSize > 0) {
+ deserializeNodes(dis, rtree);
+ }
+ }
+
+ private void deserializeNodes(DataInputStream dis, RTree tree) throws IOException {
+ RTreeNode root = tree.getRoot();
+ deserializeNode(dis, root, true);
+ }
+
+ private void deserializeNode(DataInputStream dis, RTreeNode node, boolean isRoot)
+ throws IOException {
+ boolean isLeaf = dis.readBoolean();
+ int entryCount = dis.readInt();
+
+ BoundingBox bbox = BoundingBox.deserialize(dis, dimensions);
+ node.getBoundingBox().expand(bbox);
+
+ if (isLeaf) {
+ for (int i = 0; i < entryCount; i++) {
+ int rowId = dis.readInt();
+ BoundingBox entryBbox = BoundingBox.deserialize(dis, dimensions);
+ node.addLeafEntry(new LeafEntry(rowId, entryBbox));
+ }
+ } else {
+ for (int i = 0; i < entryCount; i++) {
+ RTreeNode child = new RTreeNode(dimensions, maxEntries, false);
+ node.addChild(child);
Review Comment:
I changed ```private final boolean isLeaf``` → ```private boolean isLeaf```, added ```setLeaf(boolean)``` method, then called ```setLeaf()``` during deserialization to correct the root node's leaf flag.
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTree.java:
##########
@@ -0,0 +1,212 @@
+/*
+ * 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.fileindex.rtree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** R-Tree spatial index implementation. */
+public class RTree {
+ private RTreeNode root;
+ private final int dimensions;
+ private final int minEntries;
+ private final int maxEntries;
+ private int size;
+
+ public RTree(int dimensions, int maxEntries) {
+ this.dimensions = dimensions;
+ this.maxEntries = maxEntries;
+ this.minEntries = Math.max(2, maxEntries / 2);
+ this.root = new RTreeNode(dimensions, maxEntries, true);
+ this.size = 0;
+ }
+
+ public int getDimensions() {
+ return dimensions;
+ }
+
+ public int getMinEntries() {
+ return minEntries;
+ }
+
+ public int getMaxEntries() {
+ return maxEntries;
+ }
+
+ public RTreeNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(RTreeNode newRoot) {
+ this.root = newRoot;
+ }
+
+ public void setSize(int newSize) {
+ this.size = newSize;
+ }
+
+ public int getSize() {
+ return size;
+ }
+
+ public void insert(double[] point, int rowId) {
+ BoundingBox pointBox = BoundingBox.fromPoint(point);
+ insert(pointBox, rowId, root);
+ size++;
+ }
+
+ private void insert(BoundingBox bbox, int rowId, RTreeNode node) {
+ if (node.isLeaf()) {
+ node.addLeafEntry(new LeafEntry(rowId, bbox));
+
+ if (node.canSplit()) {
+ splitNode(node);
+ }
+ } else {
+ RTreeNode bestChild = chooseBestChild(node, bbox);
+ insert(bbox, rowId, bestChild);
+
+ if (bestChild.canSplit()) {
+ splitNode(bestChild);
+ }
+ node.getBoundingBox().expand(bbox);
+ }
+ }
+
+ private RTreeNode chooseBestChild(RTreeNode node, BoundingBox bbox) {
+ RTreeNode best = null;
+ double minExpansion = Double.POSITIVE_INFINITY;
+ double minArea = Double.POSITIVE_INFINITY;
+
+ for (RTreeNode child : node.getChildren()) {
+ double expansion = child.getBoundingBox().getExpansionArea(bbox);
+ double area = child.getBoundingBox().getArea();
+
+ if (expansion < minExpansion || (expansion == minExpansion && area < minArea)) {
+ minExpansion = expansion;
+ minArea = area;
+ best = child;
+ }
+ }
+
+ if (best == null) {
+ throw new IllegalStateException("No child found in non-leaf node");
+ }
+ return best;
+ }
+
+ private void splitNode(RTreeNode node) {
+ if (node.isLeaf()) {
+ splitLeafNode(node);
+ } else {
+ splitInternalNode(node);
+ }
+ }
+
+ private void splitLeafNode(RTreeNode node) {
+ List<LeafEntry> entries = new ArrayList<>(node.getLeafEntries());
+ node.getLeafRowIds().clear();
+ node.getLeafEntries().clear();
+ node.getBoundingBox().clear();
+
+ RTreeNode newNode = new RTreeNode(dimensions, maxEntries, true);
+
+ int mid = entries.size() / 2;
Review Comment:
I did these changes:
1. Implemented QuadraticSplit algorithm (2-step approach):
a. PickSeeds: Select two entries with maximum distance as initial seeds
b. Assign: Assign remaining entries to group with minimum bbox expansion
2. Implemented QuadraticSplitInternal: Same algorithm for internal node splitting
3. Modified ```RTree.java``` to use QuadraticSplit instead of linear splitting
--
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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #7919:
URL: https://github.com/apache/paimon/pull/7919#issuecomment-5523303889
Close this now. Feel free to create new 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] [common] Introduce RTreeFileIndex for query optimization [paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #7919:
URL: https://github.com/apache/paimon/pull/7919#discussion_r3458850433
##########
paimon-common/src/main/java/org/apache/paimon/fileindex/rtree/RTreeFileIndexWriter.java:
##########
@@ -0,0 +1,178 @@
+/*
+ * 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.fileindex.rtree;
+
+import org.apache.paimon.data.InternalArray;
+import org.apache.paimon.fileindex.FileIndexWriter;
+import org.apache.paimon.options.Options;
+import org.apache.paimon.types.ArrayType;
+import org.apache.paimon.types.DataType;
+import org.apache.paimon.types.DoubleType;
+
+import java.io.ByteArrayOutputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+/** Writer for R-Tree file index. */
+public class RTreeFileIndexWriter extends FileIndexWriter {
+
+ private final DataType dataType;
+ private final Options options;
+ private final int dimensions;
+ private final int maxEntries;
+ private final List<LeafEntry> entries;
+ private int rowNumber;
+
+ public RTreeFileIndexWriter(DataType dataType, Options options) {
+ this.dataType = dataType;
+ this.options = options;
+ this.dimensions =
+ options.getInteger(RTreeFileIndex.DIMENSIONS, RTreeFileIndex.DEFAULT_DIMENSIONS);
+ this.maxEntries =
+ options.getInteger(RTreeFileIndex.MAX_ENTRIES, RTreeFileIndex.DEFAULT_MAX_ENTRIES);
Review Comment:
`max-entries` and `dimensions` come from user table options, but they are not validated before the writer/bulk loader uses them. In particular, `max-entries=0` can hang the STR bulk loader: `buildInternalLevel` iterates with `i += maxEntries`, so a zero value never advances once there is at least one node; negative values also make the tiling math invalid. Could we reject invalid values here (for example `dimensions > 0` and `maxEntries > 1`, or whatever minimum the R-tree implementation requires) with a clear `IllegalArgumentException` before any data is written?
--
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