...

Motivation

The main goal is to speed up SQL query execution.

Currently, we have only row count statistics to choose optimal query plans.

Description

Glossary

Cardinality - we always operate with cardinality (not selectivity). For this document, cardinality means a number of different values in some set (column values in partition, node or in the whole table). But there are another opinions: http://dbaparadise.com/2017/08/5-things-to-better-understand-selectivity-and-cardinality/

...

OSC – Object Statistics Coordinator, some node, which responsible for particular objects statistics collection. It can be calculated from object name and we need such separated node just to coordinate statistics collection in one node.

Suggested design

Stage 1

Stage 1 consists of:

1) Local statistics collection to speed up H2 query execution.

...

4) View to show collected statistics

Statistics collection

These part consists of two processes: statistics collection process itself and acquiring statistics by the client.

Acquiring statistics by client process:

1. First-time request: client query planning node will send stats request to all server nodes. 
2. Getting response: 
1. If requested statistics are presented somewhere - node just return it to client
2. If statistics are presented on more than one server node - client will use the last one received.
3. If there are no statistics in all of them - client will choose random server node and require it to collect necessary statistics.
3. After getting statistics client will cache it and the server node, which sent it to renew statistics from the same node.

To request statistics following messages are used:

...

with different collection area. They all can contain the same data (min/max/cardinality/nulls and so on) See (Pluggable statistics).

Statistics persistence

To save collected statistics proposed to use local meta storage. Server node will store statistics for each partition for potentially each object. Client node (or server, planning query execution plan) will require global statistics in a lazy manner from all server nodes.

...

On getting global statistics request server node won’t do anything until statistics collection request will be received. On getting such request node will renew statistics only if there is no previously received request for the same objects with smaller uniq reqId.

API to collect statistics

To manually control statistics collection there are should be the following API methods:

...

Statistics will be collected by table columns (St1). Possible objects to collect statistics later is: combined columns (for combined index, for example) and condition index itself (index with where clause).

Stage 2

Stage 2 consists of:

1) Add metrics to show: collection time, last collected time/update counter, memory consumption to cache&store statistics.

...

4) Partially statistics update to speed up statistics update (scan only partitions/nodes with a lot of changes)

Metrics

To make statistic collection more controlled and visible we can show through JMX metrics about memory, disk space and CPU time consumption by statistics subsystem on each (client and server) node. It can be even the same as statistics view and contains addition API to collect/drop statistics. These can be shown by each object for partition/local/global levels.

Sampling

To speed up statistics collection we can use sampling. Main idea is to scan not all rows in tables, but some subset of its. To estimate optimal row quantity statistics subsystem should take in account one ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.1734&rep=rep1&type=pdf ) and two ( https://ru.wikipedia.org/wiki/Reservoir_sampling ).

Automatic statistics collection

There is two similar processes:

...

From the user point of view, both processes should work in the same way. To track the number of changes in objects we can use the following approach: add one more HLL structure to track inserted, modified or removed keys count and update statistics when this amount grow some border. It meat that for each Nth insert, update, delete should be put into local cardinality tracking structure by taking a hash of its row key. And we should save that structure with statistics in the local meta store.

In addition -

Partially statistics update

Partially statistics update is another way to speed up statistics update. If a lot of updates will be detected only on some node such node can update it’s own locally statistics and send it to object statistics coordinator to aggregate it later. Thus the whole cluster will be using actual enough statistics without unnecessary scanning old data.

Stage 3

Stage 3 consists of:

H2 independent statistics (its own types and comparators). Implementation will be connected with schema first approach.

...

Advanced statistics (heavy heaters, histograms and so on).

H2 independent statistics

To avoid H2 from statistics collection engine we need some schema, so this part is blocked by schema first approach. But the main idea is to collect statistics (get and compare values) without h2 code.

Type dependent statistics

The main idea is to collect type optimized statistics. We can split data types by: thin, fixed length, variable length, complex types (like Geometry or JSON in the future).

...

Complex types – for now it enough if we treat it like byte[], but in future we can calculate some type-specific statistics metrics.

Advanced statistics

Advanced statistics mean collecting some histogramms, heavy heaters and any other complex metrics, designed to improve quality of query plans.

Stage 4

Stage 4 consists of

• Pluggable statistics interface.
     
• Load/Export statistics (for test purposes, for performance testing, to collect statistics on a hot backup cluster and load into primary one)
     
• Index statistics collection (for conditional indexes, if     needed)
  
  

Pluggable statistics interface

To collect any kind of statistics for:

...

TBD: human-readable representation to show in views.

Load/Export statistics

Just as idea - node can support some API to export/import statistics. It can be usefull for test, benchmark and other purposes.

Index statistics collection

Just as idea - we can have some object which statistics can be more accurate that just statistics by data tables. For example - conditional indexes(normal index with where clause). That's why we collect not "table" but "object" statistics.

Risks and Assumptions

// Describe project risks, such as API or binary compatibility issues, major protocol changes, etc.

Discussion Links

// Links to discussions on the devlist, if applicable.

Reference Links

// Links to various reference documents, if applicable.

Tickets

// Links or report with relevant JIRA tickets.