Data Auto Sharding and Auto Indexing: Difference between revisions

From MemCP
Jump to navigation Jump to search
No edit summary
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
 
Line 1: Line 1:
To understand the following explainations, you should read about [[Shards, RecordIDs, Main Storage, Delta Storage]] first. An understanding of [[Scan]] can also help.
<!-- Copyright (C) 2026 Carl-Philip Haensch -->


== Auto-Indexing ==
<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
Auto Indexing works the following way:


* Whenever there is a [[scan]] over a table shard that has certain boundaries (e.g. <code>WHERE col1 = value1 AND col2 = value2 ORDER BY col3 ASC</code>), there exists a "'''desired index'''" (e.g. [col1 col2 col3])
<span id="data-auto-sharding-and-auto-indexing"></span>
* Every desired index is created shard-locally but marked "inactive"
= Data Auto Sharding and Auto Indexing =
* There is a cost model consisting of three components:
** The cost of scanning without index
** The cost of building the index
** The cost of scanning with the index
* After about two indexed scans, the cost of indexing will be ammortized
** before the amortization threshold is met, do full scans
** as soon as the amortization threshold is met, build the index


Indexes are (currently) only built over the main storage. Delta storage items are currently appended to the scan in an unordered way.
MemCP observes executed scans and uses their boundaries, ordering, selectivity, and row counts as evidence for physical organization. It can build adaptive indexes and use partitioning hints during later shard rebuilds, reducing the need to predict every access path when defining a schema.


An index is a [[Integer Compression|integer-compressed]] list of recordIds, meaning: instead of storing the values in the index itself, the index is a cache-compressed pointerless structure. This list is sorted by the sort criterion. This makes storing indexes so cheap.
This self-tuning behavior is incremental rather than instantaneous: small shards and weak evidence deliberately avoid expensive builds, while repartitioning happens as background physical maintenance. The choices never change SQL semantics and do not replace logical decorrelation, join ordering, transaction visibility, or residual predicate checks. Operators should still inspect plans and resource use for important workloads.


A 60,000 item index would compress to 16 bits integer width, so the size of the index would be 120 KB.
Unlike a declared primary or unique key, an adaptive index is a performance object rather than a data-integrity rule. Keep schema constraints that protect correctness; let workload evidence propose additional physical access paths.


== Auto-Sharding ==
<span id="adaptive-indexes"></span>
Auto-Sharding is done similar to Auto-Indexing:
== Adaptive indexes ==


* Whenever there is a [[scan]] over a table where a sharding scheme along a column <code>col</code> would be benefitial, the "partitioning score" for <code>col</code> is increased.
Equality, range, IN-list, LIKE-prefix, computed-expression, and ordering boundaries describe useful index prefixes. MemCP reuses compatible longer indexes, avoids new indexes for tiny shards, and accumulates estimated savings until build cost is amortized. ORDER/LIMIT scans receive a weighted benefit so a small top-k does not train an expensive full index as aggressively as a broad ordered scan.
* After a while (~15min), there is a reevaluation if the shards of a table should be repartitioned
* The shard dimensions are chosen proportional to the "partitioning score" from the previous steps
* The number of shard dimensions can be limited in the [[Settings]]
* Then, data is reshuffled. This may take a while for bigger tables.


Partitioning has the following positive effects:
Indexes contain compressed record-ID permutations rather than copies of column values. Main rows and delta inserts are both ordered: an index-local delta tree is merged with the main permutation during iteration. Deleted/invisible rows and residual predicates remain subject to transaction visibility and filtering.


* A scan with boundaries matching the partitioning scheme will only touch those partitions with relevant data in it
Relevant settings are <code>IndexThreshold</code>, <code>AnalyzeMinItems</code>, <code>ScanDebugging</code>, and <code>ShardSize</code>.
* INSERTs with unique keys will be able to scale whenever all unique keys are covered within the partitioning schema


By using insert or scan very often, it will increase the partitioning score on the right dimensions, so auto-sharding in MemCP is self learning.
The benefit estimate compares continued full-scan work, index build cost, and future indexed probes. Until estimated savings amortize the build, MemCP can continue scanning. This avoids eagerly creating every syntactically possible index and lets a compatible longer index serve a shorter prefix.


== Parallel Sharding==
<span id="adaptive-sharding"></span>
MemCP automatically creates parallel shards for optimal query performance across multiple CPU cores.
== Adaptive sharding ==
===Bulk Insert Optimization===
 
When inserting large amounts of data, MemCP automatically:
Scans contribute partitioning evidence for useful columns. Rebuild/repartition work uses these hints, row counts, <code>ShardSize</code>, CPU parallelism, and <code>PartitionMaxDimensions</code> to choose shard boundaries. Bulk inserts create and rebuild shards in batches; readers and writers are protected during generation replacement.
#'''Splits bulk inserts into chunks''' of 60,000 rows (configurable via ShardSize)
 
#'''Creates new shards on-the-fly''' when the current shard fills up
Repartitioning is background physical maintenance. It may consume CPU, memory, and storage bandwidth, so observe it on large production tables. It must preserve writes and durability across old and new shard generations.
#'''Rebuilds full shards in parallel''' using background goroutines
 
This enables insertion of millions of rows while maintaining parallel query execution.
Useful partitioning lets a bounded scan skip unrelated shards and lets independent shards execute concurrently. It is not the same as distributing tables across network nodes: current adaptive sharding is local to one MemCP instance.
===Automatic Repartitioning===
 
During <code>rebuild()</code>, if no partitioning hints exist but data exceeds ShardSize:*MemCP calculates the optimal number of shards based on data size
== Bulk import and operational guidance ==
*Creates at least <code>2 × NumCPU</code> shards for good parallelism
 
*Uses the first column for round-robin distribution
Large inserts are chunked around the configured shard target and full shards can rebuild in parallel. Loading in batches is more efficient than a client round trip per row and gives the analyzer enough evidence to select compact representations. After a representative warm-up, inspect <code>EXPLAIN PHYSICAL</code>, shard statistics, resident memory, build activity, and query latency.
===Performance Characteristics===
 
With parallel sharding enabled: - Query CPU utilization: 1500-1900% (15-19 cores on a 24-core machine) - Speedup: 3-6x compared to single-threaded execution - Throughput: ~0.04 µs/row for COUNT/SUM operations
Avoid tuning <code>ShardSize</code> or <code>PartitionMaxDimensions</code> from a single query. Very small shards add scheduling/index metadata overhead; very large shards reduce pruning and parallel choices. Validate changes with the complete read/write workload and restart behavior.
===Configuration===
 
{| class="wikitable"
The current defaults are <code>ShardSize=60000</code> and <code>PartitionMaxDimensions=10</code>. They are starting points, not a promise that every table will have exactly 60,000 rows per shard or use ten dimensions.
!Setting
 
! Default
== Historical parallel-scan observation ==
!Description
 
|-
An earlier development run reported 1,500–1,900% CPU utilization on a 24-core host, a 3–6× improvement over its single-shard comparison and roughly 0.04 µs per row for simple COUNT/SUM work. The old page did not preserve the commit, dataset, query, repetitions, correctness checks or machine state, so these numbers remain a useful engineering observation rather than a current benchmark claim. Reproduce them with [[Performance Measurement|the performance framework]] before using them for capacity planning.
|ShardSize
 
|60,000
See [[Query_Planner_and_Physical_Lowering|Query Planner and Physical Lowering]] for the cost model that decides whether a query uses an index, direct scan, RecSet, cache, or another scan source. [[RecSets]] explains how exact and candidate memberships interact with these indexes and adapt between ranges, sparse IDs, and bitmaps.
| Rows per shard before splitting
|-
|PartitionMaxDimensions
|10
|Maximum partitioning dimensions
|}

Latest revision as of 11:59, 28 August 2026


Data Auto Sharding and Auto Indexing

MemCP observes executed scans and uses their boundaries, ordering, selectivity, and row counts as evidence for physical organization. It can build adaptive indexes and use partitioning hints during later shard rebuilds, reducing the need to predict every access path when defining a schema.

This self-tuning behavior is incremental rather than instantaneous: small shards and weak evidence deliberately avoid expensive builds, while repartitioning happens as background physical maintenance. The choices never change SQL semantics and do not replace logical decorrelation, join ordering, transaction visibility, or residual predicate checks. Operators should still inspect plans and resource use for important workloads.

Unlike a declared primary or unique key, an adaptive index is a performance object rather than a data-integrity rule. Keep schema constraints that protect correctness; let workload evidence propose additional physical access paths.

Adaptive indexes

Equality, range, IN-list, LIKE-prefix, computed-expression, and ordering boundaries describe useful index prefixes. MemCP reuses compatible longer indexes, avoids new indexes for tiny shards, and accumulates estimated savings until build cost is amortized. ORDER/LIMIT scans receive a weighted benefit so a small top-k does not train an expensive full index as aggressively as a broad ordered scan.

Indexes contain compressed record-ID permutations rather than copies of column values. Main rows and delta inserts are both ordered: an index-local delta tree is merged with the main permutation during iteration. Deleted/invisible rows and residual predicates remain subject to transaction visibility and filtering.

Relevant settings are IndexThreshold, AnalyzeMinItems, ScanDebugging, and ShardSize.

The benefit estimate compares continued full-scan work, index build cost, and future indexed probes. Until estimated savings amortize the build, MemCP can continue scanning. This avoids eagerly creating every syntactically possible index and lets a compatible longer index serve a shorter prefix.

Adaptive sharding

Scans contribute partitioning evidence for useful columns. Rebuild/repartition work uses these hints, row counts, ShardSize, CPU parallelism, and PartitionMaxDimensions to choose shard boundaries. Bulk inserts create and rebuild shards in batches; readers and writers are protected during generation replacement.

Repartitioning is background physical maintenance. It may consume CPU, memory, and storage bandwidth, so observe it on large production tables. It must preserve writes and durability across old and new shard generations.

Useful partitioning lets a bounded scan skip unrelated shards and lets independent shards execute concurrently. It is not the same as distributing tables across network nodes: current adaptive sharding is local to one MemCP instance.

Bulk import and operational guidance

Large inserts are chunked around the configured shard target and full shards can rebuild in parallel. Loading in batches is more efficient than a client round trip per row and gives the analyzer enough evidence to select compact representations. After a representative warm-up, inspect EXPLAIN PHYSICAL, shard statistics, resident memory, build activity, and query latency.

Avoid tuning ShardSize or PartitionMaxDimensions from a single query. Very small shards add scheduling/index metadata overhead; very large shards reduce pruning and parallel choices. Validate changes with the complete read/write workload and restart behavior.

The current defaults are ShardSize=60000 and PartitionMaxDimensions=10. They are starting points, not a promise that every table will have exactly 60,000 rows per shard or use ten dimensions.

Historical parallel-scan observation

An earlier development run reported 1,500–1,900% CPU utilization on a 24-core host, a 3–6× improvement over its single-shard comparison and roughly 0.04 µs per row for simple COUNT/SUM work. The old page did not preserve the commit, dataset, query, repetitions, correctness checks or machine state, so these numbers remain a useful engineering observation rather than a current benchmark claim. Reproduce them with the performance framework before using them for capacity planning.

See Query Planner and Physical Lowering for the cost model that decides whether a query uses an index, direct scan, RecSet, cache, or another scan source. RecSets explains how exact and candidate memberships interact with these indexes and adapt between ranges, sparse IDs, and bitmaps.

Retrieved from "https://www.memcp.org/index.php?title=Data_Auto_Sharding_and_Auto_Indexing&oldid=323"