Hi there!

I would like to work on this issue and then submit my proposal.
How can I configuring system to solve this?

Did you see https://mariadb.org/get-involved/getting-started-for-developers/get-code-build-test/ ?

Ok this task is selected for Google Summer of Code 2021. The student is Michael Okoko, the mentor is me.

Discussion:
https://lists.launchpad.net/maria-developers/msg12743.html
https://lists.launchpad.net/maria-developers/msg12757.html

Code for Milestone-1 is here: https://github.com/MariaDB/server/pull/1854 . It still fails the tests.

Code for Milestone-2: https://github.com/MariaDB/server/pull/1871 . It has a memory leak in class Histogram but this will be fixed in the subsequent milestones.

On the question of "How does 'col IN (const1,const2,...)' store its lookup array" :

It is item_cmpfunc.h, class in_vector. It has type-specific descendants like in_string, in_longlong,
in_timestamp. It is created through this call:

array= m_comparator.type_handler()->make_in_vector(thd, this, arg_count - 1);

The storage format is specific to each datatype and is not explicitly defined.

The interface for populating the array and making lookups uses Item objects:

  virtual void set(uint pos,Item *item)=0;

  bool find(Item *item);

One thing it doesn't have is that there's no way to get the values back from the array.

Some notes from debugging

=== Histogram lifecycle ===

=== Loading histogram from mysql.column_stat ===

alloc_statistics_for_table_share() - allocates stats data structures but
doesn't read them.

read_statistics_for_table() - loads the statistics.

Note that this is done in two steps: first, column stats are loaded, including
histogram_type and histogram_size. Then, the histogram itself is loaded.
The second step even does a separate read from mysql.column_stats!

The loading is synchronized using TABLE_STATISTICS_CB (only one thread is doing
the loading)

read_histograms_for_table() - called after read_statistics_for_table(), reads the
histograms.

The synchronization is done through TABLE_STATISTICS_CB (only one thread is doing
the loading).

Also, TABLE_STATISTICS_CB ensures that histograms are only read once (if there
are two TABLE objects, they'll share the same field->read_stats and so
Histogram object).

=== Collecting histogram ===

alloc_statistics_for_table() is used to allocate statistical data structures.
allocation is done on TABLE's MEM_ROOT.

collect_statistics_for_table() - is used to collect the statistics.

(Note: it looks like it's possible for different threads to collect statistics
for different fields simultaneously?)

Then, Column_stat::store_stat_fields() saves the data into table.

Then, the histogram is read back from disk before it is used.

Patch for Milestone-3: https://github.com/MariaDB/server/pull/1875

Patch for Milestone-4.1: https://github.com/idoqo/server/pull/2/

More on the in-memory data structure for lookups.

It doesn't have to have anything to do with collection-time data structure.

It is basically an ordered array (either of bucket endpoints or of some
stuctures that contain endpoints plus something else).

The ordered array will be used to make lookups into it, so that we can find the
buckets that overlap with the range we're computing the estimate for (denote as
$SEARCH_RANGE).

It is likely that $SEARCH_RANGE partially overlaps with a bucket, that is

$BUCKET_MIN < $SEARCH_ENDP < $BUCKET_MAX.

In this case, we'll follow existing histograms and assume that $SEARCH_RANGE
occupies a "proportional" part of the bucket.

Currenty the fraction is calculated as follows:

        store_key_image_to_rec(field, (uchar *) $SEARCH_ENDP,

                               field->key_length());

        pos = field->pos_in_interval(min_value,

                                     max_value);

Here, the min_value and max_value have the bounds.

They are defined as

Field * Column_statistics::min_value

and pos_in_interval is defined as:

  double pos_in_interval(Field *min, Field *max);

There are two implementations:
pos_in_interval_val_real(), which gets min/max values by calling min/max->val_real() and then operating on the numbers it has got.

pos_in_interval_val_str() which gets min and max values by calling

strxfrm(..., target_size=8, min->ptr + data_offset, min->data_length())

and then operating on 8-byte prefixes as integers.

Arguments against in_vector data structure:

1. Its methods to populate/make lookups use "Item *item" as parameters. This will need to change to also allow Field*.
2. The find() method currently only supports equality lookups. We need [X;Y) open/closed ranges.
3. The values are stored in some custom format. The format allows to compare values, but it is unclear how one could implement an analog of Field::pos_in_interval() for it.
4. in_vector is not flexible - there's no way to store any extra data for a bucket.

Arguments for using it: we will be able to reuse
1. Code that allocates the array
2. Encoding functions

Not much.

Leaning towards using std::vector<KeyTupleFormat> data structure/

Here is a patch https://github.com/MariaDB/server/commit/4d3c434028649a0f14471ed4a1a4c10b97b78eb8 that shows how to do all needed operations:

• JSON text -> binary conversion
• Comparing two values (so one can find the bucket)
• Computing pos_in_interval(A,B,X) - for A <= X <= B, return a fraction specifying how close X to the endoints of the [A,B] interval.

Patch usage: https://gist.github.com/spetrunia/a09bd451f650737ba5ea7a6e51bc797a

The progress so far is documented as part of the GSoC final report at https://gist.github.com/idoqo/ac520943e53f64034beaed4258b62ba5

The candidate code is at: https://github.com/MariaDB/server/tree/bb-10.7-mdev21130

elenst, documentation for testing:

histogram_type variable is used to specify what kind of histogram is collected.

After this patch, it can be set to a new value: JSON_HB.

Then, EITS code will create JSON histograms. Old histogram types remain supported, the optimizer will use whatever histogram is available.

The histograms are kept in mysql.column_stats, the columns of interest are:

• hist_type (SINGLE_PREC_HB, DOUBLE_PREC_HB, now also JSON_HB)
• histogram. for JSON_HB, this is a JSON document.

the function DECODE_HISTOGRAM also "supports" JSON_HB by returning the histogram unmodified. That is, one can do this:

select DECODE_HISTOGRAM(hist_type, histgram) from mysql.column_stats

and get a readable representation of histogram for any kind of histogram.

Things to test

• Collection of histograms. ANALYZE ... PERSISTENT FOR... statements overlapping with other workload. Histogram memory management has changed significantly (This also affects old, binary histograms).
• Use by the optimizer. You can look into the MTR tests and find examples like this:

analyze select * from tbl where col1= const

analyze select * from tbl where col1< const

analyze select * from tbl where col1 between const1 and const2 

There is only one column col1 which is not indexed. The interesting parts of the output are filtered (prediction from the histogram) and r_filtered (actual value).

There will be differences in estimates with binary histograms. The estimates should be generally better. Rounding-error-level regressions are acceptable. An estimate that is significantly worse than one from the binary histogram warrants an investigation.

The issue in MySQL that I was mentioning: https://bugs.mysql.com/bug.php?id=104789

Pushed more cleanup patches to https://github.com/MariaDB/server/tree/bb-10.7-mdev21130 . Buildbot is clean.

Descriptions in the server for system variables need updating as well, for example histogram_type still states "Specifies type of the histograms created by ANALYZE. Possible values are: SINGLE_PREC_HB - single precision height-balanced, DOUBLE_PREC_HB - double precision height-balanced." even though JSON_HB is valid as well.

Pushed into 10.8. JSON_HB histograms are not enabled by default.