This is unfortunately the outcome of numerous changes we had to experiment with to address various important performance and functionality challenges during a contract with a customer. It should have been better modularized into separate commits, but this did not happen as the work got interleaved as we were progressing with the contract. To be absolutely avoided in the future!

To make the reviewing progress somewhat easier, I am breaking down the changes per meaningful group of files.

High-level Changes

• Added R-Tree to boost sparse subarray reads.
• Added new algorithm for multi-range subarray read for sparse arrays.
• New sparse read algorithm uses significantly less memory.
• Refactored the way subarray partitioning works for multi-range subarrays.
• Subarray partitioning now takes into account a congigurable memory budget.
• Removed array schema and fragment metadata cache.
• GLOBAL_ORDER is no longer permitted in reads.
• Refactored fragment metadata to partially work out-of-core (they are no longer loaded entirely when opening an array)
• Added proper array exclusive lock when storing metadata and reconciled consolidator.
• Fixed an issue with consolidating kv.
• Deleted consistency test, since now flushing the fragment metadata after writing to an array requires an exclusive lock. The TileDB consistency model is now better captured by the tiledb_array_open_at functionality anyway.
• Tweak to reader/VFS parallelism: read_all now uses reader thread pool.
• Added memory budget parameter to config
• Tuned the way read batches are stitched in VFS prior to reading
• Parallelized fragment metadata loading.
• Clean up unused VFS config params.
• Changed config param for VFS batching to vfs.min_batch_size.
• Added one more VFS config parameter (vfs.batch_gap_size) to control the read batch stitching. If there are fewer than vfs.batch_gap_size bytes between two batches, the batches get stitched. The current default is 500KB
• Fixed issue with expanding state for key validation checks when opening an already open encrypted array

TODO after merge

• Improve out-of-core fragment metadata: add footer with all generic tile offsets.
• Do not expose SubarrayPartitioner to the C/C++ API via tiledb_subarray_partitioner_t.
• Add new algorithm for dense multi-range subarray reads.
• Clean up dead code and tests.
• Finalize C API for setting subarrays.
• Add C++ API.
• Revisit StorageManager::get_fragment_info (there are some TODOs there regarding xlocking)
• Do not use TBB for parallel IO in StorageManager. Use an alternative thread pool instead.

Review Help

tiledb/sm/rtree/rtree.cc
tiledb/sm/rtree/rtree.h
test/src/unit-rtree.cc

• The implementation of the R-Tree, used to boost sparse subarray reads.
• Tests of the RTree class.

tiledb/sm/subarray/subarray.cc
tiledb/sm/subarray/subarray.h
tiledb/sm/misc/tile_overlap.h
tiledb/sm/cpp_api/deleter.h
tiledb/sm/cpp_api/query.h
tiledb/sm/cpp_api/subarray.h
tiledb/sm/cpp_api/tiledb
tiledb/sm/query/query.h
tiledb/sm/query/query.cc

• The implementation of Subarray, which now handles multi-range subarrays.
• This is exposed and unit-tested at the C and C++ APIs

tiledb/sm/subarray/subarray_partitioner.cc
tiledb/sm/subarray/subarray_partitioner.h

• The implementation of SubarrayPartitioner, which manages the result size and facilitates incomplete queries.
• This is exposed and unit-tested at the C API

tiledb/sm/c_api/tiledb.h
tiledb/sm/c_api/tiledb.cc
test/src/unit-capi-subarray.cc
test/src/unit-capi-subarray-partitioner.cc
test/src/unit-cppapi-subarray.cc
doc/source/c-api.rst

• Added APIs for tiledb_subarray_t (which wraps Subarray)
• Added APIs for tiledb_subarray_partitioner_t (which wraps SubarrayPartitioner)
• Changed documentation of config.
• Unit tests for subarray (C and C++ API) and subarray partitioner (C API)
• Updated C API docs

tiledb/sm/vfs/vfs.h
tiledb/sm/vfs/vfs.cc
test/src/unit-vfs.cc

• VFS::read_all takes as input a thread pool
• Changed the way small read batches are stitched in a single one. Specifically, if (i) the two batches fit in a single batch whose size is smaller than a config parameter, or (ii) the gap between two batches is smaller than a new config parameter, then the two batches are stitched in a single one.

tiledb/sm/storage_manager/config.h
tiledb/sm/storage_manager/config.cc
tiledb/sm/cpp_api/config.h
test/src/unit-config.cc
docs/source/tutorials/config.rst
docs/source/tutorials/performance-factors.rst

• Removed unused configs (array schema and fragment metadata cache size, batch amplification)
• Added memory budget configs
• Added min batch gap config for improved VFS batch stitching.
• Renamed max batch read size to min batch gap.

tiledb/sm/tile/tile.cc

• Bug fix.

tiledb/sm/fragment_metadata/fragment_metadata.h
tiledb/sm/fragment_metadata/fragment_metadata.cc
doc/source/tutorials/format-description.rst

• Refactored fragment metadata to work partially out-of-core.
• Instead of loading the entire metadata, initially a small generic tile is loaded with all the basic information.
• The rest of the metadata is loaded on demand.
• Added R-Tree to metadata for MBRs.
• Moved store/load to FragmentMetadata instead of StorageManager
• Added xlock array logic when storing fragment metadata to prevent process-safety issues
• Updated format spec on docs
• There is some dead code that must be deleted after adding dense multi-range subarrays.

tiledb/sm/storage_manager/open_array.h
tiledb/sm/storage_manager/open_array.cc

• Handle key validation in OpenArray instead of StorageManager
• Prevents the need for an ever expanding state for key validation in StorageManager
• Minor thread-safety fix

tiledb/sm/storage_manager/consolidator.h
tiledb/sm/storage_manager/consolidator.cc
test/src/unit-capi-consolidation.cc

• Clean up
• Better way of xlocking the array during consolidation
• Some fixes in the tests

tiledb/sm/fragment/fragment_info.h

• Use std vector instead of void* for non empty domain.

tiledb/sm/array_schema/domain.h

• Minor template header fix

tiledb/sm/misc/uri.h
tiledb/sm/misc/uri.cc

• Added auxiliary function to remove double slash characters in URIs (they were causing problems in some backends)

tiledb/sm/misc/utils.h
tiledb/sm/misc/utils.cc

• Auxiliary functions needed by the R-Tree.

tiledb/sm/query/writer.h
tiledb/sm/query/writer.cc

• Currently setting subarray for writes works only with void* subarrays.
• Added placeholder for when we get rid of setting void* subarrays and use Subarray instead for writes.

tiledb/sm/query/reader.h
tiledb/sm/query/reader.cc
test/src/unit-capi-incomplete-2.cc
test/src/unit-capi-sparse_array-2.cc
test/src/unit-capi-sparse_neg-2.cc
test/src/unit-capi-sparse_real-2.cc

• New algorithm for multi-range subarray sparse reads
• New way to partition subarray and maintain state
• The new algorithm uses significantly less memory (attribute tiles are fetched incrementally, not all at once).
• The new algorithm is Read::read_2. This will substitute Read::read once the dense multi-range subarray are implemented.
• The old algorithm (which admits a single-range void* subarray still works).
• All old tests work.
• Added new tests with suffix *-2.cc, which will substitute the old ones once the dense multi-range subarray are implemented.
• The tests could use some cleaning.

tiledb/sm/storage_manager/storage_manager.h
tiledb/sm/storage_manager/storage_manager.cc

• Removed array schema and fragment metadata caches.
• Moved storing of fragment metadata to Writer.
• Fixed issues with ever expanding state for key validation when reopening already open encrypted arrays.
• Some array xlocking work.

tiledb/sm/misc/constants.h
tiledb/sm/misc/constants.cc

• Mainly added default values for the new config parameters.

tiledb/sm/misc/parallel_functions.h

• Added 2D parallel for function.

tiledb/sm/misc/status.h
tiledb/sm/misc/status.cc

• Added statuses for the newly added classes.

tiledb/sm/array.h
tiledb/sm/array.cc

• Added getter for the encryption key. Needed to decrypt fragment metadata on the fly.

test/src/unit-capi-array.cc
test/src/unit-dense-array.cc
test/src/unit-kv.cc
test/src/unit-cppapi-array.cc

• Minor fixes.

test/src/unit-capi-consistency.cc

• Removed this set of tests. Consistency now is handled through the open_{array,kv}_at functions.

HISTORY.md

• We need to update this just before merging.