This is an automated email from the ASF dual-hosted git repository.
JingsongLi pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/paimon.git
The following commit(s) were added to refs/heads/master by this push:
new 0edf2c354b [python] Support BTree v2 posting list decoding (#10495)
0edf2c354b is described below
commit 0edf2c354bdb97d5bd9199d90e4b0737cec11d52
Author: QuakeWang <[email protected]>
AuthorDate: Mon Oct 12 21:25:58 2026 +0800
[python] Support BTree v2 posting list decoding (#10495)
---
.../globalindex/btree/btree_file_footer.py | 1 +
.../globalindex/btree/btree_index_reader.py | 27 +---
.../globalindex/btree/btree_posting_list.py | 77 ++++++++++
.../pypaimon/tests/btree_index_reader_test.py | 164 ++++++++++++++++++++-
.../pypaimon/tests/btree_posting_list_test.py | 111 ++++++++++++++
.../resources/btree/BTreeFixtureGenerator.java | 161 ++++++++++++++++++++
.../pypaimon/tests/resources/btree/README.md | 63 ++++++++
.../pypaimon/tests/resources/btree/expected.json | 7 +
.../tests/resources/btree/java-v1-bloom.btree | Bin 0 -> 2300 bytes
.../tests/resources/btree/java-v1-bloom.btree.meta | Bin 0 -> 19 bytes
.../resources/btree/java-v1-string-bloom.btree | Bin 0 -> 2296 bytes
.../btree/java-v1-string-bloom.btree.meta | Bin 0 -> 15 bytes
.../tests/resources/btree/java-v1-string.btree | Bin 0 -> 2290 bytes
.../resources/btree/java-v1-string.btree.meta | Bin 0 -> 15 bytes
.../pypaimon/tests/resources/btree/java-v1.btree | Bin 0 -> 2294 bytes
.../tests/resources/btree/java-v1.btree.meta | Bin 0 -> 19 bytes
.../tests/resources/btree/java-v2-bloom.btree | Bin 0 -> 324 bytes
.../tests/resources/btree/java-v2-bloom.btree.meta | Bin 0 -> 19 bytes
.../resources/btree/java-v2-string-bloom.btree | Bin 0 -> 320 bytes
.../btree/java-v2-string-bloom.btree.meta | Bin 0 -> 15 bytes
.../tests/resources/btree/java-v2-string.btree | Bin 0 -> 314 bytes
.../resources/btree/java-v2-string.btree.meta | Bin 0 -> 15 bytes
.../pypaimon/tests/resources/btree/java-v2.btree | Bin 0 -> 318 bytes
.../tests/resources/btree/java-v2.btree.meta | Bin 0 -> 19 bytes
.../pypaimon/tests/resources/btree/posting-1.bin | Bin 0 -> 2 bytes
.../pypaimon/tests/resources/btree/posting-2.bin | 1 +
.../pypaimon/tests/resources/btree/posting-3.bin | Bin 0 -> 28 bytes
.../pypaimon/tests/resources/btree/posting-4.bin | Bin 0 -> 28 bytes
.../pypaimon/tests/resources/btree/posting-5.bin | Bin 0 -> 28 bytes
.../tests/resources/btree/posting-high-buckets.bin | Bin 0 -> 47 bytes
paimon-python/pypaimon/utils/roaring_bitmap.py | 8 +
31 files changed, 597 insertions(+), 23 deletions(-)
diff --git a/paimon-python/pypaimon/globalindex/btree/btree_file_footer.py
b/paimon-python/pypaimon/globalindex/btree/btree_file_footer.py
index d50195f131..4b6940b0f6 100644
--- a/paimon-python/pypaimon/globalindex/btree/btree_file_footer.py
+++ b/paimon-python/pypaimon/globalindex/btree/btree_file_footer.py
@@ -47,6 +47,7 @@ class BTreeFileFooter:
MAGIC_NUMBER = 0x50425449
VERSION_1 = 1
+ VERSION_2 = 2
CURRENT_VERSION = VERSION_1
ENCODED_LENGTH = 52
diff --git a/paimon-python/pypaimon/globalindex/btree/btree_index_reader.py
b/paimon-python/pypaimon/globalindex/btree/btree_index_reader.py
index 8e9f21e6e3..007ccf4361 100644
--- a/paimon-python/pypaimon/globalindex/btree/btree_index_reader.py
+++ b/paimon-python/pypaimon/globalindex/btree/btree_index_reader.py
@@ -35,24 +35,10 @@ from pypaimon.globalindex.key_serializer import
KeySerializer
from pypaimon.utils.roaring_bitmap import RoaringBitmap64
from pypaimon.globalindex.btree.btree_file_footer import BTreeFileFooter
from pypaimon.globalindex.btree.sst_file_reader import SstFileReader
-from pypaimon.globalindex.memory_slice_input import MemorySliceInput
+from pypaimon.globalindex.btree.btree_posting_list import add_row_ids
from pypaimon.globalindex.sorted_file_meta_selector import
SortedFileMetaSelector
-def _deserialize_row_ids(data: bytes) -> List[int]:
- data_input = MemorySliceInput(data)
- length = data_input.read_var_len_int()
-
- if length <= 0:
- raise ValueError(f"Invalid row id length: {length}")
-
- row_ids = []
- for _ in range(length):
- row_ids.append(data_input.read_var_len_long())
-
- return row_ids
-
-
class BTreeIndexReader:
"""Synchronous index reader for a single BTree index file.
@@ -97,7 +83,7 @@ class BTreeIndexReader:
# Read footer to get index and bloom filter handles
self.footer = self._read_footer()
- if self.footer.version != BTreeFileFooter.VERSION_1:
+ if self.footer.version not in (BTreeFileFooter.VERSION_1,
BTreeFileFooter.VERSION_2):
raise ValueError(
f"Unsupported BTree index file version:
{self.footer.version}")
@@ -195,8 +181,7 @@ class BTreeIndexReader:
if difference > 0 or (not to_inclusive and difference == 0):
return result
- for row_id in _deserialize_row_ids(entry.value):
- result.add(row_id)
+ add_row_ids(entry.value, self.footer.version, result)
return result
@@ -255,8 +240,7 @@ class BTreeIndexReader:
for entry in self._entries_from(prefix):
if upper_bound is not None and entry.key >= upper_bound:
break
- for row_id in _deserialize_row_ids(entry.value):
- result.add(row_id)
+ add_row_ids(entry.value, self.footer.version, result)
return GlobalIndexResult.create(result)
def visit_ends_with(self, literal: object) -> Optional[GlobalIndexResult]:
@@ -282,8 +266,7 @@ class BTreeIndexReader:
result = RoaringBitmap64()
row_ids = self.reader.lookup(self.key_serializer.serialize(key))
if row_ids is not None:
- for row_id in _deserialize_row_ids(row_ids):
- result.add(row_id)
+ add_row_ids(row_ids, self.footer.version, result)
return result
def close(self) -> None:
diff --git a/paimon-python/pypaimon/globalindex/btree/btree_posting_list.py
b/paimon-python/pypaimon/globalindex/btree/btree_posting_list.py
new file mode 100644
index 0000000000..b9ba140ae8
--- /dev/null
+++ b/paimon-python/pypaimon/globalindex/btree/btree_posting_list.py
@@ -0,0 +1,77 @@
+# 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.
+
+"""Decode BTree postings into a query result bitmap."""
+
+from pypaimon.globalindex.btree.btree_file_footer import BTreeFileFooter
+from pypaimon.globalindex.memory_slice_input import MemorySliceInput
+from pypaimon.utils.roaring_bitmap import RoaringBitmap64
+
+
+_SINGLE = 0
+_DELTA_LIST = 1
+_ROARING = 2
+_LONG_MAX_VALUE = (1 << 63) - 1
+
+
+def _read_row_id(input_: MemorySliceInput) -> int:
+ row_id = input_.read_var_len_long()
+ if row_id > _LONG_MAX_VALUE:
+ raise ValueError(f"BTree row id exceeds Long.MAX_VALUE: {row_id}")
+ return row_id
+
+
+def add_row_ids(data: bytes, version: int, target: RoaringBitmap64) -> None:
+ """Accumulate a posting; malformed input raises instead of returning a
result."""
+ input_ = MemorySliceInput(data)
+ if version == BTreeFileFooter.VERSION_1:
+ count = input_.read_var_len_int()
+ if count <= 0:
+ raise ValueError(f"Invalid row id length: {count}")
+ for _ in range(count):
+ target.add(input_.read_var_len_long())
+ return
+
+ if version != BTreeFileFooter.VERSION_2:
+ raise ValueError(f"Unsupported BTree index file version: {version}")
+
+ type_ = input_.read_unsigned_byte()
+ if type_ == _SINGLE:
+ target.add(_read_row_id(input_))
+ elif type_ == _DELTA_LIST:
+ count = input_.read_var_len_int()
+ if count <= 1 or count > (1 << 31) - 1:
+ raise ValueError(f"Invalid delta BTree posting list length:
{count}")
+ row_id = _read_row_id(input_)
+ target.add(row_id)
+ for _ in range(count - 1):
+ delta = _read_row_id(input_)
+ if delta == 0:
+ raise ValueError("Invalid non-positive BTree row id delta: 0")
+ row_id += delta
+ if row_id > _LONG_MAX_VALUE:
+ raise ValueError(f"BTree row id exceeds Long.MAX_VALUE:
{row_id}")
+ target.add(row_id)
+ elif type_ == _ROARING:
+ bitmap =
RoaringBitmap64.deserialize(input_.read_slice(input_.available()))
+ if bitmap.is_empty():
+ raise ValueError("Invalid empty Roaring BTree posting list")
+ if bitmap.max() > _LONG_MAX_VALUE:
+ raise ValueError("BTree row id exceeds Long.MAX_VALUE")
+ target.or_inplace(bitmap)
+ else:
+ raise ValueError(f"Unknown BTree posting list type: {type_}")
diff --git a/paimon-python/pypaimon/tests/btree_index_reader_test.py
b/paimon-python/pypaimon/tests/btree_index_reader_test.py
index c1e396467e..9f8b9e8c9f 100644
--- a/paimon-python/pypaimon/tests/btree_index_reader_test.py
+++ b/paimon-python/pypaimon/tests/btree_index_reader_test.py
@@ -18,17 +18,24 @@
"""File-level tests for BTree reader versions and initialization cleanup."""
import io
+import json
import os
import struct
import tempfile
import unittest
+from concurrent.futures import ThreadPoolExecutor
+from pathlib import Path
+from unittest.mock import patch
from pypaimon.filesystem.local_file_io import LocalFileIO
from pypaimon.globalindex.btree.btree_file_footer import BTreeFileFooter
from pypaimon.globalindex.btree.btree_index_reader import BTreeIndexReader
from pypaimon.globalindex.btree.btree_index_writer import BTreeIndexWriter
+from pypaimon.globalindex.btree.lazy_filtered_btree_reader import
LazyFilteredBTreeReader
from pypaimon.globalindex.global_index_meta import GlobalIndexIOMeta
+from pypaimon.globalindex.global_index_reader import FieldRef
from pypaimon.globalindex.key_serializer import create_serializer
+from pypaimon.globalindex.offset_global_index_reader import
OffsetGlobalIndexReader
from pypaimon.globalindex.sorted_file_meta_selector import
SortedFileMetaSelector
from pypaimon.globalindex.sorted_index_file_meta import SortedIndexFileMeta
from pypaimon.schema.data_types import AtomicType
@@ -182,7 +189,7 @@ class BTreeIndexReaderTest(unittest.TestCase):
def test_unsupported_versions_rejected_before_sst_read(self):
for input_type in (_TrackingInput, _PreadInput):
- for version in (0, 2, 3, 0x80000000, 0xffffffff):
+ for version in (0, 3, 0x80000000, 0xffffffff):
with self.subTest(input_type=input_type, version=version):
data = self.data[:-8] + struct.pack('<I', version) +
self.data[-4:]
file_io = self._file_io(data, input_type)
@@ -251,5 +258,160 @@ class BTreeIndexReaderTest(unittest.TestCase):
self.serializer, file_io, '/unused', self.io_meta)
+class JavaBTreeIndexReaderTest(unittest.TestCase):
+
+ def setUp(self):
+ self.directory = Path(__file__).parent / 'resources' / 'btree'
+ self.serializer = create_serializer(AtomicType('INT'))
+ self.rows = {int(k): v for k, v in json.loads(
+ (self.directory / 'expected.json').read_text()).items()}
+
+ def _meta(self, version, bloom=False, string=False):
+ name = 'java-v%d%s%s.btree' % (version, '-string' if string else '',
'-bloom' if bloom else '')
+ data = (self.directory / name).read_bytes()
+ return data, GlobalIndexIOMeta(
+ name, len(data), (self.directory / (name + '.meta')).read_bytes())
+
+ def test_java_file_queries(self):
+ for version in (1, 2):
+ for bloom in (False, True):
+ for input_type in (_TrackingInput, _PreadInput):
+ with self.subTest(version=version, bloom=bloom,
input_type=input_type):
+ data, meta = self._meta(version, bloom)
+ file_io = _MemoryFileIO(data, input_type)
+ reader = BTreeIndexReader(self.serializer, file_io,
'/unused', meta)
+ try:
+ self.assertEqual(version, reader.footer.version)
+ self.assertEqual(bloom,
reader.footer.bloom_filter_handle is not None)
+ for key, expected in self.rows.items():
+ self.assertEqual(expected,
reader.visit_equal(key).results().to_list())
+ self.assertEqual([],
reader.visit_equal(6).results().to_list())
+ self.assertEqual([], reader.visit_between(6,
7).results().to_list())
+ self.assertEqual(
+ sorted(self.rows[2] + self.rows[3] +
self.rows[4]),
+ reader.visit_between(2, 4).results().to_list())
+ self.assertEqual(
+ self.rows[3], reader._range_query(2, 4, False,
False).to_list())
+ self.assertEqual(
+ sorted(self.rows[1] + self.rows[3]),
+ reader.visit_in([1, 3, 3, 6,
None]).results().to_list())
+ self.assertEqual(self.rows[1],
reader.visit_less_than(2).results().to_list())
+ self.assertEqual(self.rows[5],
reader.visit_greater_than(4).results().to_list())
+ self.assertEqual([999],
reader.visit_is_null().results().to_list())
+ self.assertEqual(
+ sorted(sum(self.rows.values(), [])),
+ reader.visit_is_not_null().results().to_list())
+ if version == 2:
+ iterator = reader.reader.create_iterator()
+ iterator.seek_to(self.serializer.serialize(1))
+ blocks = 0
+ keys = []
+ while True:
+ block = iterator.read_batch()
+ if block is None:
+ break
+ blocks += 1
+ while block.has_next():
+ entry = next(block)
+ key =
self.serializer.deserialize(entry.key)
+ keys.append(key)
+ self.assertEqual(
+ (self.directory /
('posting-%d.bin' % key)).read_bytes(),
+ entry.value)
+ self.assertEqual([1, 2, 3, 4, 5], keys)
+ self.assertGreater(blocks, 1)
+ finally:
+ reader.close()
+ self.assertTrue(file_io.input_stream.closed)
+
+ def test_java_string_prefix_queries(self):
+ serializer = create_serializer(AtomicType('STRING'))
+ keys = ['ke', 'keep', 'keeper', 'key', 'kf']
+ for version in (1, 2):
+ for bloom in (False, True):
+ for input_type in (_TrackingInput, _PreadInput):
+ with self.subTest(version=version, bloom=bloom,
input_type=input_type):
+ data, meta = self._meta(version, bloom, string=True)
+ file_io = _MemoryFileIO(data, input_type)
+ reader = BTreeIndexReader(serializer, file_io,
'/unused', meta)
+ try:
+ for prefix in ('', 'ke', 'keep', 'keeper', 'key',
'kf', 'absent', 'kg'):
+ with self.subTest(prefix=prefix):
+ expected = sorted(
+ row_id for i, key in enumerate(keys, 1)
+ if key.startswith(prefix) for row_id
in self.rows[i])
+ result = reader.visit_starts_with(prefix)
+ self.assertTrue(result.is_exact())
+ self.assertEqual(expected,
result.results().to_list())
+ iterator = reader.reader.create_iterator()
+ iterator.seek_to(serializer.serialize(''))
+ blocks = 0
+ seen = []
+ while True:
+ block = iterator.read_batch()
+ if block is None:
+ break
+ blocks += 1
+ while block.has_next():
+ entry = next(block)
+ key = serializer.deserialize(entry.key)
+ seen.append(key)
+ if version == 2:
+ self.assertEqual(
+ (self.directory /
('posting-%d.bin' % (keys.index(key) + 1))).read_bytes(),
+ entry.value)
+ self.assertEqual(keys, seen)
+ self.assertGreater(blocks, 1)
+ self.assertEqual([999],
reader.visit_is_null().results().to_list())
+ finally:
+ reader.close()
+ self.assertTrue(file_io.input_stream.closed)
+
+ def test_v2_initialization_failure_preserves_error_and_closes_stream(self):
+ data, meta = self._meta(2)
+ footer =
BTreeFileFooter.read_footer(data[-BTreeFileFooter.ENCODED_LENGTH:])
+ damaged = bytearray(data)
+ handle = footer.index_block_handle
+ damaged[handle.offset + handle.size + 1] ^= 1
+ for input_type in (_TrackingInput, _PreadInput):
+ for close_error in (None, OSError('Close failed')):
+ with self.subTest(input_type=input_type,
close_error=close_error):
+ file_io = _MemoryFileIO(bytes(damaged), input_type,
close_error=close_error)
+ with self.assertRaisesRegex(ValueError, 'CRC32 mismatch'):
+ BTreeIndexReader(self.serializer, file_io, '/unused',
meta)
+ self.assertTrue(file_io.input_stream.closed)
+
+ def test_malformed_posting_fails_query(self):
+ data, meta = self._meta(2)
+ reader = BTreeIndexReader(self.serializer, _MemoryFileIO(data,
_TrackingInput), '/unused', meta)
+ try:
+ with patch.object(reader.reader, 'lookup',
return_value=b'\x01\x02\x0a'):
+ with self.assertRaises(IndexError):
+ reader.visit_equal(1)
+ finally:
+ reader.close()
+
+ def test_mixed_versions_with_range_offset(self):
+ metas = [self._meta(version)[1] for version in (1, 2)]
+ with ThreadPoolExecutor(max_workers=2) as executor:
+ reader = LazyFilteredBTreeReader(
+ self.serializer, LocalFileIO(), str(self.directory), metas,
executor,
+ fallback_scan_max_size=1 << 20)
+ offset_reader = OffsetGlobalIndexReader(reader, 100, (1 << 63) - 1)
+ field = FieldRef(0, 'key', 'INT')
+ try:
+ result = offset_reader.visit_in(field, [1, 2,
3]).result(timeout=10)
+ expected = sorted(v + 100 for v in self.rows[1] + self.rows[2]
+ self.rows[3])
+ self.assertEqual(expected, result.results().to_list())
+ self.assertEqual(
+ sorted(v + 100 for v in self.rows[2] + self.rows[3]),
+ offset_reader.visit_between(field, 2,
3).result(timeout=10).results().to_list())
+ self.assertEqual(
+ [1099],
offset_reader.visit_is_null(field).result(timeout=10).results().to_list())
+ self.assertEqual({1, 2}, {r.footer.version for r in
reader._reader_cache.values()})
+ finally:
+ offset_reader.close()
+
+
if __name__ == '__main__':
unittest.main()
diff --git a/paimon-python/pypaimon/tests/btree_posting_list_test.py
b/paimon-python/pypaimon/tests/btree_posting_list_test.py
new file mode 100644
index 0000000000..83670d43ef
--- /dev/null
+++ b/paimon-python/pypaimon/tests/btree_posting_list_test.py
@@ -0,0 +1,111 @@
+# 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.
+
+"""BTree posting format and Java interoperability tests."""
+
+import json
+from pathlib import Path
+import unittest
+from unittest.mock import patch
+
+from pypaimon.globalindex.btree.btree_posting_list import add_row_ids
+from pypaimon.utils.roaring_bitmap import RoaringBitmap64
+
+
+def _varint(value):
+ data = bytearray()
+ while value > 127:
+ data.append((value & 127) | 128)
+ value >>= 7
+ data.append(value)
+ return bytes(data)
+
+
+class BTreePostingListTest(unittest.TestCase):
+
+ def test_java_postings_accumulate_without_expanding_roaring(self):
+ directory = Path(__file__).parent / 'resources' / 'btree'
+ expected = json.loads((directory / 'expected.json').read_text())
+ result = RoaringBitmap64()
+ result.add(7)
+ all_rows = [7]
+ for key, type_ in ((1, 0), (2, 1), (3, 2), (4, 2), (5, 2)):
+ data = (directory / ('posting-%d.bin' % key)).read_bytes()
+ self.assertEqual(type_, data[0])
+ if type_ == 2:
+ with patch.object(RoaringBitmap64, '__iter__',
side_effect=AssertionError('Expanded bitmap')), \
+ patch.object(RoaringBitmap64, 'to_list',
side_effect=AssertionError('Expanded bitmap')):
+ add_row_ids(data, 2, result)
+ else:
+ add_row_ids(data, 2, result)
+ all_rows.extend(expected[str(key)])
+ self.assertEqual(sorted(all_rows), result.to_list())
+
+ def test_java_roaring_crosses_high_word_buckets(self):
+ directory = Path(__file__).parent / 'resources' / 'btree'
+ data = (directory / 'posting-high-buckets.bin').read_bytes()
+ self.assertEqual(2, data[0])
+ result = RoaringBitmap64()
+ add_row_ids(data, 2, result)
+ self.assertEqual(list(range((1 << 32) - 64, (1 << 32) + 64)),
result.to_list())
+
+ def test_single_and_delta_numeric_boundaries(self):
+ values = [0, 127, 128, 16383, 16384, (1 << 32) - 1, 1 << 32, (1 << 63)
- 1]
+ for value in values:
+ with self.subTest(value=value):
+ result = RoaringBitmap64()
+ add_row_ids(b'\x00' + _varint(value), 2, result)
+ self.assertEqual([value], result.to_list())
+ data = b'\x01' + _varint(len(values)) + _varint(values[0])
+ data += b''.join(_varint(b - a) for a, b in zip(values, values[1:]))
+ result = RoaringBitmap64()
+ add_row_ids(data, 2, result)
+ self.assertEqual(values, result.to_list())
+
+ def test_v1_uses_absolute_ids_and_footer_version(self):
+ for values in ([10], [10, 20], [0, 128, 1 << 32, (1 << 63) - 1]):
+ with self.subTest(values=values):
+ result = RoaringBitmap64()
+ data = _varint(len(values)) + b''.join(_varint(v) for v in
values)
+ add_row_ids(data, 1, result)
+ self.assertEqual(values, result.to_list())
+
+ def test_rejects_invalid_postings(self):
+ oversized = _varint(1 << 63)
+ invalid = [
+ b'', b'\x63', b'\x00', b'\x00\x80',
+ b'\x01', b'\x01\x80', b'\x01\x00', b'\x01\x01\x0a',
+ b'\x01' + _varint(1 << 31), b'\x01\x02',
+ b'\x01\x02\x80', b'\x01\x02\x0a', b'\x01\x02\x0a\x80',
+ b'\x01\x02\x0a\x00', b'\x00' + oversized,
+ b'\x01\x02' + oversized, b'\x01\x02\x00' + oversized,
+ b'\x01\x02' + _varint((1 << 63) - 1) + b'\x01',
+ b'\x02', b'\x02invalid', b'\x02' + RoaringBitmap64().serialize(),
+ ]
+ bitmap = RoaringBitmap64()
+ bitmap.add(1 << 63)
+ invalid.append(b'\x02' + bitmap.serialize())
+ directory = Path(__file__).parent / 'resources' / 'btree'
+ invalid.append((directory / 'posting-3.bin').read_bytes()[:-1])
+ for data in invalid:
+ with self.subTest(data=data):
+ with self.assertRaises((ValueError, IndexError)):
+ add_row_ids(data, 2, RoaringBitmap64())
+
+ def test_rejects_unknown_version(self):
+ with self.assertRaisesRegex(ValueError, 'Unsupported BTree index file
version: 3'):
+ add_row_ids(b'\x00\x0a', 3, RoaringBitmap64())
diff --git
a/paimon-python/pypaimon/tests/resources/btree/BTreeFixtureGenerator.java
b/paimon-python/pypaimon/tests/resources/btree/BTreeFixtureGenerator.java
new file mode 100644
index 0000000000..04a101491b
--- /dev/null
+++ b/paimon-python/pypaimon/tests/resources/btree/BTreeFixtureGenerator.java
@@ -0,0 +1,161 @@
+/*
+ * 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.globalindex.btree;
+
+import org.apache.paimon.data.BinaryString;
+import org.apache.paimon.fs.PositionOutputStream;
+import org.apache.paimon.globalindex.KeySerializer;
+import org.apache.paimon.globalindex.ResultEntry;
+import org.apache.paimon.globalindex.io.GlobalIndexFileWriter;
+import org.apache.paimon.memory.MemorySlice;
+import org.apache.paimon.types.IntType;
+import org.apache.paimon.types.VarCharType;
+import org.apache.paimon.utils.BloomFilter;
+import org.apache.paimon.utils.LongArrayList;
+
+import java.io.ByteArrayOutputStream;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.Arrays;
+
+/** Generates Python interoperability fixtures using the actual Java writer. */
+public final class BTreeFixtureGenerator {
+
+ public static void main(String[] args) throws Exception {
+ Path directory = Paths.get(args[0]);
+ Files.createDirectories(directory);
+ long[][] rows = new long[5][];
+ rows[0] = new long[] {10};
+ rows[1] = new long[] {20, 40, (1L << 32) + 1};
+ rows[2] = new long[128];
+ rows[3] = new long[128];
+ rows[4] = new long[128];
+ for (int i = 0; i < 128; i++) {
+ rows[2][i] = 1000 + i;
+ rows[3][i] = (1L << 33) + i;
+ rows[4][i] = Long.MAX_VALUE - 127 + i;
+ }
+ int[] expectedTypes = {0, 1, 2, 2, 2};
+ StringBuilder expected = new StringBuilder("{\n");
+ for (int i = 0; i < rows.length; i++) {
+ LongArrayList list = new LongArrayList(rows[i].length);
+ for (long row : rows[i]) {
+ list.add(row);
+ }
+ byte[] encoded = BTreePostingList.serialize(list);
+ if ((encoded[0] & 255) != expectedTypes[i]) {
+ throw new AssertionError("Unexpected posting encoding");
+ }
+ long[] decoded =
+ BTreePostingList.deserialize(MemorySlice.wrap(encoded),
Integer.MAX_VALUE);
+ if (!Arrays.equals(decoded, rows[i])) {
+ throw new AssertionError("Java posting mismatch");
+ }
+ Files.write(directory.resolve("posting-" + (i + 1) + ".bin"),
encoded);
+ expected.append('"').append(i + 1).append("\":
").append(Arrays.toString(rows[i]));
+ expected.append(i + 1 == rows.length ? "\n}\n" : ",\n");
+ }
+ Files.write(
+ directory.resolve("expected.json"),
+ expected.toString().getBytes(StandardCharsets.UTF_8));
+ LongArrayList crossing = new LongArrayList(128);
+ for (int i = 0; i < 128; i++) {
+ crossing.add((1L << 32) - 64 + i);
+ }
+ byte[] crossingPosting = BTreePostingList.serialize(crossing);
+ if ((crossingPosting[0] & 255) != BTreePostingList.ROARING) {
+ throw new AssertionError("Expected Roaring across high-word
buckets");
+ }
+ Files.write(directory.resolve("posting-high-buckets.bin"),
crossingPosting);
+ String[] stringKeys = {"ke", "keep", "keeper", "key", "kf"};
+ for (int version = 1; version <= 2; version++) {
+ for (boolean bloom : new boolean[] {false, true}) {
+ for (boolean string : new boolean[] {false, true}) {
+ final String name =
+ "java-v"
+ + version
+ + (string ? "-string" : "")
+ + (bloom ? "-bloom" : "")
+ + ".btree";
+ final ByteArrayOutputStream bytes = new
ByteArrayOutputStream();
+ GlobalIndexFileWriter fileWriter =
+ new GlobalIndexFileWriter() {
+ @Override
+ public String newFileName(String prefix) {
+ return name;
+ }
+
+ @Override
+ public PositionOutputStream
newOutputStream(String fileName) {
+ return new PositionOutputStream() {
+ @Override
+ public long getPos() {
+ return bytes.size();
+ }
+
+ @Override
+ public void write(int value) {
+ bytes.write(value);
+ }
+
+ @Override
+ public void write(byte[] value) {
+ bytes.write(value, 0,
value.length);
+ }
+
+ @Override
+ public void write(byte[] value, int
offset, int length) {
+ bytes.write(value, offset, length);
+ }
+
+ @Override
+ public void flush() {}
+
+ @Override
+ public void close() {}
+ };
+ }
+ };
+ BTreeIndexWriter writer =
+ new BTreeIndexWriter(
+ fileWriter,
+ string
+ ?
KeySerializer.create(VarCharType.STRING_TYPE)
+ : KeySerializer.create(new
IntType()),
+ 32,
+ bloom ?
BloomFilter.fixedBuilder(rows.length, 0.01) : null,
+ null,
+ version);
+ for (int i = 0; i < rows.length; i++) {
+ for (long row : rows[i]) {
+ writer.write(
+ string ?
BinaryString.fromString(stringKeys[i]) : i + 1, row);
+ }
+ }
+ writer.write(null, 999);
+ ResultEntry entry = writer.finish().get(0);
+ Files.write(directory.resolve(name), bytes.toByteArray());
+ Files.write(directory.resolve(name + ".meta"),
entry.meta());
+ }
+ }
+ }
+ }
+}
diff --git a/paimon-python/pypaimon/tests/resources/btree/README.md
b/paimon-python/pypaimon/tests/resources/btree/README.md
new file mode 100644
index 0000000000..a521c23512
--- /dev/null
+++ b/paimon-python/pypaimon/tests/resources/btree/README.md
@@ -0,0 +1,63 @@
+# Java BTree interoperability fixtures
+
+These files are generated by `BTreeFixtureGenerator.java` using the
repository's
+`BTreeIndexWriter` and `BTreePostingList`. They are not Python round-trip
fixtures.
+
+Each `java-v{1,2}[-bloom].btree` uses INT keys, no block compression, a 32-byte
+target block size, and an independent null bitmap containing row ID 999.
+The matching `.meta` file contains the writer's serialized index metadata.
+`expected.json` records the non-null row IDs for each key:
+
+| Key | Rows | v2 encoding |
+| --- | --- | --- |
+| 1 | 10 | SINGLE (0) |
+| 2 | 20, 40, 4294967297 | DELTA_LIST (1) |
+| 3 | 1000 through 1127 | ROARING (2) |
+| 4 | 8589934592 through 8589934719 | ROARING (2) |
+| 5 | 9223372036854775680 through 9223372036854775807 | ROARING (2) |
+
+`posting-{1..5}.bin` contains the Java v2 posting for each key. The generator
+checks the actual encoding tag and the Java round-trip. Python file tests
compare
+the postings extracted from the SST blocks against these bytes. Python posting
+tests check the tags and compare decoded row IDs against `expected.json`.
+`posting-high-buckets.bin` is an additional Java Roaring posting covering
+4294967232 through 4294967359, across two high-word buckets in one payload.
+
+`java-v{1,2}-string[-bloom].btree` and their `.meta` files use STRING keys
+`ke`, `keep`, `keeper`, `key`, and `kf`, with the same postings and null
bitmap.
+These fixtures verify exact prefix queries across blocks, including all three
+v2 encodings and the exclusive prefix upper bound.
+
+To regenerate from the repository root with JDK 8, first build and run the Java
+posting tests to obtain the reactor's exact classpath:
+
+```shell
+mvn -pl paimon-common -am -DwildcardSuites=none \
+ -DfailIfNoTests=false -Dtest=BTreePostingListTest test
+```
+
+Then compile and run the generator without adding it to production sources:
+
+```python
+from pathlib import Path
+import subprocess
+import tempfile
+import xml.etree.ElementTree as ET
+
+root = Path.cwd()
+directory = root / 'paimon-python/pypaimon/tests/resources/btree'
+report = root /
'paimon-common/target/surefire-reports/TEST-org.apache.paimon.globalindex.btree.BTreePostingListTest.xml'
+properties = ET.parse(report).getroot().find('properties')
+classpath = next(p.attrib['value'] for p in properties
+ if p.attrib['name'] == 'java.class.path')
+with tempfile.TemporaryDirectory() as classes:
+ subprocess.run(['javac', '-source', '8', '-target', '8', '-cp', classpath,
+ '-d', classes, str(directory /
'BTreeFixtureGenerator.java')], check=True)
+ subprocess.run(['java', '-cp', classes + ':' + classpath,
+
'org.apache.paimon.globalindex.btree.BTreeFixtureGenerator',
+ str(directory)], check=True)
+```
+
+The fixtures were verified with Python 3.13 and pyroaring 1.1.0. These samples
+cover 64-bit portable Roaring payloads, including multiple high-word values and
+`Long.MAX_VALUE`. They do not establish compatibility with every pyroaring
version.
diff --git a/paimon-python/pypaimon/tests/resources/btree/expected.json
b/paimon-python/pypaimon/tests/resources/btree/expected.json
new file mode 100644
index 0000000000..e6f5fb295e
--- /dev/null
+++ b/paimon-python/pypaimon/tests/resources/btree/expected.json
@@ -0,0 +1,7 @@
+{
+"1": [10],
+"2": [20, 40, 4294967297],
+"3": [1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011,
1012, 1013, 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024,
1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037,
1038, 1039, 1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050,
1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063,
1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076,
1077, 1078, 1079, 1080, [...]
+"4": [8589934592, 8589934593, 8589934594, 8589934595, 8589934596, 8589934597,
8589934598, 8589934599, 8589934600, 8589934601, 8589934602, 8589934603,
8589934604, 8589934605, 8589934606, 8589934607, 8589934608, 8589934609,
8589934610, 8589934611, 8589934612, 8589934613, 8589934614, 8589934615,
8589934616, 8589934617, 8589934618, 8589934619, 8589934620, 8589934621,
8589934622, 8589934623, 8589934624, 8589934625, 8589934626, 8589934627,
8589934628, 8589934629, 8589934630, 8589934631, 858993 [...]
+"5": [9223372036854775680, 9223372036854775681, 9223372036854775682,
9223372036854775683, 9223372036854775684, 9223372036854775685,
9223372036854775686, 9223372036854775687, 9223372036854775688,
9223372036854775689, 9223372036854775690, 9223372036854775691,
9223372036854775692, 9223372036854775693, 9223372036854775694,
9223372036854775695, 9223372036854775696, 9223372036854775697,
9223372036854775698, 9223372036854775699, 9223372036854775700,
9223372036854775701, 9223372036854775702, 922 [...]
+}
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree
new file mode 100644
index 0000000000..96f18ceffe
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree.meta
new file mode 100644
index 0000000000..a3ac99b2c5
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-bloom.btree.meta differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree
new file mode 100644
index 0000000000..1c15806467
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree.meta
new file mode 100644
index 0000000000..71a5dc84be
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string-bloom.btree.meta
differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree
new file mode 100644
index 0000000000..ba1d3a448a
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree.meta
new file mode 100644
index 0000000000..71a5dc84be
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1-string.btree.meta differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v1.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v1.btree
new file mode 100644
index 0000000000..f1d5a8d2d8
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1.btree differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v1.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v1.btree.meta
new file mode 100644
index 0000000000..a3ac99b2c5
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v1.btree.meta differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree
new file mode 100644
index 0000000000..832d6f96ad
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree.meta
new file mode 100644
index 0000000000..a3ac99b2c5
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-bloom.btree.meta differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree
new file mode 100644
index 0000000000..ebd7a39e52
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree.meta
new file mode 100644
index 0000000000..71a5dc84be
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string-bloom.btree.meta
differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree
new file mode 100644
index 0000000000..3e69c491a1
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree.meta
new file mode 100644
index 0000000000..71a5dc84be
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2-string.btree.meta differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v2.btree
b/paimon-python/pypaimon/tests/resources/btree/java-v2.btree
new file mode 100644
index 0000000000..6f4d7957b7
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2.btree differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/java-v2.btree.meta
b/paimon-python/pypaimon/tests/resources/btree/java-v2.btree.meta
new file mode 100644
index 0000000000..a3ac99b2c5
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/java-v2.btree.meta differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/posting-1.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-1.bin
new file mode 100644
index 0000000000..1f2a4f5ef3
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/posting-1.bin differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/posting-2.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-2.bin
new file mode 100644
index 0000000000..d8d877e9b8
--- /dev/null
+++ b/paimon-python/pypaimon/tests/resources/btree/posting-2.bin
@@ -0,0 +1 @@
+����
\ No newline at end of file
diff --git a/paimon-python/pypaimon/tests/resources/btree/posting-3.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-3.bin
new file mode 100644
index 0000000000..984f6ddd4f
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/posting-3.bin differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/posting-4.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-4.bin
new file mode 100644
index 0000000000..60639129e5
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/posting-4.bin differ
diff --git a/paimon-python/pypaimon/tests/resources/btree/posting-5.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-5.bin
new file mode 100644
index 0000000000..a8c691262f
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/posting-5.bin differ
diff --git
a/paimon-python/pypaimon/tests/resources/btree/posting-high-buckets.bin
b/paimon-python/pypaimon/tests/resources/btree/posting-high-buckets.bin
new file mode 100644
index 0000000000..3e4749bea9
Binary files /dev/null and
b/paimon-python/pypaimon/tests/resources/btree/posting-high-buckets.bin differ
diff --git a/paimon-python/pypaimon/utils/roaring_bitmap.py
b/paimon-python/pypaimon/utils/roaring_bitmap.py
index 41b0a6e4d8..22a2994a67 100644
--- a/paimon-python/pypaimon/utils/roaring_bitmap.py
+++ b/paimon-python/pypaimon/utils/roaring_bitmap.py
@@ -54,6 +54,10 @@ class RoaringBitmap64:
"""Return the number of elements in the bitmap."""
return len(self._data)
+ def max(self) -> int:
+ """Return the largest value in a non-empty bitmap."""
+ return self._data.max()
+
def __iter__(self) -> Iterator[int]:
"""Iterate over all values in the bitmap in sorted order."""
return iter(self._data)
@@ -127,6 +131,10 @@ class RoaringBitmap64:
"""Remove all values contained in ``other`` from this bitmap, in
place."""
self._data -= other._data
+ def or_inplace(self, other: 'RoaringBitmap64') -> None:
+ """Add all values from another bitmap in place."""
+ self._data |= other._data
+
def serialize(self) -> bytes:
"""Serialize the bitmap to bytes."""
return self._data.serialize()
