MariaDB and MySQL — what statistics optimizer needs
Golubchik, Sergei
When your SQL query reaches the DBMS, it's the optimizer job to decide how to execute it for you to get the result as fast as possible. To make this decision optimizer can examine the actual table data, but with multi giga- and terabyte tables, the only practical solution is to use various data statistics that was collected in advance. The better the statistics is and the more precisely it describes the actual data, the faster the plan will be, because optimizer image of the reality will be closer to the actual reality. In this talk you'll learn what data statistics MariaDB and MySQL can collect, what statements do that, how to tell the optimizer to use it (it won't necessarily do it automatically!) and how it can make your queries many times faster. And, of course, when not to use indexes, when up-to-date statistics is enough.
 So this is the talk about myDB and MySQL about statistics that optimizes needs to optimize for queries and when and how not to use indexes. I'll, okay, so I've worked in MyDB, in operation as chief architect in MyDB and I was working on MySQL code base for like 20 years, so I'm pretty familiar with it. Let's start the talk. So what, statistics optimize the needs. So when optimizer, optimizes your query, it needs to know something about the data. And usually, well, tradition was done by optimizer was asking engine different questions, like, I don't know, how many rows does this table have or how much would it cost to do the full table scan and cost is in some arbitrary cost units, not in microseconds or CPU cycles or anything. Or for example, how much would it cost to read a thousand values from the index number three and then optimizer would compare this cost with the cost of the full table scan and decide whether it's cheaper. Or how many distinct values are in the index and then if the index has say 10 million rows and there are one million distinct values, then optimizer would assume that every value is present about 10 times in the index. Or optimizer could ask how many rows, how many index values lie in the range between say 10,000 and 11,000. And then it would ask the cost to read them and then it would compare with the full table scan and so on. That works reasonably well, but there are some issues with that. And one of the problems is instability. Not all engines has these values all the time already. They calculate them on the fly and in a DB for example is doing it using random index dives and because they are random, they supposedly don't have any bias on the other hand because they are random, they do not give repeatable results. And those are the tests I've done on DBT3 benchmarks on a query from DBT3 number Q8. The eight DB tables involved in this query and just by repeating many times, I have seen four different execution plans and with a query execution time ranging from seven minutes to 1.2 hours. And for Q7, I've seen seven different plans. The fastest one was executing in 12 minutes and the longest one, I just waited for few hours and killed the query because I got impatient. So it's not what you would prefer to have. Some might ask what about in a DB persistent statistics and it does solve the instability problem in a way that DB is still doing those random dives and then it remembers the results in an internal table and next time it will just show you the same result. So there's no instability, always get the same result and the same execution plan. But because it still started from the random dives, if you're lucky you'll get always the same execution plan and the query will always execute in 12 minutes. If you're unlucky, you'll get always the same plan and it will always be many hours and time out. If you don't even know how many plans are there, so you might just think that query is slow if it always time out, time out after many hours, but it may be just that you got bad random dives. Another problem is that all engines, they do report statistics in arbitrary cost units, but they are different cost units for different engines and engines lie about what data are in the table. This is an example, I have a table with three integer columns and I populated every column with a random number between 1, 0 and 100,000 and repeated it 400,000 times. And now I do select count distinct, which is honest exact skill calculation to get the number of distinct values and what do you think what number I'll get here? Anybody could guess? Who's not looking in his own laptop? Okay, it was 400,000 rows and numbers are between 100,000 and 100,000, so it should be about 100,000 distinct values and this is exactly what I've got. But this query takes a lot of time to calculate, so usually optimizer relies on some imprecise estimations done by the engine. So the engine is myISOM here and here I asked the engine for the estimation how many distinct values are in the index and myISOM would estimate it, it's not exact number but it's within 1%, which is good enough for the optimizer planning point of view. Now I change the table to NADB and we'll look not worth time to guess. NADB reports 200,000 distinct values and if you remember that the table contains integers between 0 and 100,000 that cannot possibly be 200,000 distinct values in there. But what does it mean for the optimizer? So there are 400,000 rows in the table and there are 100 distinct values. It means that optimizer would expect every single value to be present in the table four times. If you look for the specific value, optimizer would expect to find four rows. But in NADB lies there are twice as many distinct values as there actually are, so optimizer would think there are only two rows to be found. So optimizer will be more likely to prefer an index in a NADB case because NADB lies about statistics. And why NADB is doing that? Well like 15 to 20 years ago the original NADB author back then, Heiki Tauri, he just noticed that for some query NADB doesn't use the index and he would like my skill to use the index. So he just edit times two and make the index twice as more attractive to the optimizer and he was happy with that. And since then, because there are many years past, optimizer just kind of adapted and it's probably embedded in many parts of the assumptions that NADB is doing that. And as far as I know they removed these times two in my skill age. So the other problem of course that if you need all the statistics you need an index. In index it's, you need to pay the price for an index, index they take space, they take time to be maintained and usually, not usually, often if you just need statistics and index it's just too much price to pay to expensive. And a solution, so from now on I'll be talking about MariaDB for a while and then later I'll describe the differences with my skill and new MariaDB versions. So this is the solution that was implemented in MariaDB called Engine Independent Table Statistics and it is provided, provides stable, precise, detailed and comparable statistics. So it's stable because statistics is calculated once and then stored in persistent tables. It's not calculated anytime using some random dives. It's precise because MariaDB analyzes all the data not just very, very small percentage of the data. So it gets very good representation of what the data is and statistics is actually close to actual data. It's detailed because this Engine Independent Statistics remembers a lot more information than just cardinality, than just one number. So it can, it allows optimizer to know more about the data and create better execution plans. And it's calculated by the server not by the engine. So it's calculated identical for all engines. So cost estimations are identical and they're comparable. So optimizer can calculate the cost for one table and one engine and for another table in different engine and then compare them and decide in what order is better to execute the query, for example, join. Now I'm not going to decide the manual. So this is just, I'm just giving you a few pointers, few keywords. If you're interested, you either download my talk later or just make a picture of the slide and these are the words you can later look up in the manual. So very briefly, it is implemented by having new tables in the MySQL schema where all the information, all the statistics stored. There's a new system variable calls, use that tables, or the tell that to my when to use information, these Engine Independent Statistics. It could be never used or preferable in some. And this optimizes use condition selectivity, which I'll be talking about for the rest of my talk, which tells the optimizer which exactly parts of the Engine Independent Statistics optimizes allowed to use. And there are optional clauses in the analyze table that can, where you can specify what parts of the table should be, for what parts of the table the statistics should be calculated. It could be done for all table or for only some indexes or for only some columns. But enough of this theory. Now let's get to the examples. And for the examples, I use the employees database, which can be downloaded from the Gzepers GitHub and Gzepers, the guy who was giving talk just before. It's not a very big data set, but it's not exactly small. Either it's 167 megabytes of data and the employees table has 300,000 records and started table has like 2.8 million records. So let's load it. It's, you need to download it from the Gzepers GitHub, then you sort, do source employees that are scaling, which creates all the table and performs all the load data to load all the data. And then I enable Engine Independent Table Statistics by setting use that tables preferably. Then I analyze all the table to collect the statistics. There's no need to specify any optional clauses for the analyze here, because if statistics is enabled preferably, then analyze will automatically do collect all the Engine Independent Statistics. So you don't need to modify your application and rewrite all the analyze table statements. You just need to enable Engine Independent Statistics once and then it will automatically work for the, for the, all of your application. And you can see that it's not a very big data set because this one took only less than 30 seconds. So how does this one help to optimize your queries? First I said optimize use condition selectivity 1, which tells optimizer not to use any, any Engine Independent Statistics. Basically it only uses the data that were available before Engine Independent Statistics was introduced. And I want to find all the managers from all departments in this example in place database. So I join departments with employees, with manager, with titles, where title equals manager. And for the purpose of the example, it's important to remember that title column is not indexed. Then my ADB does something with the data and returns the result set in 15 seconds. Now I enable optimize use condition selectivity 3, which allows optimizer to use per column statistics, statistics for non-index columns. And the same query is executed under a second. This is 16 times improvement. It's not 16 percent, it's not 1.6 times, it's 16 times improvement. And so it's pretty remarkable to me. And let's see why does this happen. This is a result of explain extended for the first query when the optimizer cannot use per column statistics. It is explain extended. So there's column filtered, which tells how many, what percentage of the table optimizer thinks will pass the where close. And because there's no data available for non-index columns, optimizer doesn't know, so he just says 100 percent, everything might pass the where close. But if we enable, if we allow optimized use per column statistics, statistics for not index columns, then optimizer knows the cardinality for non-index columns and minimal amount of value for non-index columns. And optimizer can figure out that not all employees are in fact managers. And only about 14 percent of the titles will match the where close. And in this case, optimizer decides to join tables in different order. And I start from full table scan of the titles table. And this gives 16 times improvement. Now before talking about histograms, I want to explain what the equi-height histogram is. This is not an equi-height histogram. It's a usual histogram that you see everywhere. It's equi-width histograms. The red line just shows some imaginary data distribution. And this is histogram for this data distribution under the red line. I've drawn it with five bars, five buckets. They all have the same width. That's why it's called equi-width. And the height of the bar is proportional to the area under the curve. And this is the equi-height histogram where all the bars have the same height, but different width. There are also five of them, but in this case, the area under the curve is all, might be all the same. And why would we want to do this strange thing instead of normal histograms? Because all we remember for every column is those five numbers, well, more than five, but still, fixate number of bars to describe a histogram. And then later, optimizer needs to use this data to kind of restore the original data distribution to understand the original data distribution. And if optimizer would try to restore the original distribution based on the equi-width histogram, this is what it would get. You see that the huge error in the most interesting part of the curve where the values are high. And if you try to restore the curve from the equi-height histogram, the interesting part of the curve is described much more precisely. The error is much smaller. Basically equi-height histogram allows you to describe the data distribution much more precisely with a smaller number of values. This is what my ADB is using for histograms. Now let's see how histograms are helping to optimize the queries. And for this one, we need an example of some data with non-uniform distribution. Let's look at the salary values from the emplaced database and we calculate the mid-point, mid-salary, that's exactly in the middle between minimum and maximum salary. That's the first query, it's about 100,000. And now let's see, let's select all the employees and their titles from the salary table where the salary was above the mid-point, above the 100,000. Again in some time after turn some data, my ADB returns a result in 18 seconds, 19 seconds. But if we enable the use of histograms by setting optimized use condition selectivity equals 4, you'll get the same result 3 times faster. Again, why is this happening? Because if you don't use histograms, then all the data that optimizer knows about the table is, it knows the minimum value for the salary, it knows the maximum value for the salary. And because we are searching for everything which is above the mid-point, optimizer can figure out, okay, so this is mid-point. So about half of the data should be above mid-point, about half of the data should be below mid-point. Let's optimize the things, and indeed you see the filtered column is about 50%. Let's optimize the things that half of the rows will pass the where clause. But at least half of the rows would have passed the where clause if the salary would be distributed uniformly. But in this employee database, just like in the real world, you know, so let's distribute it very non-uniformly. And if we enable histograms, optimizer can see that indeed only less than 5% of salaries lie above the mid-point. In this case, optimizer again joins tables in different order and gives, it gives a 3 times speedup. The next interesting feature that was implemented is sampling. So this is a query which could be realistically used by, I don't know, HR department by analyzing whether there's a distributed fair or there are some people are getting low salaries based on, I don't know, sex or origin or whatever. But this query, it takes the average salary per department for all the people whose last name ends with off, which supposedly could mean people with slight origin. As you know, those kind of like queries, you cannot optimize it. You cannot optimize it from the index, you cannot get any reasonable histogram for that. You cannot get any reasonable statistics for that. So optimizer doesn't know anything about this. And it finds five rows because it's grouped by department in five seconds. And if we enable sampling, you get the same result 12 times faster. Yes. So how does sampling work? Because there's no other way for optimizer to get any reasonable information about the data. So it reads few rows from the table and applies this like condition. And then it extrapolates the result to the rest of the table. And indeed, without sampling, you can see that filtered column is 100% because there's no histograms, no indexes, nothing that could help optimizer to know anything about the data. So in sampling, optimizer can realize that indeed very little, there are very few rows that matches that were close. And it optimizes joint tables in different order. And this is 12 times speed up. Everything that I was talking about now, it was implemented in MariaDB 10.0, which went GA in 2014. So it was, it's quite stable. Well, in fact, 10.0 is already, it's end of life. So don't use that, at least in one. And in this MariaDB 10.0, engine independent statistic remembers the number of rows per table and the cardinality per index. And for every column, it remembers number of distinct values, minimal and maximum value, amount of nulls, average value length for strings, and this acrythia histogram. And sampling also works. Last year, Maria, Mace-Coil 80 went GA. They implemented a conceptually similar feature. It's called, differently, it's called optimized statistic in Mace-Coil. And they remember amount of nulls per column. And but they have two different kinds of histograms. They have acrythia histograms and singleton histograms and singleton works much better than acrythia if you have data with very few distinct values. Like if you have a sex column or a column with yes, no values. These guys were singleton histograms work and acrythia basically don't. Also if you try to do, try to collect a histogram for really, really huge table, then Mace-Coil starts keeping values to keep all the data in the memory and it gives significant speed up as compared to how MariaDB 10.0 collects histograms on the huge tables. And in a few months, MariaDB 10.4 will become GA where this engine is enabled by default, which is basically the main reason why I'm giving this talk. So if you start upgrading, you should know this enable or default, you don't need to do anything anymore. Everything will just automatically and magically be faster. And MariaDB 10.4 also collects histogram by sampling, by skipping values so that analyzed table will be fast. And in MariaDB before 10.4, analyze for engine statistics was slow. This was the reason why it wasn't enabled by default. And this feature was mostly implemented as a Google Summer of Code project last year. That's all. Thank you. Have any questions? Yes? Again by this one? I'm talking about this one. Yeah, so the question is about how I compared the results and execution times for the same query. It was the same system and I would just repeat it many times. I repeated explain many times, I repeated just select many times in different order. I was collecting how many different selects, how many different explains output I would see. And caching does not affect the explained output. And yeah, execution time as well. I think after the cache was warmed up, so this shouldn't be taken into account. After the result, I was also collecting the results that were stable. Yes. I'm sorry, I didn't think about that. Is there a plan to collect the statistics on the fly? So the question is, is there any plans to collect statistics on the fly? We are thinking about that, but it will not be in Marini bit and form.
 So this is the talk about myDB and MySQL about statistics that optimizes needs to optimize  for queries and when and how not to use indexes.  I'll, okay, so I've worked in MyDB, in operation as chief architect in MyDB and I was working  on MySQL code base for like 20 years, so I'm pretty familiar with it.  Let's start the talk.  So what, statistics optimize the needs.  So when optimizer, optimizes your query, it needs to know something about the data.  And usually, well, tradition was done by optimizer was asking engine different questions, like,  I don't know, how many rows does this table have or how much would it cost to do the full  table scan and cost is in some arbitrary cost units, not in microseconds or CPU cycles or  anything.  Or for example, how much would it cost to read a thousand values from the index number  three and then optimizer would compare this cost with the cost of the full table scan  and decide whether it's cheaper.  Or how many distinct values are in the index and then if the index has say 10 million rows  and there are one million distinct values, then optimizer would assume that every value  is present about 10 times in the index.  Or optimizer could ask how many rows, how many index values lie in the range between  say 10,000 and 11,000.  And then it would ask the cost to read them and then it would compare with the full table  scan and so on.  That works reasonably well, but there are some issues with that.  And one of the problems is instability.  Not all engines has these values all the time already.  They calculate them on the fly and in a DB for example is doing it using random index  dives and because they are random, they supposedly don't have any bias on the other hand because  they are random, they do not give repeatable results.  And those are the tests I've done on DBT3 benchmarks on a query from DBT3 number Q8.  The eight DB tables involved in this query and just by repeating many times, I have seen  four different execution plans and with a query execution time ranging from seven minutes  to 1.2 hours.  And for Q7, I've seen seven different plans.  The fastest one was executing in 12 minutes and the longest one, I just waited for few  hours and killed the query because I got impatient.  So it's not what you would prefer to have.  Some might ask what about in a DB persistent statistics and it does solve the instability  problem in a way that DB is still doing those random dives and then it remembers the results  in an internal table and next time it will just show you the same result.  So there's no instability, always get the same result and the same execution plan.  But because it still started from the random dives, if you're lucky you'll get always the  same execution plan and the query will always execute in 12 minutes.  If you're unlucky, you'll get always the same plan and it will always be many hours and  time out.  If you don't even know how many plans are there, so you might just think that query  is slow if it always time out, time out after many hours, but it may be just that you got  bad random dives.  Another problem is that all engines, they do report statistics in arbitrary cost units,  but they are different cost units for different engines and engines lie about what data are  in the table.  This is an example, I have a table with three integer columns and I populated every column  with a random number between 1, 0 and 100,000 and repeated it 400,000 times.  And now I do select count distinct, which is honest exact skill calculation to get the  number of distinct values and what do you think what number I'll get here?  Anybody could guess?  Who's not looking in his own laptop?  Okay, it was 400,000 rows and numbers are between 100,000 and 100,000, so it should  be about 100,000 distinct values and this is exactly what I've got.  But this query takes a lot of time to calculate, so usually optimizer relies on some imprecise  estimations done by the engine.  So the engine is myISOM here and here I asked the engine for the estimation how many distinct  values are in the index and myISOM would estimate it, it's not exact number but it's within  1%, which is good enough for the optimizer planning point of view.  Now I change the table to NADB and we'll look not worth time to guess.  NADB reports 200,000 distinct values and if you remember that the table contains integers  between 0 and 100,000 that cannot possibly be 200,000 distinct values in there.  But what does it mean for the optimizer?  So there are 400,000 rows in the table and there are 100 distinct values.  It means that optimizer would expect every single value to be present in the table four  times.  If you look for the specific value, optimizer would expect to find four rows.  But in NADB lies there are twice as many distinct values as there actually are, so optimizer  would think there are only two rows to be found.  So optimizer will be more likely to prefer an index in a NADB case because NADB lies  about statistics.  And why NADB is doing that?  Well like 15 to 20 years ago the original NADB author back then, Heiki Tauri, he just  noticed that for some query NADB doesn't use the index and he would like my skill to  use the index.  So he just edit times two and make the index twice as more attractive to the optimizer  and he was happy with that.  And since then, because there are many years past, optimizer just kind of adapted and it's  probably embedded in many parts of the assumptions that NADB is doing that.  And as far as I know they removed these times two in my skill age.  So the other problem of course that if you need all the statistics you need an index.  In index it's, you need to pay the price for an index, index they take space, they take  time to be maintained and usually, not usually, often if you just need statistics and index  it's just too much price to pay to expensive.  And a solution, so from now on I'll be talking about MariaDB for a while and then later I'll  describe the differences with my skill and new MariaDB versions.  So this is the solution that was implemented in MariaDB called Engine Independent Table  Statistics and it is provided, provides stable, precise, detailed and comparable statistics.  So it's stable because statistics is calculated once and then stored in persistent tables.  It's not calculated anytime using some random dives.  It's precise because MariaDB analyzes all the data not just very, very small percentage  of the data.  So it gets very good representation of what the data is and statistics is actually close  to actual data.  It's detailed because this Engine Independent Statistics remembers a lot more information  than just cardinality, than just one number.  So it can, it allows optimizer to know more about the data and create better execution  plans.  And it's calculated by the server not by the engine.  So it's calculated identical for all engines.  So cost estimations are identical and they're comparable.  So optimizer can calculate the cost for one table and one engine and for another table  in different engine and then compare them and decide in what order is better to execute  the query, for example, join.  Now I'm not going to decide the manual.  So this is just, I'm just giving you a few pointers, few keywords.  If you're interested, you either download my talk later or just make a picture of the  slide and these are the words you can later look up in the manual.  So very briefly, it is implemented by having new tables in the MySQL schema where all the  information, all the statistics stored.  There's a new system variable calls, use that tables, or the tell that to my when to use  information, these Engine Independent Statistics.  It could be never used or preferable in some.  And this optimizes use condition selectivity, which I'll be talking about for the rest of  my talk, which tells the optimizer which exactly parts of the Engine Independent Statistics  optimizes allowed to use.  And there are optional clauses in the analyze table that can, where you can specify what  parts of the table should be, for what parts of the table the statistics should be calculated.  It could be done for all table or for only some indexes or for only some columns.  But enough of this theory.  Now let's get to the examples.  And for the examples, I use the employees database, which can be downloaded from the  Gzepers GitHub and Gzepers, the guy who was giving talk just before.  It's not a very big data set, but it's not exactly small.  Either it's 167 megabytes of data and the employees table has 300,000 records and started  table has like 2.8 million records.  So let's load it.  It's, you need to download it from the Gzepers GitHub, then you sort, do source employees  that are scaling, which creates all the table and performs all the load data to load all  the data.  And then I enable Engine Independent Table Statistics by setting use that tables preferably.  Then I analyze all the table to collect the statistics.  There's no need to specify any optional clauses for the analyze here, because if statistics  is enabled preferably, then analyze will automatically do collect all the Engine Independent Statistics.  So you don't need to modify your application and rewrite all the analyze table statements.  You just need to enable Engine Independent Statistics once and then it will automatically  work for the, for the, all of your application.  And you can see that it's not a very big data set because this one took only less than  30 seconds.  So how does this one help to optimize your queries?  First I said optimize use condition selectivity 1, which tells optimizer not to use any,  any Engine Independent Statistics.  Basically it only uses the data that were available before Engine Independent Statistics  was introduced.  And I want to find all the managers from all departments in this example in place database.  So I join departments with employees, with manager, with titles, where title equals manager.  And for the purpose of the example, it's important to remember that title column is not indexed.  Then my ADB does something with the data and returns the result set in 15 seconds.  Now I enable optimize use condition selectivity 3, which allows optimizer to use per column  statistics, statistics for non-index columns.  And the same query is executed under a second.  This is 16 times improvement.  It's not 16 percent, it's not 1.6 times, it's 16 times improvement.  And so it's pretty remarkable to me.  And let's see why does this happen.  This is a result of explain extended for the first query when the optimizer cannot use per  column statistics.  It is explain extended.  So there's column filtered, which tells how many, what percentage of the table optimizer  thinks will pass the where close.  And because there's no data available for non-index columns, optimizer doesn't know,  so he just says 100 percent, everything might pass the where close.  But if we enable, if we allow optimized use per column statistics, statistics for not  index columns, then optimizer knows the cardinality for non-index columns and minimal amount of  value for non-index columns.  And optimizer can figure out that not all employees are in fact managers.  And only about 14 percent of the titles will match the where close.  And in this case, optimizer decides to join tables in different order.  And I start from full table scan of the titles table.  And this gives 16 times improvement.  Now before talking about histograms, I want to explain what the equi-height histogram  is.  This is not an equi-height histogram.  It's a usual histogram that you see everywhere.  It's equi-width histograms.  The red line just shows some imaginary data distribution.  And this is histogram for this data distribution under the red line.  I've drawn it with five bars, five buckets.  They all have the same width.  That's why it's called equi-width.  And the height of the bar is proportional to the area under the curve.  And this is the equi-height histogram where all the bars have the same height, but different  width.  There are also five of them, but in this case, the area under the curve is all, might be  all the same.  And why would we want to do this strange thing instead of normal histograms?  Because all we remember for every column is those five numbers, well, more than five,  but still, fixate number of bars to describe a histogram.  And then later, optimizer needs to use this data to kind of restore the original data  distribution to understand the original data distribution.  And if optimizer would try to restore the original distribution based on the equi-width  histogram, this is what it would get.  You see that the huge error in the most interesting part of the curve where the values are high.  And if you try to restore the curve from the equi-height histogram, the interesting part  of the curve is described much more precisely.  The error is much smaller.  Basically equi-height histogram allows you to describe the data distribution much more  precisely with a smaller number of values.  This is what my ADB is using for histograms.  Now let's see how histograms are helping to optimize the queries.  And for this one, we need an example of some data with non-uniform distribution.  Let's look at the salary values from the emplaced database and we calculate the mid-point,  mid-salary, that's exactly in the middle between minimum and maximum salary.  That's the first query, it's about 100,000.  And now let's see, let's select all the employees and their titles from the salary table where  the salary was above the mid-point, above the 100,000.  Again in some time after turn some data, my ADB returns a result in 18 seconds, 19 seconds.  But if we enable the use of histograms by setting optimized use condition selectivity  equals 4, you'll get the same result 3 times faster.  Again, why is this happening?  Because if you don't use histograms, then all the data that optimizer knows about the  table is, it knows the minimum value for the salary, it knows the maximum value for the  salary.  And because we are searching for everything which is above the mid-point, optimizer can  figure out, okay, so this is mid-point.  So about half of the data should be above mid-point, about half of the data should be  below mid-point.  Let's optimize the things, and indeed you see the filtered column is about 50%.  Let's optimize the things that half of the rows will pass the where clause.  But at least half of the rows would have passed the where clause if the salary would be distributed  uniformly.  But in this employee database, just like in the real world, you know, so let's distribute  it very non-uniformly.  And if we enable histograms, optimizer can see that indeed only less than 5% of salaries  lie above the mid-point.  In this case, optimizer again joins tables in different order and gives, it gives a 3  times speedup.  The next interesting feature that was implemented is sampling.  So this is a query which could be realistically used by, I don't know, HR department by analyzing  whether there's a distributed fair or there are some people are getting low salaries based  on, I don't know, sex or origin or whatever.  But this query, it takes the average salary per department for all the people whose last  name ends with off, which supposedly could mean people with slight origin.  As you know, those kind of like queries, you cannot optimize it.  You cannot optimize it from the index, you cannot get any reasonable histogram for that.  You cannot get any reasonable statistics for that.  So optimizer doesn't know anything about this.  And it finds five rows because it's grouped by department in five seconds.  And if we enable sampling, you get the same result 12 times faster.  Yes.  So how does sampling work?  Because there's no other way for optimizer to get any reasonable information about the  data.  So it reads few rows from the table and applies this like condition.  And then it extrapolates the result to the rest of the table.  And indeed, without sampling, you can see that filtered column is 100% because there's  no histograms, no indexes, nothing that could help optimizer to know anything about the  data.  So in sampling, optimizer can realize that indeed very little, there are very few rows  that matches that were close.  And it optimizes joint tables in different order.  And this is 12 times speed up.  Everything that I was talking about now, it was implemented in MariaDB 10.0, which went  GA in 2014.  So it was, it's quite stable.  Well, in fact, 10.0 is already, it's end of life.  So don't use that, at least in one.  And in this MariaDB 10.0, engine independent statistic remembers the number of rows per  table and the cardinality per index.  And for every column, it remembers number of distinct values, minimal and maximum value,  amount of nulls, average value length for strings, and this acrythia histogram.  And sampling also works.  Last year, Maria, Mace-Coil 80 went GA.  They implemented a conceptually similar feature.  It's called, differently, it's called optimized statistic in Mace-Coil.  And they remember amount of nulls per column.  And but they have two different kinds of histograms.  They have acrythia histograms and singleton histograms and singleton works much better  than acrythia if you have data with very few distinct values.  Like if you have a sex column or a column with yes, no values.  These guys were singleton histograms work and acrythia basically don't.  Also if you try to do, try to collect a histogram for really, really huge table, then Mace-Coil  starts keeping values to keep all the data in the memory and it gives significant speed  up as compared to how MariaDB 10.0 collects histograms on the huge tables.  And in a few months, MariaDB 10.4 will become GA where this engine is enabled by default,  which is basically the main reason why I'm giving this talk.  So if you start upgrading, you should know this enable or default, you don't need to  do anything anymore.  Everything will just automatically and magically be faster.  And MariaDB 10.4 also collects histogram by sampling, by skipping values so that analyzed  table will be fast.  And in MariaDB before 10.4, analyze for engine statistics was slow.  This was the reason why it wasn't enabled by default.  And this feature was mostly implemented as a Google Summer of Code project last year.  That's all.  Thank you.  Have any questions?  Yes?  Again by this one?  I'm talking about this one.  Yeah, so the question is about how I compared the results and execution times for the same query.  It was the same system and I would just repeat it many times.  I repeated explain many times, I repeated just select many times in different order.  I was collecting how many different selects, how many different explains output I would see.  And caching does not affect the explained output.  And yeah, execution time as well.  I think after the cache was warmed up, so this shouldn't be taken into account.  After the result, I was also collecting the results that were stable.  Yes.  I'm sorry, I didn't think about that.  Is there a plan to collect the statistics on the fly?  So the question is, is there any plans to collect statistics on the fly?  We are thinking about that, but it will not be in Marini bit and form.
MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_0_167.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_168_395.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_396_755.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_756_2603.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_2604_5159.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_5160_6875.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_6876_6935.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_6936_9635.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_9636_12167.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_12168_13739.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_13740_17135.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_17136_18839.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_18840_18935.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_18936_21479.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_21480_22799.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_22800_24407.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_24408_26375.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_26376_27083.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_27084_28019.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_28020_28295.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_28296_28547.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_28548_28703.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_28704_28943.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_28944_29075.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_29076_29171.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_29172_29327.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_29328_29387.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_29388_30431.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_30432_31163.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_31164_33095.png MariaDB_and_MySQL___what_statistics_optimizer_needs_or_when_and_how_not_to_use_indexes_x5anyspAN3s_33096_33216.png
So this is the talk about myDB and MySQL about statistics that optimizes needs to optimize for queries and when and how not to use indexes. I'll, okay, so I've worked in MyDB, in operation as chief architect in MyDB and I was working on MySQL code base for like 20 years, so I'm pretty familiar with it. Let's start the talk. So what, statistics optimize the needs. So when optimizer, optimizes your query, it needs to know something about the data. And usually, well, tradition was done by optimizer was asking engine different questions, like, I don't know, how many rows does this table have or how much would it cost to do the full table scan and cost is in some arbitrary cost units, not in microseconds or CPU cycles or anything. Or for example, how much would it cost to read a thousand values from the index number three and then optimizer would compare this cost with the cost of the full table scan and decide whether it's cheaper. Or how many distinct values are in the index and then if the index has say 10 million rows and there are one million distinct values, then optimizer would assume that every value is present about 10 times in the index. Or optimizer could ask how many rows, how many index values lie in the range between say 10,000 and 11,000. And then it would ask the cost to read them and then it would compare with the full table scan and so on. That works reasonably well, but there are some issues with that. And one of the problems is instability. Not all engines has these values all the time already. They calculate them on the fly and in a DB for example is doing it using random index dives and because they are random, they supposedly don't have any bias on the other hand because they are random, they do not give repeatable results. And those are the tests I've done on DBT3 benchmarks on a query from DBT3 number Q8. The eight DB tables involved in this query and just by repeating many times, I have seen four different execution plans and with a query execution time ranging from seven minutes to 1.2 hours. And for Q7, I've seen seven different plans. The fastest one was executing in 12 minutes and the longest one, I just waited for few hours and killed the query because I got impatient. So it's not what you would prefer to have. Some might ask what about in a DB persistent statistics and it does solve the instability problem in a way that DB is still doing those random dives and then it remembers the results in an internal table and next time it will just show you the same result. So there's no instability, always get the same result and the same execution plan. But because it still started from the random dives, if you're lucky you'll get always the same execution plan and the query will always execute in 12 minutes. If you're unlucky, you'll get always the same plan and it will always be many hours and time out. If you don't even know how many plans are there, so you might just think that query is slow if it always time out, time out after many hours, but it may be just that you got bad random dives. Another problem is that all engines, they do report statistics in arbitrary cost units, but they are different cost units for different engines and engines lie about what data are in the table. This is an example, I have a table with three integer columns and I populated every column with a random number between 1, 0 and 100,000 and repeated it 400,000 times. And now I do select count distinct, which is honest exact skill calculation to get the number of distinct values and what do you think what number I'll get here? Anybody could guess? Who's not looking in his own laptop? Okay, it was 400,000 rows and numbers are between 100,000 and 100,000, so it should be about 100,000 distinct values and this is exactly what I've got. But this query takes a lot of time to calculate, so usually optimizer relies on some imprecise estimations done by the engine. So the engine is myISOM here and here I asked the engine for the estimation how many distinct values are in the index and myISOM would estimate it, it's not exact number but it's within 1%, which is good enough for the optimizer planning point of view. Now I change the table to NADB and we'll look not worth time to guess. NADB reports 200,000 distinct values and if you remember that the table contains integers between 0 and 100,000 that cannot possibly be 200,000 distinct values in there. But what does it mean for the optimizer? So there are 400,000 rows in the table and there are 100 distinct values. It means that optimizer would expect every single value to be present in the table four times. If you look for the specific value, optimizer would expect to find four rows. But in NADB lies there are twice as many distinct values as there actually are, so optimizer would think there are only two rows to be found. So optimizer will be more likely to prefer an index in a NADB case because NADB lies about statistics. And why NADB is doing that? Well like 15 to 20 years ago the original NADB author back then, Heiki Tauri, he just noticed that for some query NADB doesn't use the index and he would like my skill to use the index. So he just edit times two and make the index twice as more attractive to the optimizer and he was happy with that. And since then, because there are many years past, optimizer just kind of adapted and it's probably embedded in many parts of the assumptions that NADB is doing that. And as far as I know they removed these times two in my skill age. So the other problem of course that if you need all the statistics you need an index. In index it's, you need to pay the price for an index, index they take space, they take time to be maintained and usually, not usually, often if you just need statistics and index it's just too much price to pay to expensive. And a solution, so from now on I'll be talking about MariaDB for a while and then later I'll describe the differences with my skill and new MariaDB versions. So this is the solution that was implemented in MariaDB called Engine Independent Table Statistics and it is provided, provides stable, precise, detailed and comparable statistics. So it's stable because statistics is calculated once and then stored in persistent tables. It's not calculated anytime using some random dives. It's precise because MariaDB analyzes all the data not just very, very small percentage of the data. So it gets very good representation of what the data is and statistics is actually close to actual data. It's detailed because this Engine Independent Statistics remembers a lot more information than just cardinality, than just one number. So it can, it allows optimizer to know more about the data and create better execution plans. And it's calculated by the server not by the engine. So it's calculated identical for all engines. So cost estimations are identical and they're comparable. So optimizer can calculate the cost for one table and one engine and for another table in different engine and then compare them and decide in what order is better to execute the query, for example, join. Now I'm not going to decide the manual. So this is just, I'm just giving you a few pointers, few keywords. If you're interested, you either download my talk later or just make a picture of the slide and these are the words you can later look up in the manual. So very briefly, it is implemented by having new tables in the MySQL schema where all the information, all the statistics stored. There's a new system variable calls, use that tables, or the tell that to my when to use information, these Engine Independent Statistics. It could be never used or preferable in some. And this optimizes use condition selectivity, which I'll be talking about for the rest of my talk, which tells the optimizer which exactly parts of the Engine Independent Statistics optimizes allowed to use. And there are optional clauses in the analyze table that can, where you can specify what parts of the table should be, for what parts of the table the statistics should be calculated. It could be done for all table or for only some indexes or for only some columns. But enough of this theory. Now let's get to the examples. And for the examples, I use the employees database, which can be downloaded from the Gzepers GitHub and Gzepers, the guy who was giving talk just before. It's not a very big data set, but it's not exactly small. Either it's 167 megabytes of data and the employees table has 300,000 records and started table has like 2.8 million records. So let's load it. It's, you need to download it from the Gzepers GitHub, then you sort, do source employees that are scaling, which creates all the table and performs all the load data to load all the data. And then I enable Engine Independent Table Statistics by setting use that tables preferably. Then I analyze all the table to collect the statistics. There's no need to specify any optional clauses for the analyze here, because if statistics is enabled preferably, then analyze will automatically do collect all the Engine Independent Statistics. So you don't need to modify your application and rewrite all the analyze table statements. You just need to enable Engine Independent Statistics once and then it will automatically work for the, for the, all of your application. And you can see that it's not a very big data set because this one took only less than 30 seconds. So how does this one help to optimize your queries? First I said optimize use condition selectivity 1, which tells optimizer not to use any, any Engine Independent Statistics. Basically it only uses the data that were available before Engine Independent Statistics was introduced. And I want to find all the managers from all departments in this example in place database. So I join departments with employees, with manager, with titles, where title equals manager. And for the purpose of the example, it's important to remember that title column is not indexed. Then my ADB does something with the data and returns the result set in 15 seconds. Now I enable optimize use condition selectivity 3, which allows optimizer to use per column statistics, statistics for non-index columns. And the same query is executed under a second. This is 16 times improvement. It's not 16 percent, it's not 1.6 times, it's 16 times improvement. And so it's pretty remarkable to me. And let's see why does this happen. This is a result of explain extended for the first query when the optimizer cannot use per column statistics. It is explain extended. So there's column filtered, which tells how many, what percentage of the table optimizer thinks will pass the where close. And because there's no data available for non-index columns, optimizer doesn't know, so he just says 100 percent, everything might pass the where close. But if we enable, if we allow optimized use per column statistics, statistics for not index columns, then optimizer knows the cardinality for non-index columns and minimal amount of value for non-index columns. And optimizer can figure out that not all employees are in fact managers. And only about 14 percent of the titles will match the where close. And in this case, optimizer decides to join tables in different order. And I start from full table scan of the titles table. And this gives 16 times improvement. Now before talking about histograms, I want to explain what the equi-height histogram is. This is not an equi-height histogram. It's a usual histogram that you see everywhere. It's equi-width histograms. The red line just shows some imaginary data distribution. And this is histogram for this data distribution under the red line. I've drawn it with five bars, five buckets. They all have the same width. That's why it's called equi-width. And the height of the bar is proportional to the area under the curve. And this is the equi-height histogram where all the bars have the same height, but different width. There are also five of them, but in this case, the area under the curve is all, might be all the same. And why would we want to do this strange thing instead of normal histograms? Because all we remember for every column is those five numbers, well, more than five, but still, fixate number of bars to describe a histogram. And then later, optimizer needs to use this data to kind of restore the original data distribution to understand the original data distribution. And if optimizer would try to restore the original distribution based on the equi-width histogram, this is what it would get. You see that the huge error in the most interesting part of the curve where the values are high. And if you try to restore the curve from the equi-height histogram, the interesting part of the curve is described much more precisely. The error is much smaller. Basically equi-height histogram allows you to describe the data distribution much more precisely with a smaller number of values. This is what my ADB is using for histograms. Now let's see how histograms are helping to optimize the queries. And for this one, we need an example of some data with non-uniform distribution. Let's look at the salary values from the emplaced database and we calculate the mid-point, mid-salary, that's exactly in the middle between minimum and maximum salary. That's the first query, it's about 100,000. And now let's see, let's select all the employees and their titles from the salary table where the salary was above the mid-point, above the 100,000. Again in some time after turn some data, my ADB returns a result in 18 seconds, 19 seconds. But if we enable the use of histograms by setting optimized use condition selectivity equals 4, you'll get the same result 3 times faster. Again, why is this happening? Because if you don't use histograms, then all the data that optimizer knows about the table is, it knows the minimum value for the salary, it knows the maximum value for the salary. And because we are searching for everything which is above the mid-point, optimizer can figure out, okay, so this is mid-point. So about half of the data should be above mid-point, about half of the data should be below mid-point. Let's optimize the things, and indeed you see the filtered column is about 50%. Let's optimize the things that half of the rows will pass the where clause. But at least half of the rows would have passed the where clause if the salary would be distributed uniformly. But in this employee database, just like in the real world, you know, so let's distribute it very non-uniformly. And if we enable histograms, optimizer can see that indeed only less than 5% of salaries lie above the mid-point. In this case, optimizer again joins tables in different order and gives, it gives a 3 times speedup. The next interesting feature that was implemented is sampling. So this is a query which could be realistically used by, I don't know, HR department by analyzing whether there's a distributed fair or there are some people are getting low salaries based on, I don't know, sex or origin or whatever. But this query, it takes the average salary per department for all the people whose last name ends with off, which supposedly could mean people with slight origin. As you know, those kind of like queries, you cannot optimize it. You cannot optimize it from the index, you cannot get any reasonable histogram for that. You cannot get any reasonable statistics for that. So optimizer doesn't know anything about this. And it finds five rows because it's grouped by department in five seconds. And if we enable sampling, you get the same result 12 times faster. Yes. So how does sampling work? Because there's no other way for optimizer to get any reasonable information about the data. So it reads few rows from the table and applies this like condition. And then it extrapolates the result to the rest of the table. And indeed, without sampling, you can see that filtered column is 100% because there's no histograms, no indexes, nothing that could help optimizer to know anything about the data. So in sampling, optimizer can realize that indeed very little, there are very few rows that matches that were close. And it optimizes joint tables in different order. And this is 12 times speed up. Everything that I was talking about now, it was implemented in MariaDB 10.0, which went GA in 2014. So it was, it's quite stable. Well, in fact, 10.0 is already, it's end of life. So don't use that, at least in one. And in this MariaDB 10.0, engine independent statistic remembers the number of rows per table and the cardinality per index. And for every column, it remembers number of distinct values, minimal and maximum value, amount of nulls, average value length for strings, and this acrythia histogram. And sampling also works. Last year, Maria, Mace-Coil 80 went GA. They implemented a conceptually similar feature. It's called, differently, it's called optimized statistic in Mace-Coil. And they remember amount of nulls per column. And but they have two different kinds of histograms. They have acrythia histograms and singleton histograms and singleton works much better than acrythia if you have data with very few distinct values. Like if you have a sex column or a column with yes, no values. These guys were singleton histograms work and acrythia basically don't. Also if you try to do, try to collect a histogram for really, really huge table, then Mace-Coil starts keeping values to keep all the data in the memory and it gives significant speed up as compared to how MariaDB 10.0 collects histograms on the huge tables. And in a few months, MariaDB 10.4 will become GA where this engine is enabled by default, which is basically the main reason why I'm giving this talk. So if you start upgrading, you should know this enable or default, you don't need to do anything anymore. Everything will just automatically and magically be faster. And MariaDB 10.4 also collects histogram by sampling, by skipping values so that analyzed table will be fast. And in MariaDB before 10.4, analyze for engine statistics was slow. This was the reason why it wasn't enabled by default. And this feature was mostly implemented as a Google Summer of Code project last year. That's all. Thank you. Have any questions? Yes? Again by this one? I'm talking about this one. Yeah, so the question is about how I compared the results and execution times for the same query. It was the same system and I would just repeat it many times. I repeated explain many times, I repeated just select many times in different order. I was collecting how many different selects, how many different explains output I would see. And caching does not affect the explained output. And yeah, execution time as well. I think after the cache was warmed up, so this shouldn't be taken into account. After the result, I was also collecting the results that were stable. Yes. I'm sorry, I didn't think about that. Is there a plan to collect the statistics on the fly? So the question is, is there any plans to collect statistics on the fly? We are thinking about that, but it will not be in Marini bit and form.
So this is the talk about myDB and MySQL about queries and when and how not to use indexes. in this query and just by repeating many times, I instability, always get the same result and the you'll get always the same plan and it will as more attractive to the optimizer and he was my skill age. So the other problem of course that differences with my skill and new MariaDB versions. So this is the solution that was statistics. So it's stable because statistics is representation of what the data is and statistics and decide in what order is better to execute the tables, or the tell that to my when to use for the, all of your application. And you can see much more precisely. The error is much smaller. optimizer to get any reasonable information about extrapolates the result to the rest of the table. automatically and magically be faster. And collect the statistics on the fly? So the