Overview

MariaDB 10.1.1 introduced the max_statement_time system variable. When set to a non-zero value, any queries taking longer than this time in seconds will be aborted. The default is zero, and no limits are then applied. The aborted query has no effect on any larger transaction or connection contexts. The variable is of type double, thus you can use subsecond timeout. For example you can use value 0.01 for 10 milliseconds timeout.

The value can be set globally or per session, as well as per user or per query (see below). Replicas are not affected by this variable, however from MariaDB 10.10, there is slave_max_statement_time which serves the same purpose on replicas only.

An associated status variable, max_statement_time_exceeded, stores the number of queries that have exceeded the execution time specified by max_statement_time, and a MAX_STATEMENT_TIME_EXCEEDED column was added to the CLIENT_STATISTICS and USER STATISTICS Information Schema tables.

The feature was based upon a patch by Davi Arnaut.

User max_statement_time

max_statement_time can be stored per user with the GRANT ... MAX_STATEMENT_TIME syntax.

Per-query max_statement_time

By using max_statement_time in conjunction with SET STATEMENT, it is possible to limit the execution time of individual queries. For example:

SET STATEMENT max_statement_time=100 FOR 
  SELECT field1 FROM table_name ORDER BY field1;

max_statement_time per query Individual queries can also be limited by adding a MAX_STATEMENT_TIME clause to the query. For example:

SELECT MAX_STATEMENT_TIME=2 * FROM t1;

Limitations

• max_statement_time does not work in embedded servers.

• max_statement_time does not work for COMMIT statements in a Galera cluster (see MDEV-18673 for discussion).

Differences Between the MariaDB and MySQL Implementations

MySQL 5.7.4 introduced similar functionality, but the MariaDB implementation differs in a number of ways.

• The MySQL version of max_statement_time (max_execution_time) is defined in millseconds, not seconds

• MySQL's implementation can only kill SELECTs, while MariaDB's can kill any queries (excluding stored procedures).

• MariaDB only introduced the max_statement_time_exceeded status variable, while MySQL also introduced a number of other variables which were not seen as necessary in MariaDB.

• The SELECT MAX_STATEMENT_TIME = N ... syntax is not valid in MariaDB. In MariaDB one should use SET STATEMENT MAX_STATEMENT_TIME=N FOR....

See Also

• Query limits and timeouts

• lock_wait_timeout variable

_{This page is licensed: CC BY-SA / Gnu FDL}

The problem

How to DELETE lots of rows from a large table? Here is an example of purging items older than 30 days:

DELETE FROM tbl WHERE 
  ts < CURRENT_DATE() - INTERVAL 30 DAY

If there are millions of rows in the table, this statement may take minutes, maybe hours.

Any suggestions on how to speed this up?

Why it is a problem

• MyISAM will lock the table during the entire operation, thereby nothing else can be done with the table.

• InnoDB won't lock the table, but it will chew up a lot of resources, leading to sluggishness.

• InnoDB has to write the undo information to its transaction logs; this significantly increases the I/O required.

• Replication, being asynchronous, will effectively be delayed (on Slaves) while the DELETE is running.

InnoDB and undo

To be ready for a crash, a transactional engine such as InnoDB will record what it is doing to a log file. To make that somewhat less costly, the log file is sequentially written. If the log files you have (there are usually 2) fill up because the delete is really big, then the undo information spills into the actual data blocks, leading to even more I/O.

Deleting in chunks avoids some of this excess overhead.

Limited benchmarking of total delete elapsed time show two observations:

• Total delete time approximately doubles above some 'chunk' size (as opposed to below that threshold). I do not have a formula relating the log file size with the threshold cutoff.

• Chunk size below several hundred rows is slower. This is probably because the overhead of starting/ending each chunk dominates the timing.

Solutions

• PARTITION -- Requires some careful setup, but is excellent for purging a time-base series.

• DELETE in chunks -- Carefully walk through the table N rows at a time.

PARTITION

The idea here is to have a sliding window of partitions. Let's say you need to purge news articles after 30 days. The "partition key" would be the datetime (or timestamp) that is to be used for purging, and the PARTITIONs would be "range". Every night, a cron job would come along and build a new partition for the next day, and drop the oldest partition.

Dropping a partition is essentially instantaneous, much faster than deleting that many rows. However, you must design the table so that the entire partition can be dropped. That is, you cannot have some items living longer than others.

PARTITION tables have a lot of restrictions, some are rather weird. You can either have no UNIQUE (or PRIMARY) key on the table, or every UNIQUE key must include the partition key. In this use case, the partition key is the datetime. It should not be the first part of the PRIMARY KEY (if you have a PRIMARY KEY).

You can PARTITION InnoDB or MyISAM tables.

Since two news articles could have the same timestamp, you cannot assume the partition key is sufficient for uniqueness of the PRIMARY KEY, so you need to find something else to help with that.

Reference implementation for Partition maintenance

MariaDB docs on PARTITION

Deleting in chunks

Although the discussion in this section talks about DELETE, it can be used for any other "chunking", such as, say, UPDATE, or SELECT plus some complex processing.

(This discussion applies to both MyISAM and InnoDB.)

When deleting in chunks, be sure to avoid doing a table scan. The code below is good at that; it scans no more than 1001 rows in any one query. (The 1000 is tunable.)

Assuming you have news articles that need to be purged, and you have a schema something like

CREATE TABLE tbl
      id INT UNSIGNED NOT NULL AUTO_INCREMENT,
      ts TIMESTAMP,
      ...
      PRIMARY KEY(id)

Then, this pseudo-code is a good way to delete the rows older than 30 days:

@a = 0
   LOOP
      DELETE FROM tbl
         WHERE id BETWEEN @a AND @a+999
           AND ts < DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)
      SET @a = @a + 1000
      sleep 1  -- be a nice guy
   UNTIL end of table

Notes (Most of these caveats will be covered later):

• It uses the PK instead of the secondary key. This gives much better locality of disk hits, especially for InnoDB.

• You could (should?) do something to avoid walking through recent days but doing nothing. Caution -- the code for this could be costly.

• The 1000 should be tweaked so that the DELETE usually takes under, say, one second.

• No INDEX on ts is needed. (This helps INSERTs a little.)

• If your PRIMARY KEY is compound, the code gets messier.

• This code will not work without a numeric PRIMARY or UNIQUE key.

• Read on, we'll develop messier code to deal with most of these caveats.

If there are big gaps in id values (and there will after the first purge), then

@a = SELECT MIN(id) FROM tbl
   LOOP
      SELECT @z := id FROM tbl WHERE id >= @a ORDER BY id LIMIT 1000,1
      If @z is null
         exit LOOP  -- last chunk
      DELETE FROM tbl
         WHERE id >= @a
           AND id <  @z
           AND ts < DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)
      SET @a = @z
      sleep 1  -- be a nice guy, especially in replication
   ENDLOOP
   # Last chunk:
   DELETE FROM tbl
      WHERE id >= @a
        AND ts < DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)

That code works whether id is numeric or character, and it mostly works even if id is not UNIQUE. With a non-unique key, the risk is that you could be caught in a loop whenever @z==@a. That can be detected and fixed thus:

...
      SELECT @z := id FROM tbl WHERE id >= @a ORDER BY id LIMIT 1000,1
      If @z == @a
         SELECT @z := id FROM tbl WHERE id > @a ORDER BY id LIMIT 1
   ...

The drawback is that there could be more than 1000 items with a single id. In most practical cases, that is unlikely.

If you do not have a primary (or unique) key defined on the table, and you have an INDEX on ts, then consider

LOOP
      DELETE FROM tbl
         WHERE ts < DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)
         ORDER BY ts   -- to use the index, and to make it deterministic
         LIMIT 1000
   UNTIL no rows deleted

This technique is NOT recommended because the LIMIT leads to a warning on replication about it being non-deterministic (discussed below).

InnoDB chunking recommendation

• Have a 'reasonable' size for innodb_log_file_size.

• Use AUTOCOMMIT=1 for the session doing the deletions.

• Pick about 1000 rows for the chunk size.

• Adjust the row count down if asynchronous replication (Statement Based) causes too much delay on the Slaves or hogs the table too much.

Iterating through a compound key

To perform the chunked deletes recommended above, you need a way to walk through the PRIMARY KEY. This can be difficult if the PK has more than one column in it.

To efficiently to do compound 'greater than':

Assume that you left off at ($g, $s) (and have handled that row):

INDEX(Genus, species)
   SELECT/DELETE ...
      WHERE Genus >= '$g' AND ( species  > '$s' OR Genus > '$g' )
      ORDER BY Genus, species
      LIMIT ...

Addenda: The above AND/OR works well in older versions of MySQL; this works better in MariaDB and newer versions of MySQL:

WHERE ( Genus = '$g' AND species  > '$s' ) OR Genus > '$g' )

A caution about using @variables for strings. If, instead of '$g', you use @g, you need to be careful to make sure that @g has the same CHARACTER SET and COLLATION as Genus, else there could be a charset/collation conversion on the fly that prevents the use of the INDEX. Using the INDEX is vital for performance. It may require a COLLATE clause on SET NAMES and/or the @g in the SELECT.

Reclaiming the disk space

This is costly. (Switch to the PARTITION solution if practical.)

MyISAM leaves gaps in the table (.MYD file); OPTIMIZE TABLE will reclaim the freed space after a big delete. But it may take a long time and lock the table.

InnoDB is block-structured, organized in a BTree on the PRIMARY KEY. An isolated deleted row leaves a block less full. A lot of deleted rows can lead to coalescing of adjacent blocks. (Blocks are normally 16KB - see innodb_page_size.)

In InnoDB, there is no practical way to reclaim the freed space from ibdata1, other than to reuse the freed blocks eventually.

The only option with innodb_file_per_table = 0 is to dump ALL tables, remove ibdata*, restart, and reload. That is rarely worth the effort and time.

InnoDB, even with innodb_file_per_table = 1, won't give space back to the OS, but at least it is only one table to rebuild with. In this case, something like this should work:

CREATE TABLE new LIKE main;
   INSERT INTO new SELECT * FROM main;  -- This could take a long time
   RENAME TABLE main TO old, new TO main;   -- Atomic swap
   DROP TABLE old;   -- Space freed up here

You do need enough disk space for both copies. You must not write to the table during the process.

Deleting more than half a table

The following technique can be used for any combination of

• Deleting a large portion of the table more efficiently

• Add PARTITIONing

• Converting to innodb_file_per_table = ON

• Defragmenting

This can be done by chunking, or (if practical) all at once:

-- Optional:  SET GLOBAL innodb_file_per_table = ON;
   CREATE TABLE New LIKE Main;
   -- Optional:  ALTER TABLE New ADD PARTITION BY RANGE ...;
   -- Do this INSERT..SELECT all at once, or with chunking:
   INSERT INTO New
      SELECT * FROM Main
         WHERE ...;  -- just the rows you want to keep
   RENAME TABLE main TO Old, New TO Main;
   DROP TABLE Old;   -- Space freed up here

Notes:

• You do need enough disk space for both copies.

• You must not write to the table during the process. (Changes to Main may not be reflected in New.)

Non-deterministic replication

Any UPDATE, DELETE, etc with LIMIT that is replicated to slaves (via Statement Based Replication) may cause inconsistencies between the Master and Slaves. This is because the actual order of the records discovered for updating/deleting may be different on the slave, thereby leading to a different subset being modified. To be safe, add ORDER BY to such statements. Moreover, be sure the ORDER BY is deterministic -- that is, the fields/expressions in the ORDER BY are unique.

An example of an ORDER BY that does not quite work: Assume there are multiple rows for each 'date':

DELETE * FROM tbl ORDER BY date LIMIT 111

Given that id is the PRIMARY KEY (or UNIQUE), this will be safe:

DELETE * FROM tbl ORDER BY date, id LIMIT 111

Unfortunately, even with the ORDER BY, MySQL has a deficiency that leads to a bogus warning in mysqld.err. See Spurious "Statement is not safe to log in statement format." warnings

Some of the above code avoids this spurious warning by doing

SELECT @z := ... LIMIT 1000,1;  -- not replicated
   DELETE ... BETWEEN @a AND @z;   -- deterministic

That pair of statements guarantees no more than 1000 rows are touched, not the whole table.

Replication and KILL

If you KILL a DELETE (or any? query) on the master in the middle of its execution, what will be replicated?

If it is InnoDB, the query should be rolled back. (Exceptions??)

In MyISAM, rows are DELETEd as the statement is executed, and there is no provision for ROLLBACK. Some of the rows will be deleted, some won't. You probably have no clue of how much was deleted. In a single server, simply run the delete again. The delete is put into the binlog, but with error 1317. Since replication is supposed to keep the master and slave in sync, and since it has no clue of how to do that, replication stops and waits for manual intervention. In a HA (High Available) system using replication, this is a minor disaster. Meanwhile, you need to go to each slave(s) and verify that it is stuck for this reason, then do

SET GLOBAL SQL_SLAVE_SKIP_COUNTER = 1;
   START SLAVE;

Then (presumably) re-executing the DELETE will finish the aborted task.

(That is yet another reason to move all your tables from MyISAM to InnoDB.)

SBR vs RBR; Galera

TBD -- "Row Based Replication" may impact this discussion.

Postlog

The tips in this document apply to MySQL, MariaDB, and Percona.

See also

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: deletebig

_{This page is licensed: CC BY-SA / Gnu FDL}

The Charset Narrowing optimization handles equality comparisons like:

utf8mb3_key_column=utf8mb4_expression

It enables the optimizer to construct ref access to utf8mb3_key_column based on this equality. The optimization supports comparisons of columns that use utf8mb3_general_ci to expressions that use utf8mb4_general_ci .

The optimization was introduced in MariaDB 10.6.16, MariaDB 10.10.7, MariaDB 10.11.6, MariaDB 11.0.4, MariaDB 11.1.3 and MariaDB 11.2.2, where it is OFF by default. From MariaDB 11.7, it is ON by default.

Description

MariaDB supports both the UTF8MB3 and UTF8MB4 character sets. It is possible to construct join queries that compare values in UTF8MB3 to UTF8MB4.

Suppose, we have the table 'users that uses UTF8MB4:

CREATE TABLE users (
  user_name_mb4 VARCHAR(100) COLLATE utf8mb4_general_ci,
  ...
);

and table orders that uses UTF8MB3:

CREATE TABLE orders (
  user_name_mb3 VARCHAR(100) COLLATE utf8mb3_general_ci,
  ...,
  INDEX idx1(user_name_mb3)
);

One can join users to orders on user_name:

SELECT * FROM orders, users WHERE orders.user_name_mb3=users.user_name_mb4;

Internally the optimizer will handle the equality by converting the UTF8MB3 value into UTF8MB4 and then doing the comparison. One can see the call to CONVERT in EXPLAIN FORMAT=JSON output or Optimizer Trace:

CONVERT(orders.user_name_mb3 USING utf8mb4) = users.user_name_mb4

This produces the expected result but the query optimizer is not able to use the index over orders.user_name_mb3 to find matches for values of users.user_name_mb4.

The EXPLAIN of the above query looks like this:

EXPLAIN SELECT * FROM orders, users WHERE orders.user_name_mb3=users.user_name_mb4;
+------+-------------+--------+------+---------------+------+---------+------+-------+-------------------------------------------------+
| id   | select_type | table  | type | possible_keys | key  | key_len | ref  | rows  | Extra                                           |
+------+-------------+--------+------+---------------+------+---------+------+-------+-------------------------------------------------+
|    1 | SIMPLE      | users  | ALL  | NULL          | NULL | NULL    | NULL | 1000  |                                                 |
|    1 | SIMPLE      | orders | ALL  | NULL          | NULL | NULL    | NULL | 10330 | Using where; Using join buffer (flat, BNL join) |
+------+-------------+--------+------+---------------+------+---------+------+-------+-------------------------------------------------+

The Charset Narrowing optimization enables the optimizer to perform the comparison between UTF8MB3 and UTF8MB4 values by "narrowing" the value in UTF8MB4 to UTF8MB3. The CONVERT call is no longer needed, and the optimizer is able to use the equality to construct ref access:

SET optimizer_switch='cset_narrowing=ON';

EXPLAIN SELECT * FROM orders, users WHERE orders.user_name_mb3=users.user_name_mb4;
+------+-------------+--------+------+---------------+------+---------+---------------------+------+-----------------------+
| id   | select_type | table  | type | possible_keys | key  | key_len | ref                 | rows | Extra                 |
+------+-------------+--------+------+---------------+------+---------+---------------------+------+-----------------------+
|    1 | SIMPLE      | users  | ALL  | NULL          | NULL | NULL    | NULL                | 1000 | Using where           |
|    1 | SIMPLE      | orders | ref  | idx1          | idx1 | 303     | users.user_name_mb4 | 1    | Using index condition |
+------+-------------+--------+------+---------------+------+---------+---------------------+------+-----------------------+

Controlling the Optimization

The optimization is controlled by an optimizer_switch flag. Specify:

SET optimizer_switch='cset_narrowing=ON';

to enable the optimization.

References

• MDEV-32113: utf8mb3_key_col=utf8mb4_value cannot be used for ref access

• Blog post: Making “tbl.utf8mb3_key_column=utf8mb4_expr” sargable

_{This page is licensed: CC BY-SA / Gnu FDL}

Fetching random rows from a table (beyond ORDER BY RAND())

The problem

One would like to do "SELECT ... ORDER BY RAND() LIMIT 10" to get 10 rows at random. But this is slow. The optimizer does

• Fetch all the rows -- this is costly

• Append RAND() to the rows

• Sort the rows -- also costly

• Pick the first 10.

All the algorithms given below are "fast", but most introduce flaws:

• Bias -- some rows are more like to be fetched than others.

• Repetitions -- If two random sets contain the same row, they are likely to contain other dups.

• Sometimes failing to fetch the desired number of rows.

"Fast" means avoiding reading all the rows. There are many techniques that require a full table scan, or at least an index scan. They are not acceptable for this list. There is even a technique that averages half a scan; it is relegated to a footnote.

Metrics

Here's a way to measure performance without having a big table.

FLUSH STATUS;
    SELECT ...;
    SHOW SESSION STATUS LIKE 'Handler%';

If some of the "Handler" numbers look like the number of rows in the table, then there was a table scan.

None of the queries presented here need a full table (or index) scan. Each has a time proportional to the number of rows returned.

Virtually all published algorithms involve a table scan. The previously published version of this blog had, embarrassingly, several algorithms that had table scans.

Sometimes the scan can be avoided via a subquery. For example, the first of these will do a table scan; the second will not.

SELECT *  FROM RandTest AS a
  WHERE id = FLOOR(@min + (@max - @min + 1) * RAND());  -- BAD: table scan
SELECT *
 FROM RandTest AS a
 JOIN (
   SELECT FLOOR(@min + (@max - @min + 1) * RAND()) AS id -- Good; single eval.
      ) b  USING (id);

Case: Consecutive AUTO_INCREMENT without gaps, 1 row returned

• Requirement: AUTO_INCREMENT id

• Requirement: No gaps in id

SELECT r.*
      FROM (
          SELECT FLOOR(mm.min_id + (mm.max_id - mm.min_id + 1) * RAND()) AS id
              FROM (
                  SELECT MIN(id) AS min_id,
                         MAX(id) AS max_id
                      FROM RandTest
                   ) AS mm
           ) AS init
      JOIN  RandTest AS r  ON r.id = init.id;

(Of course, you might be able to simplify this. For example, min_id is likely to be 1. Or precalculate limits into @min and @max.)

Case: Consecutive AUTO_INCREMENT without gaps, 10 rows

• Requirement: AUTO_INCREMENT id

• Requirement: No gaps in id

• Flaw: Sometimes delivers fewer than 10 rows

-- First select is one-time:
  SELECT @min := MIN(id),
         @max := MAX(id)
      FROM RandTest;
  SELECT DISTINCT *
      FROM RandTest AS a
      JOIN (
          SELECT FLOOR(@min + (@max - @min + 1) * RAND()) AS id
              FROM RandTest
              LIMIT 11    -- more than 10 (to compensate for dups)
           ) b  USING (id)
      LIMIT 10;           -- the desired number of rows

The FLOOR expression could lead to duplicates, hence the inflated inner LIMIT. There could (rarely) be so many duplicates that the inflated LIMIT leads to fewer than the desired 10 different rows. One approach to that Flaw is to rerun the query if it delivers too few rows.

A variant:

SELECT r.*
      FROM (
          SELECT FLOOR(mm.min_id + (mm.max_id - mm.min_id + 1) * RAND()) AS id
              FROM (
                  SELECT MIN(id) AS min_id,
                         MAX(id) AS max_id
                      FROM RandTest
                   ) AS mm
              JOIN ( SELECT id dummy FROM RandTest LIMIT 11 ) z
           ) AS init
      JOIN  RandTest AS r  ON r.id = init.id
      LIMIT 10;

Again, ugly but fast, regardless of table size.

Case: AUTO_INCREMENT with gaps, 1 or more rows returned

• Requirement: AUTO_INCREMENT, possibly with gaps due to DELETEs, etc

• Flaw: Only semi-random (rows do not have an equal chance of being picked), but it does partially compensate for the gaps

• Flaw: The first and last few rows of the table are less likely to be delivered.

This gets 50 "consecutive" ids (possibly with gaps), then delivers a random 10 of them.

-- First select is one-time:
SELECT @min := MIN(id),
       @max := MAX(id)
    FROM RandTest;
SELECT a.*
    FROM RandTest a
    JOIN ( SELECT id FROM
            ( SELECT id
                FROM ( SELECT @min + (@max - @min + 1 - 50) * RAND() 
                  AS start FROM DUAL ) AS init
                JOIN RandTest y
                WHERE    y.id > init.start
                ORDER BY y.id
                LIMIT 50         -- Inflated to deal with gaps
            ) z ORDER BY RAND()
           LIMIT 10              -- number of rows desired (change to 1 if looking for a single row)
         ) r ON a.id = r.id;

Yes, it is complex, but yes, it is fast, regardless of the table size.

Case: Extra FLOAT column for randomizing

(Unfinished: need to check these.)

Assuming rnd is a FLOAT (or DOUBLE) populated with RAND() and INDEXed:

• Requirement: extra, indexed, FLOAT column

• Flaw: Fetches 10 adjacent rows (according to rnd), hence not good randomness

• Flaw: Near 'end' of table, can't find 10 rows.

SELECT r.*
      FROM ( SELECT RAND() AS start FROM DUAL ) init
      JOIN RandTest r
      WHERE r.rnd >= init.start
      ORDER BY r.rnd
      LIMIT 10;

• These two variants attempt to resolve the end-of-table flaw:

SELECT r.*
      FROM ( SELECT RAND() * ( SELECT rnd
                        FROM RandTest
                        ORDER BY rnd DESC
                        LIMIT 10,1 ) AS start
           ) AS init
      JOIN RandTest r
      WHERE r.rnd > init.start
      ORDER BY r.rnd
      LIMIT 10;


  SELECT @start := RAND(),
         @cutoff := CAST(1.1 * 10 + 5 AS DECIMAL(20,8)) / TABLE_ROWS
      FROM information_schema.TABLES
      WHERE TABLE_SCHEMA = 'dbname'
        AND TABLE_NAME = 'RandTest'; -- 0.0030
  SELECT d.*
      FROM (
          SELECT a.id
              FROM RandTest a
              WHERE rnd BETWEEN @start AND @start + @cutoff
           ) sample
      JOIN RandTest d USING (id)
      ORDER BY rand()
      LIMIT 10;

Case: UUID or MD5 column

• Requirement: UUID/GUID/MD5/SHA1 column exists and is indexed.

• Similar code/benefits/flaws to AUTO_INCREMENT with gaps.

• Needs 7 random HEX digits:

RIGHT( HEX( (1<<24) * (1+RAND()) ), 6)

can be used as a start for adapting a gapped AUTO_INCREMENT case. If the field is BINARY instead of hex, then

UNHEX(RIGHT( HEX( (1<<24) * (1+RAND()) ), 6))

See also

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: random

_{This page is licensed: CC BY-SA / Gnu FDL}

The problem

You are ingesting lots of data. Performance is bottlenecked in the INSERT area.

This will be couched in terms of Data Warehousing, with a huge Fact table and Summary (aggregation) tables.

Overview of solution

• Have a separate staging table.

• Inserts go into Staging.

• Normalization and Summarization reads Staging, not Fact.

• After normalizing, the data is copied from Staging to Fact.

Staging is one (or more) tables in which the data lives only long enough to be handed off to Normalization, Summary, and the Fact tables.

Since we are probably talking about a billion-row table, shrinking the width of the Fact table by normalizing (as mentioned here). Changing an INT to a MEDIUMINT will save a GB. Replacing a string by an id (normalizing) saves many GB. This helps disk space and cacheability, hence speed.

Injection speed

Some variations:

• Big dump of data once an hour, versus continual stream of records.

• The input stream could be single-threaded or multi-threaded.

• You might have 3rd party software tying your hands.

Generally the fastest injection rate can be achieved by "staging" the INSERTs in some way, then batch processing the staged records. This blog discusses various techniques for staging and batch processing.

Normalization

Let's say your Input has a VARCHAR host_name column, but you need to turn that into a smaller MEDIUMINT host_id in the Fact table. The "Normalization" table, as I call it, looks something like

CREATE TABLE Hosts (
    host_id  MEDIUMINT UNSIGNED  NOT NULL AUTO_INCREMENT,
    host_name VARCHAR(99) NOT NULL,
    PRIMARY KEY (host_id),      -- for mapping one direction
    INDEX(host_name, host_id)   -- for mapping the other direction
) ENGINE=InnoDB;                -- InnoDB works best for Many:Many mapping table

Here's how you can use Staging as an efficient way achieve the swap from name to id.

Staging has two fields (for this normalization example):

host_name VARCHAR(99) NOT NULL,     -- Comes from the insertion proces
    host_id  MEDIUMINT UNSIGNED  NULL,  -- NULL to start with; see code below

Meawhile, the Fact table has:

host_id  MEDIUMINT UNSIGNED NOT NULL,

SQL #1 (of 2):

# This should not be in the main transaction, and it should be done with autocommit = ON
    # In fact, it could lead to strange errors if this were part
    #    of the main transaction and it ROLLBACKed.
    INSERT IGNORE INTO Hosts (host_name)
        SELECT DISTINCT s.host_name
            FROM Staging AS s
            LEFT JOIN Hosts AS n  ON n.host_name = s.host_name
            WHERE n.host_id IS NULL;

By isolating this as its own transaction, we get it finished in a hurry, thereby minimizing blocking. By saying IGNORE, we don't care if other threads are 'simultaneously' inserting the same host_names.

There is a subtle reason for the LEFT JOIN. If, instead, it were INSERT IGNORE..SELECT DISTINCT, then the INSERT would preallocate auto_increment ids for as many rows as the SELECT provides. This is very likely to "burn" a lot of ids, thereby leading to overflowing MEDIUMINT unnecessarily. The LEFT JOIN leads to finding just the new ids that are needed (except for the rare possibility of a 'simultaneous' insert by another thread). More rationale: Mapping table

SQL #2:

# Also not in the main transaction, and it should be with autocommit = ON
    # This multi-table UPDATE sets the ids in Staging:
    UPDATE   Hosts AS n
        JOIN Staging AS s  ON s.host_name = n host_name
        SET s.host_id = n.host_id

This gets the IDs, whether already existing, set by another thread, or set by SQL #1.

If the size of Staging changes depending on the busy versus idle times of the day, this pair of SQL statements has another comforting feature. The more rows in Staging, the more efficient the SQL runs, thereby helping compensate for the "busy" times.

The companion Data Warehouse article folds SQL #2 into the INSERT INTO Fact. But you may need host_id for further normalization steps and/or Summarization steps, so this explicit UPDATE shown here is often better.

Flip-flop staging

The simple way to stage is to ingest for a while, then batch-process what is in Staging. But that leads to new records piling up waiting to be staged. To avoid that issue, have 2 processes:

• one process (or set of processes) for INSERTing into Staging;

• one process (or set of processes) to do the batch processing (normalization, summarization).

To keep the processes from stepping on each other, we have a pair of staging tables:

• Staging is being INSERTed into;

• StageProcess is one being processed for normalization, summarization, and moving to the Fact table. A separate process does the processing, then swaps the tables:

DROP   TABLE StageProcess;
    CREATE TABLE StageProcess LIKE Staging;
    RENAME TABLE Staging TO tmp, StageProcess TO Staging, tmp TO StageProcess;

This may not seem like the shortest way to do it, but has these features:

• The DROP + CREATE might be faster than TRUNCATE, which is the desired effect.

• The RENAME is atomic, so the INSERT process(es) never find that Staging is missing.

A variant on the 2-table flip-flop is to have a separate Staging table for each Insertion process. The Processing process would run around to each Staging in turn.

A variant on that would be to have a separate processing process for each Insertion process.

The choice depends on which is faster (insertion or processing). There are tradeoffs; a single processing thread avoids some locks, but lacks some parallelism.

Engine choice

Fact table -- InnoDB, if for no other reason than that a system crash would not need a REPAIR TABLE. (REPAIRing a billion-row MyISAM table can take hours or days.)

Normalization tables -- InnoDB, primarily because it can be done efficiently with 2 indexes, whereas, MyISAM would need 4 to achieve the same efficiency.

Staging -- Lots of options here.

• If you have multiple Inserters and a single Staging table, InnoDB is desirable due to row-level, not table-level, locking.

• MEMORY may be the fastest and it avoids I/O. This is good for a single staging table.

• For multiple Inserters, a separate Staging table for each Inserter is desired.

• For multiple Inserters into a single Staging table, InnoDB may be faster. (MEMORY does table-level locking.)

• With one non-InnoDB Staging table per Inserter, using an explicit LOCK TABLE avoids repeated implicit locks on each INSERT.

• But, if you are doing LOCK TABLE and the Processing thread is separate, an UNLOCK is necessary periodically to let the RENAME grab the table.

• "Batch INSERTs" (100-1000 rows per SQL) eliminates much of the issues of the above bullet items.

Confused? Lost? There are enough variations in applications that make it impractical to predict what is best. Or, simply good enough. Your ingestion rate may be low enough that you don't hit the brick walls that I am helping you avoid.

Should you do "CREATE TEMPORARY TABLE"? Probably not. Consider Staging as part of the data flow, not to be DROPped.

Summarization

This is mostly covered here: Summary Tables Summarize from the Staging table instead of the Fact table.

Replication Issues

Row Based Replication (RBR) is probably the best option.

The following allows you to keep more of the Ingestion process in the Master, thereby not bogging down the Slave(s) with writes to the Staging table.

• RBR

• Staging is in a separate database

• That database is not replicated (binlog-ignore-db on Master)

• In the Processing steps, USE that database, reach into the main db via syntax like "MainDb.Hosts". (Otherwise, the binlog-ignore-db does the wrong thing.)

That way

• Writes to Staging are not replicated.

• Normalization sends only the few updates to the normalization tables.

• Summarization sends only the updates to the summary tables.

• Flip-flop does not replicate the DROP, CREATE or RENAME.

Sharding

You could possibly spread the data you are trying ingest across multiple machines in a predictable way (sharding on hash, range, etc). Running "reports" on a sharded Fact table is a challenge unto itself. On the other hand, Summary Tables rarely get too big to manage on a single machine.

For now, Sharding is beyond the scope of this blog.

Push me vs pull me

I have implicitly assumed the data is being pushed into the database. If, instead, you are "pulling" data from some source(s), then there are some different considerations.

Case 1: An hourly upload; run via cron

1. Grab the upload, parse it

2. Put it into the Staging table

3. Normalize -- each SQL in its own transaction (autocommit)

4. BEGIN

5. Summarize

6. Copy from Staging to Fact.

7. COMMIT

If you need parallelism in Summarization, you will have to sacrifice the transactional integrity of steps 4-7.

Caution: If these steps add up to more than an hour, you are in deep dodo.

Case 2: You are polling for the data

It is probably reasonable to have multiple processes doing this, so it will be detailed about locking.

1. Create a Staging table for this polling processor. Loop:

2. With some locked mechanism, decide which 'thing' to poll.

3. Poll for the data, pull it in, parse it. (Potentially polling and parsing are significantly costly)

4. Put it into the process-specific Staging table

5. Normalize -- each SQL in its own transaction (autocommit)

6. BEGIN

7. Summarize

8. Copy from Staging to Fact.

9. COMMIT

10. Declare that you are finished with this 'thing' (see step 1) EndLoop.

iblog_file_size should be larger than the change in the STATUS "Innodb_os_log_written" across the BEGIN...COMMIT transaction (for either Case).

See also

• companion Data Warehouse blog

• companion Summary Table blog

• a forum thread that prodded me into writing this blog

• StackExchange discussion

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: staging_table

_{This page is licensed: CC BY-SA / Gnu FDL}

Preface

This document discusses the creation and maintenance of "Summary Tables". It is a companion to the document on Data Warehousing Techniques.

The basic terminology ("Fact Table", "Normalization", etc) is covered in that document.

Summary tables for data warehouse "reports"

Summary tables are a performance necessity for large tables. MariaDB and MySQL do not provide any automated way to create such, so I am providing techniques here.

(Other vendors provide something similar with "materialized views".)

When you have millions or billions of rows, it takes a long time to summarize the data to present counts, totals, averages, etc, in a size that is readily digestible by humans. By computing and saving subtotals as the data comes in, one can make "reports" run much faster. (I have seen 10x to 1000x speedups.) The subtotals go into a "summary table". This document guides you on efficiency in both creating and using such tables.

General structure of a summary table

A summary table includes two sets of columns:

• Main KEY: date + some dimension(s)

• Subtotals: COUNT(*), SUM(...), ...; but not AVG()

The "date" might be a DATE (a 3-byte native datatype), or an hour, or some other time interval. A 3-byte MEDIUMINT UNSIGNED 'hour' can be derived from a DATETIME or TIMESTAMP via

FLOOR(UNIX_TIMESTAMP(dt) / 3600)
   FROM_UNIXTIME(hour * 3600)

The "dimensions" (a DW term) are some of the columns of the "Fact" table. Examples: Country, Make, Product, Category, Host Non-dimension examples: Sales, Quantity, TimeSpent

There would be one or more indexes, usually starting with some dimensions and ending with the date field. By ending with the date, one can efficiently get a range of days/weeks/etc. even when each row summarizes only one day.

There will typically be a "few" summary tables. Often one summary table can serve multiple purposes sufficiently efficiently.

As a rule of thumb, a summary table will have one-tenth the number of rows as the Fact table. (This number is very loose.)

Example

Let's talk about a large chain of car dealerships. The Fact table has all the sales with columns such as datetime, salesman_id, city, price, customer_id, make, model, model_year. One Summary table might focus on sales:

PRIMARY KEY(city, datetime),
   Aggregations: ct, sum_price
   
   # Core of INSERT..SELECT:
   DATE(datetime) AS DATE, city, COUNT(*) AS ct, SUM(price) AS sum_price
   
   # Reporting average price FOR last month, broken down BY city:
   SELECT city,
          SUM(sum_price) / SUM(ct) AS 'AveragePrice'
      FROM SalesSummary
      WHERE datetime BETWEEN ...
      GROUP BY city;
   
   # Monthly sales, nationwide, FROM same summary TABLE:
   SELECT MONTH(datetime) AS 'Month',
          SUM(ct)         AS 'TotalSalesCount'
          SUM(sum_price)  AS 'TotalDollars'
      FROM SalesSummary
      WHERE datetime BETWEEN ...
      GROUP BY MONTH(datetime);
   # This might benefit FROM a secondary INDEX(datetime)

When to augment the summary table(s)?

"Augment" in this section means to add new rows into the summary table or increment the counts in existing rows.

Plan A: "While inserting" rows into the Fact table, augment the summary table(s). This is simple, and workable for a smaller DW database (under 10 Fact table rows per second). For larger DW databases, Plan A likely to be too costly to be practical.

Plan B: "Periodically", via cron or an EVENT.

Plan C: "As needed". That is, when someone asks for a report, the code first updates the summary tables that will be needed.

Plan D: "Hybrid" of B and C. C, by itself, can led to long delays for the report. By also doing B, those delays can be kept low.

Plan E: (This is not advised.) "Rebuild" the entire summary table from the entire Fact table. The cost of this is prohibitive for large tables. However, Plan E may be needed when you decide to change the columns of a Summary Table, or discover a flaw in the computations. To lessen the impact of an entire build, adapt the chunking techniques in Deleting in chunks .

Plan F: "Staging table". This is primarily for very high speed ingestion. It is mentioned briefly in this blog, and discussed more thoroughly in the companion blog: High Speed Ingestion

Summarizing while Inserting (one row at a time)

INSERT INTO Fact ...;
    INSERT INTO Summary (..., ct, foo, ...) VALUES (..., 1, foo, ...)
        ON DUPLICATE KEY UPDATE ct = ct+1, sum_foo = sum_foo + VALUES(foo), ...;

IODKU (Insert On Duplicate Key Update) will update an existing row or create a new row. It knows which to do based on the Summary table's PRIMARY KEY.

Caution: This approach is costly, and will not scale to an ingestion rate of over, say, 10 rows per second (Or maybe 50/second on SSDs). More discussion later.

Summarizing periodically vs as-needed

If your reports need to be up-to-the-second, you need "as needed" or "hybrid". If your reports have less urgency (eg, weekly reports that don't include 'today'), then "periodically" might be best.

For a daily summaries, augmenting the summary tables could be done right after midnight. But, beware of data coming "late".

For both "periodic" and "as needed", you need a definitive way of keeping track of where you "left off".

Case 1: You insert into the Fact table first and it has an AUTO_INCREMENT id: Grab MAX(id) as the upper bound for summarizing and put it either into some other secure place (an extra table), or put it into the row(s) in the Summary table as you insert them. (Caveat: AUTO_INCREMENT ids do not work well in multi-master, including Galera, setups.)

Case 2: If you are using a 'staging' table, there is no issue. (More on staging tables later.)

Summarizing while batch inserting

This applies to multi-row (batch) INSERT and LOAD DATA.

The Fact table needs an AUTO_INCREMENT id, and you need to be able to find the exact range of ids inserted. (This may be impractical in any multi-master setup.)

Then perform bulk summarization using

FROM Fact
   WHERE id BETWEEN min_id AND max_id

Summarizing when using a staging table

Load the data (via INSERTs or [LOAD DATA) en masse into a "staging table". Then perform batch summarization from the Staging table. And batch copy from the Staging table to the Fact table. Note that the Staging table is handy for batching "normalization" during ingestion. See also [data-warehousing-high-speed-ingestion|High Speed Ingestion

Summary table: PK or not?

Let's say your summary table has a DATE, dy, and a dimension, foo. The question is: Should (foo, dy) be the PRIMARY KEY? Or a non-UNIQUE index?

Case 1: PRIMARY KEY (foo, dy) and summarization is in lock step with, say, changes in dy.

This case is clean and simple -- until you get to endcases. How will you handle the case of data arriving 'late'? Maybe you will need to recalculate some chunks of data? If so, how?

Case 2: (foo, dy) is a non-UNIQUE INDEX.

This case is clean and simple, but it can clutter the summary table because multiple rows can occur for a given (foo, dy) pair. The report will always have to SUM() up values because it cannot assume there is only one row, even when it is reporting on a single foo for a single dy. This forced-SUM is not really bad -- you should do it anyway; that way all your reports are written with one pattern.

Case 3: PRIMARY KEY (foo, dy) and summarization can happen anytime.

Since you should be using InnoDB, there needs to be an explicit PRIMARY KEY. One approach when you do not have a 'natural' PK is this:

id INT UNSIGNED AUTO_INCREMENT NOT NULL,
   ...
   PRIMARY KEY(foo, dy, id),  -- `id` added to make unique
   INDEX(id)                  -- sufficient to keep AUTO_INCREMENT happy

This case pushes the complexity onto the summarization by doing a IODKU.

Advice? Avoid Case 1; too messy. Case 2 is ok if the extra rows are not too common. Case 3 may be the closest to "once size fits all".

Averages, etc.

When summarizing, include COUNT(*) AS ct and SUM(foo) AS sum_foo. When reporting, the "average" is computed as SUM(sum_foo) / SUM(ct). That is mathematically correct.

Exception... Let's say you are looking at weather temperatures. And you monitoring station gets the temp periodically, but unreliably. That is, the number of readings for a day varies. Further, you decide that the easiest way to compensate for the inconsistency is to do something like: Compute the avg temp for each day, then average those across the month (or other timeframe).

Formula for Standard Deviation:

SQRT( SUM(sum_foo2)/SUM(ct) - POWER(SUM(sum_foo)/SUM(ct), 2) )

Where sum_foo2 is SUM(foo * foo) from the summary table. sum_foo and sum_foo2 should be FLOAT. FLOAT gives you about 7 significant digits, which is more than enough for things like average and standard deviation. FLOAT occupies 4 bytes. DOUBLE would give you more precision, but occupies 8 bytes. INT and BIGINT are not practical because they may lead to complaints about overflow.

Staging table

The idea here is to first load a set of Fact records into a "staging table", with the following characteristics (at least):

• The table is repeatedly populated and truncated

• Inserts could be individual or batched, and from one or many clients

• SELECTs will be table scans, so no indexes needed

• Inserting will be fast (InnoDB may be the fastest)

• Normalization can be done in bulk, hence efficiently

• Copying to the Fact table will be fast

• Summarization can be done in bulk, hence efficiently

• "Bursty" ingestion is smoothed by this process

• Flip-flop a pair of Staging tables

If you have bulk inserts (Batch INSERT or LOAD DATA) then consider doing the normalization and summarization immediately after each bulk insert.

More details: High Speed Ingestion

Extreme design

Here is a more complex way to design the system, with the goal of even more scaling.

• Use master-slave setup: ingest into master; report from slave(s).

• Feed ingestion through a staging table (as described above)

• Single-source of data: ENGINE=MEMORY; multiple sources: InnoDB

• binlog_format = ROW

• Use binlog_ignore_db to avoid replicating staging -- necessitating putting it in a separate database.

• Do the summarization from Staging

• Load Fact via INSERT INTO Fact ... SELECT FROM Staging ...

Explanation and comments:

• ROW + ignore_db avoids replicating Staging, yet replicates the INSERTs based on it. Hence, it lightens the write load on the Slaves

• If using MEMORY, remember that it is volatile -- recover from a crash by starting the ingestion over.

• To aid with debugging, TRUNCATE or re-CREATE Staging at the start of the next cycle.

• Staging needs no indexes -- all operations read all rows from it.

Stats on the system that this 'extreme design' came from: Fact Table: 450GB, 100M rows/day (batch of 4M/hour), 60 day retention (60+24 partitions), 75B/row, 7 summary tables, under 10 minutes to ingest and summarize the hourly batch. The INSERT..SELECT handled over 20K rows/sec going into the Fact table. Spinning drives (not SSD) with RAID-10.

"Left Off"

One technique involves summarizing some of the data, then recording where you "left off", so that next time, you can start there. There are some subtle issues with "left off" that you should be cautious of.

If you use a DATETIME or TIMESTAMP as "left off", beware of multiple rows with the same value.

• Plan A: Use a compound "left off" (eg, TIMESTAMP + ID). This is messy, error prone, etc.

• Plan B: WHERE ts >= $left_off AND ts < $max_ts -- avoids dups, but has other problems (below)

• Separate threads could COMMIT TIMESTAMPs out of order.

If you use an AUTO_INCREMENT as "left off" beware of:

• In InnoDB, separate threads could COMMIT ids in the 'wrong' order.

• Multi-master (including Galera and InnoDB Cluster), could lead to ordering issues.

So, nothing works, at least not in a multi-threaded environment?

If you can live with an occasional hiccup (skipped record), then maybe this is 'not a problem' for you.

The "Flip-Flop Staging" is a safe alternative, optionally combined with the "Extreme Design".

Flip-flop staging

If you have many threads simultaneously INSERTing into one staging table, then here is an efficient way to handle a large load: Have a process that flips that staging table with another, identical, staging table, and performs bulk normalization, Fact insertion, and bulk summarization.

The flipping step uses a fast, atomic, RENAME.

Here is a sketch of the code:

# Prep FOR flip:
    CREATE TABLE new LIKE Staging;

    # Swap (flip) Staging tables:
    RENAME TABLE Staging TO old, new TO Staging;

    # Normalize new `foo`s:
    # (autocommit = 1)
    INSERT IGNORE INTO Foos SELECT fpp FROM old LEFT JOIN Foos ...

    # Prep FOR possible deadlocks, etc
    WHILE...
    START TRANSACTION;

    # ADD TO Fact:
    INSERT INTO Fact ... FROM old JOIN Foos ...

    # Summarize:
    INSERT INTO Summary ... FROM old ... GROUP BY ...

    COMMIT;
    end-WHILE

    # Cleanup:
    DROP TABLE old;

Meanwhile, ingestion can continue writing to Staging. The ingestion INSERTs will conflict with the RENAME, but will be resolved gracefully and silently and quickly.

How fast should you flip-flop? Probably the best scheme is to

• Have a job that flip-flops in a tight loop (no delay, or a small delay, between iterations), and

• Have a CRON that serves only as a "keep-alive" to restart the job if it dies.

If Staging is 'big', an iteration will take longer, but run more efficiently. Hence, it is self-regulating.

In a Galera (or InnoDB Cluster?) environment, each node could be receiving input. If can afford to loose a few rows, have Staging be a non-replicated MEMORY table. Otherwise, have one Staging per node and be InnoDB; it will be more secure, but slower and not without problems. In particular, if a node dies completely, you somehow need to process its Staging table.

Multiple summary tables

• Look at the reports you will need.

• Design a summary table for each.

• Then look at the summary tables -- you are likely to find some similarities.

• Merge similar ones.

To look at what a report needs, look at the WHERE clause that would provide the data. Some examples, assuming data about service records for automobiles: The GROUP BY to gives a clue of what the report might be about.

1. WHERE make = ? AND model_year = ? GROUP BY service_date, service_type

2. WHERE make = ? AND model = ? GROUP BY service_date, service_type

3. WHERE service_type = ? GROUP BY make, model, service_date

4. WHERE service_date between ? and ? GROUP BY make, model, model_year

You need to allow for 'ad hoc' queries? Well, look at all the ad hoc queries -- they all have a date range, plus nail down one or two other things. (I rarely see something as ugly as '%CL%' for nailing down another dimension.) So, start by thinking of date plus one or two other dimensions as the 'key' into a new summary table. Then comes the question of what data might be desired -- counts, sums, etc. Eventually you have a small set of summary tables. Then build a front end to allow them to pick only from those possibilities. It should encourage use of the existing summary tables, not be truly 'open ended'.

Later, another 'requirement' may surface. So, build another summary table. Of course, it may take a day to initially populate it.

Games on summary tables

Does one ever need to summarize a summary table? Yes, but only in extreme situations. Usually a 'weekly' report can be derived from a 'daily' summary table; building a separate weekly summary table not being worth the effort.

Would one ever PARTITION a Summary Table? Yes, in extreme situations, such as the table being large, and

• Need to purge old data (unlikely), or

• Recent' data is usually requested, and the index(es) fail to prevent table scans (rare). ("Partition pruning" to the rescue.)

See also

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: summarytables

Examples

• 1876

• 1766831

• 1766831

_{This page is licensed: CC BY-SA / Gnu FDL}

Preface

This document discusses techniques for improving performance for data-warehouse-like tables in MariaDB and MySQL.

• How to load large tables.

• Normalization.

• Developing 'summary tables' to make 'reports' efficient.

• Purging old data.

Details on summary tables is covered in the companion document: Summary Tables.

Terminology

This list mirrors "Data Warehouse" terminology.

• Fact table -- The one huge table with the 'raw' data.

• Summary table -- a redundant table of summarized data that could -- use for efficiency

• Dimension -- columns that identify aspects of the dataset (region, country, user, SKU, zipcode, ...)

• Normalization table (dimension table) -- mapping between strings an ids; used for space and speed.

• Normalization -- The process of building the mapping ('New York City' <-> 123)

Fact table

Techniques that should be applied to the huge Fact table.

• id INT/BIGINT UNSIGNED NOT NULL AUTO_INCREMENT

• PRIMARY KEY (id)

• Probably no other INDEXes

• Accessed only via id

• All VARCHARs are "normalized"; ids are stored instead

• ENGINE = InnoDB

• All "reports" use summary tables, not the Fact table

• Summary tables may be populated from ranges of id (other techniques described below)

There are exceptions where the Fact table must be accessed to retrieve multiple rows. However, you should minimize the number of INDEXes on the table because they are likely to be costly on INSERT.

Why keep the Fact table?

Once you have built the Summary table(s), there is not much need for the Fact table. One option that you should seriously consider is to not have a Fact table. Or, at least, you could purge old data from it sooner than you purge the Summary tables. Maybe even keep the Summary tables forever.

Case 1: You need to find the raw data involved in some event. But how will you find those row(s)? This is where a secondary index may be required.

If a secondary index is bigger than can be cached in RAM, and if the column(s) being indexed is random, then each row inserted may cause a disk hit to update the index. This limits insert speed to something like 100 rows per second (on ordinary disks). Multiple random indexes slow down insertion further. RAID striping and/or SSDs speed up insertion. Write caching helps, but only for bursts.

Case 2: You need some event, but you did not plan ahead with the optimal INDEX. Well, if the data is PARTITIONed on date, so even if you have a clue of when the event occurred, "partition pruning" will keep the query from being too terribly slow.

Case 3: Over time, the application is likely to need new 'reports', which may lead to a new Summary table. At this point, it would be handy to scan through the old data to fill up the new table.

Case 4: You find a flaw in the summarization, and need to rebuild an existing Summary table.

Cases 3 and 4 both need the "raw" data. But they don't necessarily need the data sitting in a database table. It could be in the pre-database format (such as log files). So, consider not building the Fact table, but simply keep the raw data, comressed, on some file system.

Batching the load of the Fact table

When talking about billions of rows in the Fact table, it is essentially mandatory that you "batch" the inserts. There are two main ways:

• INSERT INTO Fact (.,.,.) VALUES (.,.,.), (.,.,.), ...; -- "Batch insert"

• LOAD DATA ...;

A third way is to INSERT or LOAD into a Staging table, then

• INSERT INTO Fact SELECT * FROM Staging; This INSERT..SELECT allows you to do other things, such as normalization. More later.

Batched INSERT Statement

Chunk size should usually be 100-1000 rows.

• 100-1000 an insert will run 10 times as fast as single-row inserts.

• Beyond 100, you may be interfering replication and SELECTs.

• Beyond 1000, you are into diminishing returns -- virtually no further performance gains.

• Don't go past, say, 1MB for the constructed INSERT statement. This deals with packet sizes, etc. (1MB is unlikely to be hit for a Fact table.) Decide whether your application should lean toward the 100 or the 1000.

If your data is coming in continually, and you are adding a batching layer, let's do some math. Compute your ingestion rate -- R rows per second.

• If R < 10 (= 1M/day = 300M/year) -- single-row INSERTs would probably work fine (that is, batching is optional)

• If R < 100 (3B records per year) -- secondary indexes on Fact table may be ok

• If R < 1000 (100M records/day) -- avoid secondary indexes on Fact table.

• If R > 1000 -- Batching may not work. Decide how long (S seconds) you can stall loading the data in order to collect a batch of rows.

• If S < 0.1s -- May not be able to keep up

If batching seems viable, then design the batching layer to gather for S seconds or 100-1000 rows, whichever comes first.

(Note: Similar math applies to rapid UPDATEs of a table.)

Normalization (Dimension) table

Normalization is important in Data Warehouse applications because it significantly cuts down on the disk footprint and improves performance. There are other reasons for normalizing, but space is the important one for DW.

Here is a typical pattern for a Dimension table:

CREATE TABLE Emails (
        email_id MEDIUMINT UNSIGNED NOT NULL AUTO_INCREMENT,  -- don't make bigger than needed
        email VARCHAR(...) NOT NULL,
        PRIMARY KEY (email),  -- for looking up one way
        INDEX(email_id)  -- for looking up the other way (UNIQUE is not needed)
    ) ENGINE = InnoDB;  -- to get clustering

Notes:

• MEDIUMINT is 3 bytes with UNSIGNED range of 0..16M; pick SMALLINT, INT, etc, based on a conservative estimate of how many 'foo's you will eventually have.

• datatype sizes

• There may be more than one VARCHAR in the table. Example: For cities, you might have City and Country.

• InnoDB is better than MyISAM because of way the two keys are structured.

• The secondary key is effectively (email_id, email), hence 'covering' for certain queries.

• It is OK to not specify an AUTO_INCREMENT to be UNIQUE.

Batched normalization

I bring this up as a separate topic because of some of the subtle issues that can happen.

You may be tempted to do

INSERT IGNORE INTO Foos
        SELECT DISTINCT foo FROM Staging;  -- not wise

It has the problem of "burning" AUTO_INCREMENT ids. This is because MariaDB pre-allocates ids before getting to "IGNORE". That could rapidly increase the AUTO_INCREMENT values beyond what you expected.

Better is this...

INSERT IGNORE INTO Foos
        SELECT DISTINCT foo
            FROM Staging
            LEFT JOIN Foos ON Foos.foo = Staging.foo
            WHERE Foos.foo_id IS NULL;

Notes:

• The LEFT JOIN .. IS NULL finds the foos that are not yet in Foos.

• This INSERT..SELECT must not be done inside the transaction with the rest of the processing. Otherwise, you add to deadlock risks, leading to burned ids.

• IGNORE is used in case you are doing the INSERT from multiple processes simultaneously.

Once that INSERT is done, this will find all the foo_ids it needs:

INSERT INTO Fact (..., foo_id, ...)
        SELECT ..., Foos.foo_id, ...
            FROM Staging
            JOIN Foos ON Foos.foo = Staging.foo;

An advantage of "Batched Normalization" is that you can summarize directly from the Staging table. Two approaches:

Case 1: PRIMARY KEY (dy, foo) and summarization is in lock step with, say, changes in dy.

• This approach can have troubles if new data arrives after you have summarized the day's data.

INSERT INTO Summary (dy, foo, ct, blah_total)
        SELECT  DATE(dt) AS dy, foo,
                COUNT(*) AS ct, SUM(blah) AS blah_total)
            FROM Staging
            GROUP BY 1, 2;

Case 2: (dy, foo) is a non-UNIQUE INDEX.

• Same code as Case 1.

• By having the index be non-UNIQUE, delayed data simply shows up as extra rows.

• You need to take care to avoid summarizing the data twice. (The id on the Fact table may be a good tool for that.)

Case 3: PRIMARY KEY (dy, foo) and summarization can happen anytime.

INSERT INTO Summary (dy, foo, ct, blah_total)
        ON DUPLICATE KEY UPDATE
            ct = ct + VALUE(ct),
            blah_total = blah_total + VALUE(bt)
        SELECT  DATE(dt) AS dy, foo,
                COUNT(*) AS ct, SUM(blah) AS bt)
            FROM Staging
            GROUP BY 1, 2;

Too many choices?

This document lists a number of ways to do things. Your situation may lead to one approach being more/less acceptable. But, if you are thinking "Just tell me what to do!", then here:

• Batch load the raw data into a temporary table (Staging).

• Normalize from Staging -- use code in Case 3.

• INSERT .. SELECT to move the data from Staging into the Fact table

• Summarize from Staging to Summary table(s) via IODKU (Insert ... On Duplicate Key Update).

• Drop the Staging

Those techniques should perform well and scale well in most cases. As you develop your situation, you may discover why I described alternative solutions.

Purging old data

Typically the Fact table is PARTITION BY RANGE (10-60 ranges of days/weeks/etc) and needs purging (DROP PARTITION) periodically. This discusses a safe/clean way to design the partitioning and do the DROPs: Purging PARTITIONs

Master / slave

For "read scaling", backup, and failover, use master-slave replication or something fancier. Do ingestion only on a single active master; it replicate to the slave(s). Generate reports on the slave(s).

Sharding

"Sharding" is the splitting of data across multiple servers. (In contrast, replication and Galera have the same data on all servers, requiring all data to be written to all servers.)

With the non-sharding techniques described here, terabyte(s) of data can be handled by a single machine. Tens of terabytes probably requires sharding.

Sharding is beyond the scope of this document.

How fast? How big?

With the techniques described here, you may be able to achieve the following performance numbers. I say "may" because every data warehouse situation is different, and you may require performance-hurting deviations from what I describe here. I give multiple options for some aspects; these may cover some of your deviations.

One big performance killer is UUID/GUID keys. Since they are very 'random', updates of them (at scale) are limited to 1 row = 1 disk hit. Plain disks can handle only 100 hits/second. RAID and/or SSD can increase that to something like 1000 hits/sec. Huge amounts of RAM (for caching the random index) are a costly solution. It is possible to turn type-1 UUIDs into roughly-chronological keys, thereby mittigating the performance problems if the UUIDs are written/read with some chronological clustering. UUID discussion

Hardware, etc:

• Single SATA drive: 100 IOPs (Input/Output operations per second)

• RAID with N physical drives -- 100*N IOPs (roughly)

• SSD -- 5 times as fast as rotating media (in this context)

• Batch INSERT -- 100-1000 rows is 10 times as fast as INSERTing 1 row at a time (see above)

• Purge "old" data -- Do not use DELETE or TRUNCATE, design so you can use DROP PARTITION (see above)

• Think of each INDEX (except the PRIMARY KEY on InnoDB) as a separate table

• Consider access patterns of each table/index: random vs at-the-end vs something in between

"Count the disk hits" -- back-of-envelope performance analysis

• Random accesses to a table/index -- count each as a disk hit.

• At-the-end accesses (INSERT chronologically or with AUTO_INCREMENT; range SELECT) -- count as zero hits.

• In between (hot/popular ids, etc) -- count as something in between

• For INSERTs, do the analysis on each index; add them up.

• For SELECTs, do the analysis on the one index used, plus the table. (Use of 2 indexes is rare.) Insert cost, based on datatype of first column in an index:

• AUTO_INCREMENT -- essentially 0 IOPs

• DATETIME, TIMESTAMP -- essentially 0 for 'current' times

• UUID/GUID -- 1 per insert (terrible)

• Others -- depends on their patterns SELECT cost gets a little tricky:

• Range on PRIMARY KEY -- think of it as getting 100 rows per disk hit.

• IN on PRIMARY KEY -- 1 disk hit per item in IN

• "=" -- 1 hit (for 1 row)

• Secondary key -- First compute the hits for the index, then...

• Think of each row as needing 1 disk hit.

• However, if the rows are likely to be 'near' each other (based on the PRIMARY KEY), then it could be < 1 disk hit/row.

More on Count the Disk Hits

How fast?

Look at your data; compute raw rows per second (or hour or day or year). There are about 30M seconds in a year; 86,400 seconds per day. Inserting 30 rows per second becomes a billion rows per year.

10 rows per second is about all you can expect from an ordinary machine (after allowing for various overheads). If you have less than that, you don't have many worries, but still you should probably create Summary tables. If more than 10/sec, then batching, etc, becomes vital. Even on spiffy hardware, 100/sec is about all you can expect without utilizing the techniques here.

Not so fast?

Let's say your insert rate is only one-tenth of your disk IOPs (eg, 10 rows/sec vs 100 IOPs). Also, let's say your data is not "bursty"; that is, the data comes in somewhat soothly throughout the day.

Note that 10 rows/sec (300M/year) implies maybe 30GB for data + indexes + normalization tables + summary tables for 1 year. I would call this "not so big".

Still, the normalization and summarization are important. Normalization keeps the data from being, say, twice as big. Summarization speeds up the reports by orders of magnitude.

Let's design and analyse a "simple ingestion scheme" for 10 rows/second, without 'batching'.

# Normalize:
    $foo_id = SELECT foo_id FROM Foos WHERE foo = $foo;
    IF NO $foo_id, THEN
        INSERT IGNORE INTO Foos ...

    # Inserts:
    BEGIN;
        INSERT INTO Fact ...;
        INSERT INTO Summary ... ON DUPLICATE KEY UPDATE ...;
    COMMIT;
    # (plus code TO deal WITH errors ON INSERTs OR COMMIT)

Depending on the number and randomness of your indexes, etc, 10 Fact rows may (or may not) take less than 100 IOPs.

Also, note that as the data grows over time, random indexes will become less and less likely to be cached. That is, even if runs fine with 1 year's worth of data, it may be in trouble with 2 year's worth.

For those reasons, I started this discussion with a wide margin (10 rows versus 100 IOPs).

References

• sec. 3.3.2: Dimensional Model and "Star schema"

• Summary Tables

See also

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: datawarehouse

_{This page is licensed: CC BY-SA / Gnu FDL}

Basics

One can use DISTINCT keyword to de-duplicate the arguments of an aggregate function. For example:

SELECT COUNT(DISTINCT col1) FROM tbl1;

In order to compute this, MariaDB has to collect the values of col1 and remove the duplicates. This may be computationally expensive.

After the fix for MDEV-30660 (available from MariaDB 10.5.25, MariaDB 10.6.18, MariaDB 10.11.8, MariaDB 11.0.6, MariaDB 11.1.5, MariaDB 11.2.4, MariaDB 11.4.2), the optimizer can detect certain cases when argument of aggregate function will not have duplicates and so de-duplication can be skipped.

When one can skip de-duplication

A basic example: if we're doing a select from one table, then the values of primary_key are already distinct:

SELECT aggregate_func(DISTINCT tbl.primary_key, ...) FROM tbl;

If the SELECT has other constant tables, that's also ok, as they will not create duplicates.

The next step: a part of the primary key can be "bound" by the GROUP BY clause. Consider a query:

SELECT aggregate_func(DISTINCT t1.pk1, ...) FROM t1 GROUP BY t1.pk2;

Suppose the table has PRIMARY KEY(pk1, pk2). Grouping by pk2 fixes the value of pk2 within each group. Then, the values of pk1 must be unique within each group, and de-duplication is not necessary.

Observability

EXPLAIN or EXPLAIN FORMAT=JSON do not show any details about how aggregate functions are computed. One has to look at the Optimizer Trace. Search for aggregator_type:

When de-duplication is necessary, it will show:

{
            "prepare_sum_aggregators": {
              "function": "count(distinct t1.col1)",
              "aggregator_type": "distinct"
            }
          }

When de-duplication is not necessary, it will show:

{
            "prepare_sum_aggregators": {
              "function": "count(distinct t1.pk1)",
              "aggregator_type": "simple"
            }
          }

_{This page is licensed: CC BY-SA / Gnu FDL}

Basic idea

Consider a query with a WHERE clause:

WHERE col1=col2 AND ...

the WHERE clause will compute to true only if col1=col2. This means that in the rest of the WHERE clause occurrences of col1 can be substituted with col2 (with some limitations which are discussed in the next section). This allows the optimizer to infer additional restrictions.

For example:

WHERE col1=col2 AND col1=123

allows to infer a new equality: col2=123

WHERE col1=col2 AND col1 < 10

allows to infer that col2<10.

Identity and comparison substitution

There are some limitations to where one can do the substitution, though.

The first and obvious example is the string datatype and collations. Most commonly-used collations in SQL are "case-insensitive", that is 'A'='a'. Also, most collations have a "PAD SPACE" attribute, which means that comparison ignores the spaces at the end of the value, 'a'='a '.

Now, consider a query:

INSERT INTO t1 (col1, col2) VALUES ('ab', 'ab   ');
SELECT * FROM t1 WHERE col1=col2 AND LENGTH(col1)=2

Here, col1=col2, the values are "equal". At the same time LENGTH(col1)=2, while LENGTH(col2)=4, which means one can't perform the substiution for the argument of LENGTH(...).

It's not only collations. There are similar phenomena when equality compares columns of different datatypes. The exact criteria of when thy happen are rather convoluted.

The take-away is: sometimes, X=Y does not mean that one can replace any reference to X with Y. What one CAN do is still replace the occurrence in the comparisons <, >, >=, <=, etc.

This is how we get two kinds of substitution:

• Identity substitution: X=Y, and any occurrence of X can be replaced with Y.

• Comparison substitution: X=Y, and an occurrence of X in a comparison (X<Z) can be replaced with Y (Y<Z).

Place in query optimization

(A draft description): Let's look at how Equality Propagation is integrated with the rest of the query optimization process.

• First, multiple-equalities are built (TODO example from optimizer trace)

  • If multiple-equality includes a constant, fields are substituted with a constant if possible.

• From this point, all optimizations like range optimization, ref access, etc make use of multiple equalities: when they see a reference to tableX.columnY somewhere, they also look at all the columns that tableX.columnY is equal to.

• After the join order is picked, the optimizer walks through the WHERE clause and substitutes each field reference with the "best" one - the one that can be checked as soon as possible.

  • Then, the parts of the WHERE condition are attached to the tables where they can be checked.

Interplay with ORDER BY optimization

Consider a query:

SELECT ... FROM ... WHERE col1=col2 ORDER BY col2

Suppose, there is an INDEX(col1). MariaDB optimizer is able to figure out that it can use an index on col1 (or sort by the value of col1) in order to resolve ORDER BY col2.

Optimizer trace

Look at these elements:

• condition_processing

• attaching_conditions_to_tables

More details

Equality propagation doesn't just happen at the top of the WHERE clause. It is done "at all levels" where a level is:

• A top level of the WHERE clause.

• If the WHERE clause has an OR clause, each branch of the OR clause.

• The top level of any ON expression

• (the same as above about OR-levels)

_{This page is licensed: CC BY-SA / Gnu FDL}

Optimization Description

When n is sufficiently small, the optimizer will use a priority queue for sorting. Before the optimization's porting to MariaDB 10.0, the alternative was, roughly speaking, to sort the entire output and then pick only first n rows.

NOTE: The problem of choosing which index to use for query with ORDER BY ... LIMIT is a different problem, see optimizer_join_limit_pref_ratio-optimization.

Optimization Visibility in MariaDB

There are two ways to check whether filesort has used a priority queue.

Status Variable

The first way is to check the Sort_priority_queue_sorts status variable. It shows the number of times that sorting was done through a priority queue. (The total number of times sorting was done is a sum Sort_range and Sort_scan).

Slow Query Log

The second way is to check the slow query log. When one uses Extended statistics in the slow query log and specifies log_slow_verbosity=query_plan, slow query log entries look like this

# Time: 140714 18:30:39
# User@Host: root[root] @ localhost []
# Thread_id: 3  Schema: test  QC_hit: No
# Query_time: 0.053857  Lock_time: 0.000188  Rows_sent: 11  Rows_examined: 100011
# Full_scan: Yes  Full_join: No  Tmp_table: No  Tmp_table_on_disk: No
# Filesort: Yes  Filesort_on_disk: No  Merge_passes: 0  Priority_queue: Yes
SET timestamp=1405348239;SET timestamp=1405348239;
select * from t1 where col1 between 10 and 20 order by col2 limit 100;

Note the "Priority_queue: Yes" on the last comment line. (pt-query-digest is able to parse slow query logs with the Priority_queue field)

As for EXPLAIN, it will give no indication whether filesort uses priority queue or the generic quicksort and merge algorithm. Using filesort will be shown in both cases, by both MariaDB and MySQL.

See Also

• LIMIT Optimization page in the MySQL 5.6 manual (search for "priority queue").

• MySQL WorkLog entry, WL#1393

• MDEV-415, MDEV-6430

_{This page is licensed: CC BY-SA / Gnu FDL}

Description

Forcing an index to be used is mostly useful when the optimizer decides to do a table scan even if you know that using an index would be better. (The optimizer could decide to do a table scan even if there is an available index when it believes that most or all rows will match and it can avoid the overhead of using the index).

FORCE INDEX works by only considering the given indexes (like with USE_INDEX) but in addition it tells the optimizer to regard a table scan as something very expensive. However if none of the 'forced' indexes can be used, then a table scan will be used anyway.

FORCE INDEX cannot force an ignored index to be used - it will be treated as if it doesn't exist.

Example

CREATE INDEX Name ON City (Name);
EXPLAIN SELECT Name,CountryCode FROM City FORCE INDEX (Name)
WHERE name>="A" AND CountryCode >="A";

This produces:

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	City	range	Name	Name	35	NULL	4079	Using where

Index Prefixes

When using index hints (USE, FORCE or IGNORE INDEX), the index name value can also be an unambiguous prefix of an index name.

See Also

• Index Hints: How to Force Query Plans for more details

• USE INDEX

• IGNORE INDEX

• Ignored Indexes

_{This page is licensed: CC BY-SA / Gnu FDL}

The problem

You want to find the largest row in each group of rows. An example is looking for the largest city in each state. While it is easy to find the MAX(population) ... GROUP BY state, it is hard to find the name of the city associated with that population. Alas, MySQL and MariaDB do not have any syntax to provide the solution directly.

This article is under construction, mostly for cleanup. The content is reasonably accurate during construction.

The article presents two "good" solutions. They differ in ways that make neither of them 'perfect'; you should try both and weigh the pros and cons.

Also, a few "bad" solutions will be presented, together with why they were rejected.

MySQL manual gives 3 solutions; only the "Uncorrelated" one is "good", the other two are "bad".

Sample data

To show how the various coding attempts work, I have devised this simple task: Find the largest city in each Canadian province. Here's a sample of the source data (5493 rows):

+------------------+----------------+------------+
| province         | city           | population |
+------------------+----------------+------------+
| Saskatchewan     | Rosetown       |       2309 |
| British Columbia | Chilliwack     |      51942 |
| Nova Scotia      | Yarmouth       |       7500 |
| Alberta          | Grande Prairie |      41463 |
| Quebec           | Sorel          |      33591 |
| Ontario          | Moose Factory  |       2060 |
| Ontario          | Bracebridge    |       8238 |
| British Columbia | Nanaimo        |      84906 |
| Manitoba         | Neepawa        |       3151 |
| Alberta          | Grimshaw       |       2560 |
| Saskatchewan     | Carnduff       |        950 |
...

Here's the desired output (13 rows):

+---------------------------+---------------+------------+
| province                  | city          | population |
+---------------------------+---------------+------------+
| Alberta                   | Calgary       |     968475 |
| British Columbia          | Vancouver     |    1837970 |
| Manitoba                  | Winnipeg      |     632069 |
| New Brunswick             | Saint John    |      87857 |
| Newfoundland and Labrador | Corner Brook  |      18693 |
| Northwest Territories     | Yellowknife   |      15866 |
| Nova Scotia               | Halifax       |     266012 |
| Nunavut                   | Iqaluit       |       6124 |
| Ontario                   | Toronto       |    4612187 |
| Prince Edward Island      | Charlottetown |      42403 |
| Quebec                    | Montreal      |    3268513 |
| Saskatchewan              | Saskatoon     |     198957 |
| Yukon                     | Whitehorse    |      19616 |
+---------------------------+---------------+------------+

Duplicate max

One thing to consider is whether you want -- or do not want -- to see multiple rows for tied winners. For the dataset being used here, that would imply that the two largest cities in a province had identical populations. For this case, a duplicate would be unlikely. But there are many groupwise-max use cases where duplictes are likely.

The two best algorithms differ in whether they show duplicates.

Using an uncorrelated subquery

Characteristics:

• Superior performance or medium performance

• It will show duplicates

• Needs an extra index

• Probably requires 5.6

• If all goes well, it will run in O(M) where M is the number of output rows.

An 'uncorrelated subquery':

SELECT  c1.province, c1.city, c1.population
    FROM  Canada AS c1
    JOIN
      ( SELECT  province, MAX(population) AS population
            FROM  Canada
            GROUP BY  province
      ) AS c2 USING (province, population)
    ORDER BY c1.province;

But this also 'requires' an extra index: INDEX(province, population). In addition, MySQL has not always been able to use that index effectively, hence the "requires 5.6". (I am not sure of the actual version.)

Without that extra index, you would need 5.6, which has the ability to create indexes for subqueries. This is indicated by <auto_key0> in the EXPLAIN. Even so, the performance is worse with the auto-generated index than with the manually generated one.

With neither the extra index, nor 5.6, this 'solution' would belong in 'The Duds' because it would run in O(N*N) time.

Using @variables

Characteristics:

• Good performance

• Does not show duplicates (picks one to show)

• Consistent O(N) run time (N = number of input rows)

• Only one scan of the data

SELECT
        province, city, population   -- The desired columns
    FROM
      ( SELECT  @prev := '' ) init
    JOIN
      ( SELECT  province != @prev AS first,  -- `province` is the 'GROUP BY'
                @prev := province,           -- The 'GROUP BY'
                province, city, population   -- Also the desired columns
            FROM  Canada           -- The table
            ORDER BY
                province,          -- The 'GROUP BY'
                population DESC    -- ASC for MIN(population), DESC for MAX
      ) x
    WHERE  first
    ORDER BY  province;     -- Whatever you like

For your application, change the lines with comments.

The duds

*** 'correlated subquery' (from MySQL doc):**

SELECT  province, city, population
    FROM  Canada AS c1
    WHERE  population =
      ( SELECT  MAX(c2.population)
            FROM  Canada AS c2
            WHERE  c2.province= c1.province
      )
    ORDER BY  province;

O(N*N) (that is, terrible) performance

*** LEFT JOIN (from MySQL doc):**

SELECT  c1.province, c1.city, c1.population
    FROM  Canada AS c1
    LEFT JOIN  Canada AS c2 ON c2.province = c1.province
      AND  c2.population > c1.population
    WHERE  c2.province IS NULL
    ORDER BY province;

Medium performance (2N-3N, depending on join_buffer_size).

For O(N*N) time,... It will take one second to do a groupwise-max on a few thousand rows; a million rows could take hours.

Top-N in each group

This is a variant on "groupwise-max" wherein you desire the largest (or smallest) N items in each group. Do these substitutions for your use case:

• province --> your 'GROUP BY'

• Canada --> your table

• 3 --> how many of each group to show

• population --> your numeric field for determining "Top-N"

• city --> more field(s) you want to show

• Change the SELECT and ORDER BY if you desire

• DESC to get the 'largest'; ASC for the 'smallest'

SELECT
        province, n, city, population
    FROM
      ( SELECT  @prev := '', @n := 0 ) init
    JOIN
      ( SELECT  @n := if(province != @prev, 1, @n + 1) AS n,
                @prev := province,
                province, city, population
            FROM  Canada
            ORDER BY
                province   ASC,
                population DESC
      ) x
    WHERE  n <= 3
    ORDER BY  province, n;

Output:

+---------------------------+------+------------------+------------+
| province                  | n    | city             | population |
+---------------------------+------+------------------+------------+
| Alberta                   |    1 | Calgary          |     968475 |
| Alberta                   |    2 | Edmonton         |     822319 |
| Alberta                   |    3 | Red Deer         |      73595 |
| British Columbia          |    1 | Vancouver        |    1837970 |
| British Columbia          |    2 | Victoria         |     289625 |
| British Columbia          |    3 | Abbotsford       |     151685 |
| Manitoba                  |    1 | ...

The performance of this is O(N), actually about 3N, where N is the number of source rows.

EXPLAIN EXTENDED gives

+----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+
| id | select_type | table      | type   | possible_keys | key  | key_len | ref  | rows | filtered | Extra          |
+----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+
|  1 | PRIMARY     | <derived2> | system | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using filesort |
|  1 | PRIMARY     | <derived3> | ALL    | NULL          | NULL | NULL    | NULL | 5484 |   100.00 | Using where    |
|  3 | DERIVED     | Canada     | ALL    | NULL          | NULL | NULL    | NULL | 5484 |   100.00 | Using filesort |
|  2 | DERIVED     | NULL       | NULL   | NULL          | NULL | NULL    | NULL | NULL |     NULL | No tables used |
+----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+

Explanation, shown in the same order as the EXPLAIN, but numbered chronologically: 3. Get the subquery id=2 (init) 4. Scan the output from subquery id=3 (x) 2. Subquery id=3 -- the table scan of Canada

1. Subquery id=2 -- init for simply initializing the two @variables Yes, it took two sorts, though probably in RAM.

Main Handler values:

| Handler_read_rnd           | 39    |
| Handler_read_rnd_next      | 10971 |
| Handler_write              | 5485  |  -- #rows in Canada (+1)

Top-n in each group, take II

This variant is faster than the previous, but depends on city being unique across the dataset. (from openark.org)

SELECT  province, city, population
        FROM  Canada
        JOIN
          ( SELECT  GROUP_CONCAT(top_in_province) AS top_cities
                FROM
                  ( SELECT  SUBSTRING_INDEX(
                                   GROUP_CONCAT(city ORDER BY  population DESC),
                            ',', 3) AS top_in_province
                        FROM  Canada
                        GROUP BY  province
                  ) AS x
          ) AS y
        WHERE  FIND_IN_SET(city, top_cities)
        ORDER BY  province, population DESC;

Output. Note how there can be more than 3 cities per province:

| Alberta                   | Calgary          |     968475 |
| Alberta                   | Edmonton         |     822319 |
| Alberta                   | Red Deer         |      73595 |
| British Columbia          | Vancouver        |    1837970 |
| British Columbia          | Victoria         |     289625 |
| British Columbia          | Abbotsford       |     151685 |
| British Columbia          | Sydney           |          0 | -- Nova Scotia's second largest is Sydney
| Manitoba                  | Winnipeg         |     632069 |

Main Handler values:

| Handler_read_next          | 5484  | -- table size
| Handler_read_rnd_next      | 5500  | -- table size + number of provinces
| Handler_write              | 14    | -- number of provinces (+1)

Top-n using MyISAM

(This does not need your table to be MyISAM, but it does need MyISAM tmp table for its 2-column PRIMARY KEY feature.) See previous section for what changes to make for your use case.

-- build tmp table to get numbering
    -- (Assumes auto_increment_increment = 1)
    CREATE TEMPORARY TABLE t (
        nth MEDIUMINT UNSIGNED NOT NULL AUTO_INCREMENT,
        PRIMARY KEY(province, nth)
    ) ENGINE=MyISAM
        SELECT province, NULL AS nth, city, population
            FROM Canada
            ORDER BY population DESC;
    -- Output the biggest 3 cities in each province:
    SELECT province, nth, city, population
        FROM t
        WHERE nth <= 3
        ORDER BY province, nth;

+---------------------------+-----+------------------+------------+
| province                  | nth | city             | population |
+---------------------------+-----+------------------+------------+
| Alberta                   |   1 | Calgary          |     968475 |
| Alberta                   |   2 | Edmonton         |     822319 |
| Alberta                   |   3 | Red Deer         |      73595 |
| British Columbia          |   1 | Vancouver        |    1837970 |
| British Columbia          |   2 | Victoria         |     289625 |
| British Columbia          |   3 | Abbotsford       |     151685 |
| Manitoba                  |  ...

SELECT FOR CREATE:
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | Canada | ALL  | NULL          | NULL | NULL    | NULL | 5484 | Using filesort |
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
Other SELECT:
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | t     | index | NULL          | PRIMARY | 104     | NULL |   22 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+

The main handler values (total of all operations):

| Handler_read_rnd_next      | 10970 |
| Handler_write              | 5484  |  -- number of rows in Canada (write tmp table)

Both "Top-n" formulations probably take about the same amount of time.

Windowing functions

Hot off the press from Percona Live... MariaDB 10.2 has "windowing functions", which make "groupwise max" much more straightforward.

The code:

TBD

Postlog

Developed an first posted, Feb, 2015; Add MyISAM approach: July, 2015; Openark's method added: Apr, 2016; Windowing: Apr 2016

I did not include the technique(s) using GROUP_CONCAT. They are useful in some situations with small datasets. They can be found in the references below.

See also

• This has some of these algorithms, plus some others: Peter Brawley's blog

• Jan Kneschke's blog from 2007

• StackOverflow discussion of 'Uncorrelated'

• Other references: Inner ORDER BY thrown away

• Adding a large LIMIT to a subquery may make things work. Why ORDER BY in subquery is ignored

• StackOverflow thread

• row_number(), rank(), dense_rank()

• [http://rpbouman.blogspot.de/2008/07/calculating-nth-percentile-in-mysql.html]Perentile blog

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: groupwise_max

_{This page is licensed: CC BY-SA / Gnu FDL}

The problem

GUIDs/UUIDs (Globally/Universally Unique Identifiers) are very random. Therefore, INSERTing into an index means jumping around a lot. Once the index is too big to be cached, most INSERTs involve a disk hit. Even on a beefy system, this limits you to a few hundred INSERTs per second.

MariaDB's UUID function.

This blog is mostly eliminated in MySQL 8.0 with the advent of the following function:UUID_TO_BIN(str, swap_flag).

Why it is a problem

A 'standard' GUID/UUID is composed of the time, machine identification and some other stuff. The combination should be unique, even without coordination between different computers that could be generating UUIDs simultaneously.

The top part of the GUID/UUID is the bottom part of the current time. The top part is the primary part of what would be used for placing the value in an ordered list (INDEX). This cycles in about 7.16 minutes.

Some math... If the index is small enough to be cached in RAM, each insert into the index is CPU only, with the writes being delayed and batched. If the index is 20 times as big as can be cached, then 19 out of 20 inserts will be a cache miss. (This math applies to any "random" index.)

Second problem

36 characters is bulky. If you are using that as a PRIMARY KEY in InnoDB and you have secondary keys, remember that each secondary key has an implicit copy of the PK, thereby making it bulky.

It is tempting to declare the UUID VARCHAR(36). And, since you probably are thinking globally, so you have CHARACTER SET utf8 (or utf8mb4). For utf8:

• 2 - Overhead for VAR

• 36 - chars

• 3 (or 4) bytes per character for utf8 (or utf8mb4) So, max length = 2+3*36 = 110 (or 146) bytes. For temp tables 108 (or 144) is actually used if a MEMORY table is used.

To compress

• utf8 is unnecessary (ascii would do); but this is obviated by the next two steps

• Toss dashes

• UNHEX Now it will fit in 16 bytes: BINARY(16)

Combining the problems and crafting a solution

But first, a caveat. This solution only works for "Time based" / "Version 1" UUIDs They are recognizable by the "1" at the beginning of the third clump.

The manual's sample: 6ccd780c-baba-1026-9564-0040f4311e29 . A more current value (after a few years): 49ea2de3-17a2-11e2-8346-001eecac3efa . Notice how the 3rd part has slowly changed over time? Let's data is rearranged, thus:

1026-baba-6ccd780c-9564-0040f4311e29
      11e2-17a2-49ea2de3-8346-001eecac3efa
      11e2-17ac-106762a5-8346-001eecac3efa -- after a few more minutes

Now we have a number that increases nicely over time. Multiple sources won't be quite in time order, but they will be close. The "hot" spot for inserting into an INDEX(uuid) will be rather narrow, thereby making it quite cacheable and efficient.

If your SELECTs tend to be for "recent" uuids, then they, too, will be easily cached. If, on the other hand, your SELECTs often reach for old uuids, they will be random and not well cached. Still, improving the INSERTs will help the system overall.

Code to do it

Let's make Stored Functions to do the messy work of the two actions:

• Rearrange fields

• Convert to/from BINARY(16)

DELIMITER //

    CREATE FUNCTION UuidToBin(_uuid BINARY(36))
        RETURNS BINARY(16)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        UNHEX(CONCAT(
            SUBSTR(_uuid, 15, 4),
            SUBSTR(_uuid, 10, 4),
            SUBSTR(_uuid,  1, 8),
            SUBSTR(_uuid, 20, 4),
            SUBSTR(_uuid, 25) ));
    //
    CREATE FUNCTION UuidFromBin(_bin BINARY(16))
        RETURNS BINARY(36)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        LCASE(CONCAT_WS('-',
            HEX(SUBSTR(_bin,  5, 4)),
            HEX(SUBSTR(_bin,  3, 2)),
            HEX(SUBSTR(_bin,  1, 2)),
            HEX(SUBSTR(_bin,  9, 2)),
            HEX(SUBSTR(_bin, 11))
                 ));

    //
    DELIMITER ;

Then you would do things like

-- Letting MySQL create the UUID:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(UUID()), ...);

    -- Creating the UUID elsewhere:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(?), ...);

    -- Retrieving (point query using uuid):
    SELECT ... FROM t WHERE uuid = UuidToBin(?);

    -- Retrieving (other):
    SELECT UuidFromBin(uuid), ... FROM t ...;

Do not flip the WHERE; this will be inefficent because it won't use INDEX(uuid):

WHERE UuidFromBin(uuid) = '1026-baba-6ccd780c-9564-0040f4311e29' -- NO

TokuDB

TokuDB has been deprecated by its upstream maintainer. It is disabled from MariaDB 10.5 and has been removed in MariaDB 10.6 - MDEV-19780. We recommend MyRocks as a long-term migration path.

TokuDB is a viable engine if you must have UUIDs (even non-type-1) in a huge table. TokuDB is available in MariaDB as a 'standard' engine, making the barrier to entry very low. There are a small number of differences between InnoDB and TokuDB; I will not go into them here.

Tokudb, with its “fractal” indexing strategy builds the indexes in stages. In contrast, InnoDB inserts index entries “immediately” — actually that indexing is buffered by most of the size of the buffer_pool. To elaborate…

When adding a record to an InnoDB table, here are (roughly) the steps performed to write the data (and PK) and secondary indexes to disk. (I leave out logging, provision for rollback, etc.) First the PRIMARY KEY and data:

• Check for UNIQUEness constraints

• Fetch the BTree block (normally 16KB) that should contain the row (based on the PRIMARY KEY).

• Insert the row (overflow typically occurs 1% of the time; this leads to a block split).

• Leave the page “dirty” in the buffer_pool, hoping that more rows are added before it is bumped out of cache (buffer_pool).. Note that for AUTO_INCREMENT and TIMESTAMP-based PKs, the “last” block in the data will be updated repeatedly before splitting; hence, this delayed write adds greatly to the efficiency. OTOH, a UUID will be very random; when the table is big enough, the block will almost always be flushed before a second insert occurs in that block. <– This is the inefficiency in UUIDs. Now for any secondary keys:

• All the steps are the same, since an index is essentially a "table" except that the "data" is a copy of the PRIMARY KEY.

• UNIQUEness must be checked immediately — cannot delay the read.

• There are (I think) some other "delays" that avoid some I/O.

Tokudb, on the other hand, does something like

• Write data/index partially sorted records to disk before finding out exactly where it belongs.

• In the background, combine these partially digested blocks. Repeat as needed.

• Eventually move the info into the real table/indexes.

If you are familiar with how sort-merge works, consider the parallels to Tokudb. Each "sort" does some work of ordering things; each "merge" is quite efficient.

To summarize:

• In the extreme (data/index much larger than buffer_pool), InnoDB must read-modify-write one 16KB disk block for each UUID entry.

• Tokudb makes each I/O "count" by merging several UUIDs for each disk block. (Yeah, Toku rereads blocks, but it comes out ahead in the long run.)

• Tokudb excels when the table is really big, which implies high ingestion rate.

Wrapup

This shows three thing for speeding up usage of GUIDs/UUIDs:

• Shrink footprint (Smaller -> more cacheable -> faster).

• Rearrange uuid to make a "hot spot" to improve cachability.

• Use TokuDB (MyRocks shares some architectural traits which may also be beneficial in handling UUIDs, but this is hypothetical and hasn't been tested)

Note that the benefit of the "hot spot" is only partial:

• Chronologically ordered (or approximately ordered) INSERTs benefit; random ones don't.

• SELECTs/UPDATEs by "recent" uuids benefit; old ones don't benefit.

Postlog

Thanks to Trey for some of the ideas here.

The tips in this document apply to MySQL, MariaDB, and Percona.

Written Oct, 2012. Added TokuDB, Jan, 2015.

See Also

• UUID data type

• Detailed discussion of UUID indexing

• Graphical display of the random nature of UUID on PRIMARY KEY

• Benchmarks, etc, by Karthik Appigatla

• More details on the clock

• Percona benchmarks

• NHibernate can generate sequential GUIDs , but it seems to be backwards.

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: uuid

_{This page is licensed: CC BY-SA / Gnu FDL}

MariaDB starting with 10.6.13

The hash_join_cardinality optimizer_switch flag was added in MariaDB 11.0.2, MariaDB 10.11.3, MariaDB 10.10.4, MariaDB 10.9.6, MariaDB 10.8.8 and MariaDB 10.6.13.

In MySQL and MariaDB, the output cardinality of a part of query has historically been tied to the used access method(s). This is different from the approach used in database textbooks. There, the cardinality "x JOIN y" is the same regardless of which access methods are used to compute it.

Example

Consider a query joining customers with their orders:

SELECT * 
FROM
  customer, orders, ...
WHERE 
  customer.id = orders.customer_id AND ...

Suppose, table orders has an index IDX on orders.customer_id.

If the query plan is using this index to fetch orders for each customer, the optimizer will use index statistics from IDX to estimate the number of rows in the customer-joined-with-orders.

On the other hand, if the optimizer considers a query plan that joins customer with orders without use of indexes, it will ignore the customer.id = orders.customer_id equality completely and will compute the output cardinality as if customer was cross-joined with orders.

Hash Join

MariaDB supports Block Hash Join. It is not enabled by default, one needs to set it join_cache_level to 3 or a bigger value to enable it.

Before MDEV-30812, Query optimization for Block Hash Join would work as described in the above example: It would assume that the join operation is a cross join.

MDEV-30812 introduces a new optimizer_switch flag, hash_join_cardinality. In MariaDB versions before 11.0, it is off by default.

If one sets it to ON, the optimizer will make use of column histograms when computing the cardinality of hash join operation output.

One can see the computation in the Optimizer Trace, search for hash_join_cardinality.

_{This page is licensed: CC BY-SA / Gnu FDL}

This article describes different techniques for inserting data quickly into MariaDB.

Background

When inserting new data into MariaDB, the things that take time are: (in order of importance):

• Syncing data to disk (as part of the end of transactions)

• Adding new keys. The larger the index, the more time it takes to keep keys updated.

• Checking against foreign keys (if they exist).

• Adding rows to the storage engine.

• Sending data to the server.

The following describes the different techniques (again, in order of importance) you can use to quickly insert data into a table.

Disabling Keys

You can temporarily disable updating of non unique indexes. This is mostly useful when there are zero (or very few) rows in the table into which you are inserting data.

ALTER TABLE table_name DISABLE KEYS;
BEGIN;
... inserting data WITH INSERT OR LOAD DATA ....
COMMIT;
ALTER TABLE table_name ENABLE KEYS;

In many storage engines (at least MyISAM and Aria),ENABLE KEYS works by scanning through the row data and collecting keys, sorting them, and then creating the index blocks. This is an order of magnitude faster than creating the index one row at a time and it also uses less key buffer memory.

Note: When you insert into an empty table with INSERT orLOAD DATA, MariaDB automatically does aDISABLE KEYS before and an ENABLE KEYS afterwards.

When inserting big amounts of data, integrity checks are sensibly time-consuming. It is possible to disable the UNIQUE indexes and the foreign keys checks using the unique_checks and the foreign_key_checks system variables:

SET @@session.unique_checks = 0;
SET @@session.foreign_key_checks = 0;

For InnoDB tables, the AUTO_INCREMENT lock mode can be temporarily set to 2, which is the fastest setting:

SET @@global.innodb_autoinc_lock_mode = 2;

Also, if the table has INSERT triggers or PERSISTENT columns, you may want to drop them, insert all data, and recreate them.

Loading Text Files

The fastest way to insert data into MariaDB is through theLOAD DATA INFILE command.

The simplest form of the command is:

LOAD DATA INFILE 'file_name' INTO TABLE table_name;

You can also read a file locally on the machine where the client is running by using:

LOAD DATA LOCAL INFILE 'file_name' INTO TABLE table_name;

This is not as fast as reading the file on the server side, but the difference is not that big.

LOAD DATA INFILE is very fast because:

1. there is no parsing of SQL.

2. data is read in big blocks.

3. if the table is empty at the beginning of the operation, all non unique indexes are disabled during the operation.

4. the engine is told to cache rows first and then insert them in big blocks (At least MyISAM and Aria support this).

5. for empty tables, some transactional engines (like Aria) do not log the inserted data in the transaction log because one can rollback the operation by just doing a TRUNCATE on the table.

Because of the above speed advantages there are many cases, when you need to insert many rows at a time, where it may be faster to create a file locally, add the rows there, and then use LOAD DATA INFILE to load them; compared to using INSERT to insert the rows.

You will also get progress reporting forLOAD DATA INFILE.

mariadb-import

You can import many files in parallel with mariadb-import (mysqlimport before MariaDB 10.5). For example:

mariadb-import --use-threads=10 database text-file-name [text-file-name...]

Internally mariadb-import uses LOAD DATA INFILE to read in the data.

Inserting Data with INSERT Statements

Using Big Transactions

When doing many inserts in a row, you should wrap them with BEGIN / END to avoid doing a full transaction (which includes a disk sync) for every row. For example, doing a begin/end every 1000 inserts will speed up your inserts by almost 1000 times.

BEGIN;
INSERT ...
INSERT ...
END;
BEGIN;
INSERT ...
INSERT ...
END;
...

The reason why you may want to have many BEGIN/END statements instead of just one is that the former will use up less transaction log space.

Multi-Value Inserts

You can insert many rows at once with multi-value row inserts:

INSERT INTO table_name VALUES(1,"row 1"),(2, "row 2"),...;

The limit for how much data you can have in one statement is controlled by themax_allowed_packet server variable.

Inserting Data Into Several Tables at Once

If you need to insert data into several tables at once, the best way to do so is to enable multi-row statements and send many inserts to the server at once:

INSERT INTO table_name_1 (auto_increment_key, data) VALUES (NULL,"row 1");
INSERT INTO table_name_2 (auto_increment, reference, data) VALUES (NULL, LAST_INSERT_ID(), "row 2");

LAST_INSERT_ID() is a function that returns the lastauto_increment value inserted.

By default, the command line mariadb client will send the above as multiple statements.

To test this in the mariadb client you have to do:

delimiter ;;
SELECT 1; SELECT 2;;
delimiter ;

Note: for multi-query statements to work, your client must specify theCLIENT_MULTI_STATEMENTS flag to mysql_real_connect().

Server Variables That Can be Used to Tune Insert Speed

See Server System Variables for the full list of server variables.

_{This page is licensed: CC BY-SA / Gnu FDL}

Syntax

IGNORE INDEX [{FOR {JOIN|ORDER BY|GROUP BY}] ([index_list])

Description

You can tell the optimizer to not consider a particular index with the IGNORE INDEX option.

The benefit of using IGNORE_INDEX instead of USE_INDEX is that it will not disable a new index which you may add later.

Also see Ignored Indexes for an option to specify in the index definition that indexes should be ignored.

Index Prefixes

When using index hints (USE, FORCE or IGNORE INDEX), the index name value can also be an unambiguous prefix of an index name.

Example

This is used after the table name in the FROM clause:

CREATE INDEX Name ON City (Name);
CREATE INDEX CountryCode ON City (Countrycode);
EXPLAIN SELECT Name FROM City IGNORE INDEX (Name)
WHERE name="Helsingborg" AND countrycode="SWE";

This produces:

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	City	ref	CountryCode	CountryCode	3	const	14	Using where

See Also

• See Index Hints: How to Force Query Plans for more details

• USE INDEX

• FORCE INDEX

• Ignored Indexes

_{This page is licensed: CC BY-SA / Gnu FDL}

Index Condition Pushdown is an optimization that is applied for access methods that access table data through indexes: range, ref, eq_ref, ref_or_null, and Batched Key Access.

The idea is to check part of the WHERE condition that refers to index fields (we call it Pushed Index Condition) as soon as we've accessed the index. If the Pushed Index Condition is not satisfied, we won't need to read the whole table record.

Index Condition Pushdown is on by default. To disable it, set its optimizer_switch flag like so:

SET optimizer_switch='index_condition_pushdown=off'

When Index Condition Pushdown is used, EXPLAIN will show "Using index condition":

MariaDB [test]> EXPLAIN SELECT * FROM tbl WHERE key_col1 BETWEEN 10 AND 11 AND key_col2 LIKE '%foo%';
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------+
| id | select_type | table | type  | possible_keys | key      | key_len | ref  | rows | Extra                 |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------+
|  1 | SIMPLE      | tbl   | range | key_col1      | key_col1 | 5       | NULL |    2 | Using index condition |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------+

The Idea Behind Index Condition Pushdown

In disk-based storage engines, making an index lookup is done in two steps, like shown on the picture:

Index Condition Pushdown optimization tries to cut down the number of full record reads by checking whether index records satisfy part of the WHERE condition that can be checked for them:

How much speed will be gained depends on

• How many records will be filtered out

• How expensive it was to read them

The former depends on the query and the dataset. The latter is generally bigger when table records are on disk and/or are big, especially when they have blobs.

Example Speedup

I used DBT-3 benchmark data, with scale factor=1. Since the benchmark defines very few indexes, we've added a multi-column index (index condition pushdown is usually useful with multi-column indexes: the first component(s) is what index access is done for, the subsequent have columns that we read and check conditions on).

ALTER TABLE lineitem ADD INDEX s_r (l_shipdate, l_receiptdate);

The query was to find big (l_quantity > 40) orders that were made in January 1993 that took more than 25 days to ship:

SELECT count(*) FROM lineitem
WHERE
  l_shipdate BETWEEN '1993-01-01' AND '1993-02-01' AND
  datediff(l_receiptdate,l_shipdate) > 25 AND
  l_quantity > 40;

EXPLAIN without Index Condition Pushdown:

-+----------+-------+----------------------+-----+---------+------+--------+-------------+
 | table    | type | possible_keys         | key | key_len | ref | rows    | Extra       |
-+----------+-------+----------------------+-----+---------+------+--------+-------------+
 | lineitem | range | s_r                  | s_r | 4       | NULL | 152064 | Using where |
-+----------+-------+----------------------+-----+---------+------+--------+-------------+

with Index Condition Pushdown:

-+-----------+-------+---------------+-----+---------+------+--------+------------------------------------+
 | table     | type | possible_keys | key | key_len | ref | rows     | Extra                              |
-+-----------+-------+---------------+-----+---------+------+--------+------------------------------------+
 | lineitem | range | s_r            | s_r | 4       | NULL | 152064 | Using index condition; Using where |
-+-----------+-------+---------------+-----+---------+------+--------+------------------------------------+

The speedup was:

• Cold buffer pool: from 5 min down to 1 min

• Hot buffer pool: from 0.19 sec down to 0.07 sec

Status Variables

There are two server status variables:

That way, the value Handler_icp_attempts - Handler_icp_match shows the number records that the server did not have to read because of Index Condition Pushdown.

Limitations

• Currently, virtual column indexes can't be used for index condition pushdown. Instead, a generated column can be made declared STORED. Then, index condition pushdown will be possible.

• Index Condition Pushdown can't be used with backward-ordered index scan. When the optimizer needs to execute an ORDER BY ... DESC query which can be handled by using a backward-ordered index scan, it will disable Index Condition Pushdown.

Partitioned Tables

Index condition pushdown support for partitioned tables was added in MariaDB 11.5.

_{This page is licensed: CC BY-SA / Gnu FDL}

The optimizer is largely cost-based and will try to choose the optimal plan for any query. However in some cases it does not have enough information to choose a perfect plan and in these cases you may have to provide hints to force the optimizer to use another plan.

You can examine the query plan for a SELECT by writing EXPLAIN before the statement. SHOW EXPLAIN shows the output of a running query. In some cases, its output can be closer to reality than EXPLAIN.

For the following queries, we will use the world database for the examples.

Setting up the World Example Database

Download it from world.sql.gz

Install it with:

mariadb-admin create world
zcat world.sql.gz | ../client/mysql world

or

mariadb-admin create world
gunzip world.sql.gz
../client/mysql world < world.sql

Forcing Join Order

You can force the join order by using STRAIGHT_JOIN either in the SELECT or JOIN part.

The simplest way to force the join order is to put the tables in the correct order in the FROM clause and use SELECT STRAIGHT_JOIN like so:

SELECT STRAIGHT_JOIN SUM(City.Population) FROM Country,City WHERE
City.CountryCode=Country.Code AND Country.HeadOfState="Volodymyr Zelenskyy";

If you only want to force the join order for a few tables, useSTRAIGHT_JOIN in the FROM clause. When this is done, only tables connected with STRAIGHT_JOIN will have their order forced. For example:

SELECT SUM(City.Population) FROM Country STRAIGHT_JOIN City WHERE
City.CountryCode=Country.Code AND Country.HeadOfState="Volodymyr Zelenskyy";

In both of the above cases Country will be scanned first and for each matching country (one in this case) all rows in City will be checked for a match. As there is only one matching country this will be faster than the original query.

The output of EXPLAIN for the above cases is:

This is one of the few cases where ALL is ok, as the scan of theCountry table will only find one matching row.

Forcing Usage of a Specific Index for the WHERE Clause

In some cases the optimizer may choose a non-optimal index or it may choose to not use an index at all, even if some index could theoretically be used.

In these cases you have the option to either tell the optimizer to only use a limited set of indexes, ignore one or more indexes, or force the usage of some particular index.

USE INDEX: Use a Limited Set of Indexes

You can limit which indexes are considered with the USE INDEX option.

USE INDEX [{FOR {JOIN|ORDER BY|GROUP BY}] ([index_list])

The default is 'FOR JOIN', which means that the hint only affects how theWHERE clause is optimized.

USE INDEX is used after the table name in the FROM clause.

Example:

CREATE INDEX Name ON City (Name);
CREATE INDEX CountryCode ON City (Countrycode);
EXPLAIN SELECT Name FROM City USE INDEX (CountryCode)
WHERE name="Helsingborg" AND countrycode="SWE";

This produces:

If we had not used USE INDEX, the Name index would have been inpossible keys.

IGNORE INDEX: Don't Use a Particular Index

You can tell the optimizer to not consider some particular index with the IGNORE INDEX option.

IGNORE INDEX [{FOR {JOIN|ORDER BY|GROUP BY}] ([index_list])

This is used after the table name in the FROM clause:

CREATE INDEX Name ON City (Name);
CREATE INDEX CountryCode ON City (Countrycode);
EXPLAIN SELECT Name FROM City IGNORE INDEX (Name)
WHERE name="Helsingborg" AND countrycode="SWE";

This produces:

The benefit of using IGNORE_INDEX instead of USE_INDEX is that it will not disable a new index which you may add later.

Also see Ignored Indexes for an option to specify in the index definition that indexes should be ignored.

FORCE INDEX: Forcing an Index

Forcing an index to be used is mostly useful when the optimizer decides to do a table scan even if you know that using an index would be better. (The optimizer could decide to do a table scan even if there is an available index when it believes that most or all rows will match and it can avoid the overhead of using the index).

CREATE INDEX Name ON City (Name);
EXPLAIN SELECT Name,CountryCode FROM City FORCE INDEX (Name)
WHERE name>="A" AND CountryCode >="A";

This produces:

FORCE_INDEX works by only considering the given indexes (like withUSE_INDEX) but in addition it tells the optimizer to regard a table scan as something very expensive. However if none of the 'forced' indexes can be used, then a table scan will be used anyway.

Index Prefixes

When using index hints (USE, FORCE or IGNORE INDEX), the index name value can also be an unambiguous prefix of an index name.

Forcing an Index to be Used for ORDER BY or GROUP BY

The optimizer will try to use indexes to resolve ORDER BY and GROUP BY.

You can use USE INDEX, IGNORE INDEX and FORCE INDEX as in the WHERE clause above to ensure that some specific index used:

USE INDEX [{FOR {JOIN|ORDER BY|GROUP BY}] ([index_list])

This is used after the table name in the FROM clause.

Example:

CREATE INDEX Name ON City (Name);
EXPLAIN SELECT Name,Count(*) FROM City
FORCE INDEX FOR GROUP BY (Name)
WHERE population >= 10000000 GROUP BY Name;

This produces:

Without the FORCE INDEX option we would have 'Using where; Using temporary; Using filesort' in the 'Extra' column, which means that the optimizer would created a temporary table and sort it.

Help the Optimizer Optimize GROUP BY and ORDER BY

The optimizer uses several strategies to optimize GROUP BY and ORDER BY:

• Resolve with an index:

  • Scan the table in index order and output data as we go. (This only works if the ORDER BY / GROUP BY can be resolved by an index after constant propagation is done).

• Filesort:

  • Scan the table to be sorted and collect the sort keys in a temporary file.

  • Sort the keys + reference to row (with filesort)

  • Scan the table in sorted order

• Use a temporary table for ORDER BY:

  • Create a temporary (in memory) table for the 'to-be-sorted' data. (If this gets bigger than max_heap_table_size or contains blobs then an Aria or MyISAM disk based table will be used)

  • Sort the keys + reference to row (with filesort)

  • Scan the table in sorted order

A temporary table will always be used if the fields which will be sorted are not from the first table in the JOIN order.

• Use a temporary table for GROUP BY:

  • Create a temporary table to hold the GROUP BY result with an index that matches the GROUP BY fields.

  • Produce a result row

  • If a row with the GROUP BY key exists in the temporary table, add the new result row to it. If not, create a new row.

  • Before sending the results to the user, sort the rows with filesort to get the results in the GROUP BY order.

Forcing/Disallowing TemporaryTables to be Used for GROUP BY:

Using an in-memory table (as described above) is usually the fastest option forGROUP BY if the result set is small. It is not optimal if the result set is very big. You can tell the optimizer this by usingSELECT SQL_SMALL_RESULT or SELECT SQL_BIG_RESULT.

For example:

EXPLAIN SELECT SQL_SMALL_RESULT Name,Count(*) AS Cities 
FROM City GROUP BY Name HAVING Cities > 2;

produces:

while:

EXPLAIN SELECT SQL_BIG_RESULT Name,Count(*) AS Cities 
FROM City GROUP BY Name HAVING Cities > 2;

produces:

The difference is that with SQL_SMALL_RESULT a temporary table is used.

Forcing Usage of Temporary Tables

In some cases you may want to force the use of a temporary table for the result to free up the table/row locks for the used tables as quickly as possible.

You can do this with the SQL_BUFFER_RESULT option:

CREATE INDEX Name ON City (Name);
EXPLAIN SELECT SQL_BUFFER_RESULT Name,Count(*) AS Cities FROM City
GROUP BY Name HAVING Cities > 2;

This produces:

Without SQL_BUFFER_RESULT, the above query would not use a temporary table for the result set.

Optimizer Switch

In MariaDB 5.3 we added an optimizer switch which allows you to specify which algorithms will be considered when optimizing a query.

See the optimizer section for more information about the different algorithms which are used.

See Also

• FORCE INDEX

• USE INDEX

• IGNORE INDEX

• GROUP BY

• Ignored Indexes

_{This page is licensed: CC BY-SA / Gnu FDL}

Prior to MariaDB 5.3, the index_merge access method supported union,sort-union, and intersection operations. Starting from MariaDB 5.3, thesort-intersection operation is also supported. This allows the use ofindex_merge in a broader number of cases.

This feature is disabled by default. To enable it, turn on the optimizer switch index_merge_sort_intersection like so:

SET optimizer_switch='index_merge_sort_intersection=on'

Limitations of index_merge/intersection

Prior to MariaDB 5.3, the index_merge access method had one intersection strategy called intersection. That strategy can only be used when merged index scans produced rowid-ordered streams. In practice this means that anintersection could only be constructed from equality (=) conditions.

For example, the following query will use intersection:

MySQL [ontime]> EXPLAIN SELECT AVG(arrdelay) FROM ontime WHERE depdel15=1 AND OriginState ='CA';
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+-------------------------------------------------+
|id|select_type|table |type       |possible_keys       |key                 |key_len|ref |rows |Extra                                            |
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+-------------------------------------------------+
| 1|SIMPLE     |ontime|index_merge|OriginState,DepDel15|OriginState,DepDel15|3,5    |NULL|76952|Using intersect(OriginState,DepDel15);Using where|
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+-------------------------------------------------+

but if you replace OriginState ='CA' with OriginState IN ('CA', 'GB') (which matches the same number of records), then intersection is not usable anymore:

MySQL [ontime]> explain select avg(arrdelay) from ontime where depdel15=1 and OriginState IN ('CA', 'GB');
+--+-----------+------+----+--------------------+--------+-------+-----+-----+-----------+
|id|select_type|table |type|possible_keys       |key     |key_len|ref  |rows |Extra      |
+--+-----------+------+----+--------------------+--------+-------+-----+-----+-----------+
| 1|SIMPLE     |ontime|ref |OriginState,DepDel15|DepDel15|5      |const|36926|Using where|
+--+-----------+------+----+--------------------+--------+-------+-----+-----+-----------+

The latter query would also run 5.x times slower (from 2.2 to 10.8 seconds) in our experiments.

How index_merge/sort_intersection improves the situation

In MariaDB 5.3, when index_merge_sort_intersection is enabled,index_merge intersection plans can be constructed from non-equality conditions:

MySQL [ontime]> explain select avg(arrdelay) from ontime where depdel15=1 and OriginState IN ('CA', 'GB');
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+--------------------------------------------------------+
|id|select_type|table |type       |possible_keys       |key                 |key_len|ref |rows |Extra                                                   |
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+--------------------------------------------------------+
| 1|SIMPLE     |ontime|index_merge|OriginState,DepDel15|DepDel15,OriginState|5,3    |NULL|60754|Using sort_intersect(DepDel15,OriginState); Using where |
+--+-----------+------+-----------+--------------------+--------------------+-------+----+-----+--------------------------------------------------------+

In our tests, this query ran in 3.2 seconds, which is not as good as the case with two equalities, but still much better than 10.8 seconds we were getting without sort_intersect.

The sort_intersect strategy has higher overhead than intersect but is able to handle a broader set of WHERE conditions.

When to Use

index_merge/sort_intersection works best on tables with lots of records and where intersections are sufficiently large (but still small enough to make a full table scan overkill).

The benefit is expected to be bigger for io-bound loads.

_{This page is licensed: CC BY-SA / Gnu FDL}

Syntax

SELECT ... FROM ... WHERE ...
[group_clause] [order_clause]
LIMIT [[OFFSET,] row_count] ROWS EXAMINED rows_limit;

Similar to the parameters of LIMIT, rows_limit can be both a prepared statement parameter, or a stored program parameter.

Description

The purpose of this optimization is to provide the means to terminate the execution of SELECT statements which examine too many rows, and thus use too many resources. This is achieved through an extension of the LIMIT clause —LIMIT ROWS EXAMINED number_of_rows. Whenever possible the semantics of LIMIT ROWS EXAMINED is the same as that of normal LIMIT (for instance for aggregate functions).

The LIMIT ROWS EXAMINED clause is taken into account by the query engine only during query execution. Thus the clause is ignored in the following cases:

• If a query is EXPLAIN-ed.

• During query optimization.

• During auxiliary operations such as writing to system tables (e.g. logs).

The clause is not applicable to DELETE or UPDATE statements, and if used in those statements produces a syntax error.

The effects of this clause are as follows:

• The server counts the number of read, inserted, modified, and deleted rows during query execution. This takes into account the use of temporary tables, and sorting for intermediate query operations.

• Once the counter exceeds the value specified in the LIMIT ROWS EXAMINED clause, query execution is terminated as soon as possible.

• The effects of terminating the query because of LIMIT ROWS EXAMINED are as follows:

  • The result of the query is a subset of the complete query, depending on when the query engine detected that the limit was reached. The result may be empty if no result rows could be computed before reaching the limit.

  • A warning is generated of the form: "Query execution was interrupted. The query examined at least 100 rows, which exceeds LIMIT ROWS EXAMINED (20). The query result may be incomplete."

  • If query processing was interrupted during filesort, an error is returned in addition to the warning.

  • If a UNION was interrupted during execution of one of its queries, the last step of the UNION is still executed in order to produce a partial result.

  • Depending on the join and other execution strategies used for a query, the same query may produce no result at all, or a different subset of the complete result when terminated due to LIMIT ROWS EXAMINED.

  • If the query contains a GROUP BY clause, the last group where the limit was reached will be discarded.

The LIMIT ROWS EXAMINED clause cannot be specified on a per-subquery basis. There can be only one LIMIT ROWS EXAMINED clause for the whole SELECT statement. If a SELECT statement contains several subqueries with LIMIT ROWS EXAMINED, the one that is parsed last is taken into account.

Examples

A simple example of the clause is:

SELECT * FROM t1, t2 LIMIT 10 ROWS EXAMINED 10000;

The LIMIT ROWS EXAMINED clause is global for the whole statement.

If a composite query (such as UNION, or query with derived tables or with subqueries) contains more than one LIMIT ROWS EXAMINED, the last one parsed is taken into account. In this manner either the last or the outermost one is taken into account. For instance, in the query:

SELECT * FROM t1
WHERE c1 IN (SELECT * FROM t2 WHERE c2 > ' ' LIMIT ROWS EXAMINED 0)
LIMIT ROWS EXAMINED 11;

The limit that is taken into account is 11, not 0.

_{This page is licensed: CC BY-SA / Gnu FDL}

MariaDB 5.3 has an optimizer debugging patch. The patch is pushed into:

lp:maria-captains/maria/5.3-optimizer-debugging

The patch is wrapped in #ifdef, but there is a #define straight in mysql_priv.h so simply compiling that tree should produce a binary with optimizer debugging enabled.

The patch adds two system variables:

• @@debug_optimizer_prefer_join_prefix

• @@debug_optimizer_dupsweedout_penalized

the variables are present as session/global variables, and are also settable via the server command line.

debug_optimizer_prefer_join_prefix

If this variable is non-NULL, it is assumed to specify a join prefix as a comma-separated list of table aliases:

SET debug_optimizer_prefer_join_prefix='tbl1,tbl2,tbl3';

The optimizer will try its best to build a join plan which matches the specified join prefix. It does this by comparing join prefixes it is considering with @@debug_optimizer_prefer_join_prefix, and multiplying cost by a million if the plan doesn't match the prefix.

As a result, you can more-or-less control the join order. For example, let's take this query:

MariaDB [test]> EXPLAIN SELECT * FROM ten A, ten B, ten C;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                              |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
|  1 | SIMPLE      | A     | ALL  | NULL          | NULL | NULL    | NULL |   10 |                                    |
|  1 | SIMPLE      | B     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using join buffer (flat, BNL join) |
|  1 | SIMPLE      | C     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using join buffer (flat, BNL join) |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
3 rows in set (0.00 sec)

and request a join order of C,A,B:

MariaDB [test]> SET debug_optimizer_prefer_join_prefix='C,A,B';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> EXPLAIN SELECT * FROM ten A, ten B, ten C;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                              |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
|  1 | SIMPLE      | C     | ALL  | NULL          | NULL | NULL    | NULL |   10 |                                    |
|  1 | SIMPLE      | A     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using join buffer (flat, BNL join) |
|  1 | SIMPLE      | B     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using join buffer (flat, BNL join) |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------+
3 rows in set (0.00 sec)

We got it.

Note that this is still a best-effort approach:

• you won't be successful in forcing join orders which the optimizer considers invalid (e.g. for "t1 LEFT JOIN t2" you won't be able to get a join order of t2,t1).

• The optimizer does various plan pruning and may discard the requested join order before it has a chance to find out that it is a million-times cheaper than any other.

Semi-joins

It is possible to force the join order of joins plus semi-joins. This may cause a different strategy to be used:

MariaDB [test]> SET debug_optimizer_prefer_join_prefix=NULL;
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> EXPLAIN SELECT * FROM ten A WHERE a IN (SELECT B.a FROM ten B, ten C WHERE C.a + A.a < 4);
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                      |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
|  1 | PRIMARY     | A     | ALL  | NULL          | NULL | NULL    | NULL |   10 |                            |
|  1 | PRIMARY     | B     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using where                |
|  1 | PRIMARY     | C     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using where; FirstMatch(A) |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
3 rows in set (0.00 sec)

MariaDB [test]> SET debug_optimizer_prefer_join_prefix='C,A,B';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> EXPLAIN SELECT * FROM ten A WHERE a IN (SELECT B.a FROM ten B, ten C WHERE C.a + A.a < 4);
+----+-------------+-------+------+---------------+------+---------+------+------+-------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                           |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------------------------------------------+
|  1 | PRIMARY     | C     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Start temporary                                 |
|  1 | PRIMARY     | A     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using where; Using join buffer (flat, BNL join) |
|  1 | PRIMARY     | B     | ALL  | NULL          | NULL | NULL    | NULL |   10 | Using where; End temporary                      |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------------------------------------------+
3 rows in set (0.00 sec)

Semi-join materialization is a somewhat special case, because "join prefix" is not exactly what you see in the EXPLAIN output. For semi-join materialization:

• don't put "<subqueryN>" into @@debug_optimizer_prefer_join_prefix

• instead, put all of the materialization tables into the place where you want the <subqueryN> line.

• Attempts to control the join order inside the materialization nest will be unsuccessful. Example: we want A-C-B-AA:

MariaDB [test]> SET debug_optimizer_prefer_join_prefix='A,C,B,AA';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> EXPLAIN SELECT * FROM ten A, ten AA WHERE A.a IN (SELECT B.a FROM ten B, ten C);
+----+-------------+-------------+--------+---------------+--------------+---------+------+------+------------------------------------+
| id | select_type | table       | type   | possible_keys | key          | key_len | ref  | rows | Extra                              |
+----+-------------+-------------+--------+---------------+--------------+---------+------+------+------------------------------------+
|  1 | PRIMARY     | A           | ALL    | NULL          | NULL         | NULL    | NULL |   10 |                                    |
|  1 | PRIMARY     | <subquery2> | eq_ref | distinct_key  | distinct_key | 5       | func |    1 |                                    |
|  1 | PRIMARY     | AA          | ALL    | NULL          | NULL         | NULL    | NULL |   10 | Using join buffer (flat, BNL join) |
|  2 | SUBQUERY    | B           | ALL    | NULL          | NULL         | NULL    | NULL |   10 |                                    |
|  2 | SUBQUERY    | C           | ALL    | NULL          | NULL         | NULL    | NULL |   10 |                                    |
+----+-------------+-------------+--------+---------------+--------------+---------+------+------+------------------------------------+
5 rows in set (0.00 sec)

but we get A-B-C-AA.

debug_optimizer_dupsweedout_penalized

There are four semi-join execution strategies:

1. FirstMatch

2. Materialization

3. LooseScan

4. DuplicateWeedout

The first three strategies have flags in @@optimizer_switch that can be used to disable them. The DuplicateWeedout strategy does not have a flag. This was done for a reason, as that strategy is the catch-all strategy and it can handle all kinds of subqueries, in all kinds of join orders. (We're slowly moving to the point where it will be possible to run with FirstMatch enabled and everything else disabled but we are not there yet.)

Since DuplicateWeedout cannot be disabled, there are cases where it "gets in the way" by being chosen over the strategy you need. This is whatdebug_optimizer_dupsweedout_penalized is for. if you set:

MariaDB [test]> SET debug_optimizer_dupsweedout_penalized=TRUE;

...the costs of query plans that use DuplicateWeedout will be multiplied by a millon. This doesn't mean that you will get rid of DuplicateWeedout — due to Bug #898747 it is still possible to have DuplicateWeedout used even if a cheaper plan exits. A partial remedy to this is to run with

MariaDB [test]> SET optimizer_prune_level=0;

It is possible to use both debug_optimizer_dupsweedout_penalized and debug_optimizer_prefer_join_prefix at the same time. This should give you the desired strategy and join order.

Further reading

• See mysql-test/t/debug_optimizer.test (in the MariaDB source code) for examples

_{This page is licensed: CC BY-SA / Gnu FDL}

The NOT NULL range scan optimization enables the optimizer to construct range scans from NOT NULL conditions that it was able to infer from the WHERE clause.

The optimization appeared in MariaDB 10.5.0. It is not enabled by default; one needs to set an optimizer_switch flag to enable it.

Description

A basic (but slightly artificial) example:

CREATE TABLE items (
  price  DECIMAL(8,2),
  weight DECIMAL(8,2),
  ...
  INDEX(weight)
);

-- Find items that cost more than 1000 $currency_units per kg:
SET optimizer_switch='not_null_range_scan=ON';
EXPLAIN
SELECT * FROM items WHERE items.price > items.weight / 1000;

The WHERE condition in this form cannot be used for range scans. However, one can infer that it will reject rows that NULL for weight. That is, infer an additional condition that

weight IS NOT NULL

and pass it to the range optimizer. The range optimizer can, in turn, evaluate whether it makes sense to construct range access from the condition:

+------+-------------+-------+-------+---------------+--------+---------+------+------+-------------+
| id   | select_type | table | type  | possible_keys | key    | key_len | ref  | rows | Extra       |
+------+-------------+-------+-------+---------------+--------+---------+------+------+-------------+
|    1 | SIMPLE      | items | range | NULL          | weight | 5       | NULL | 1    | Using where |
+------+-------------+-------+-------+---------------+--------+---------+------+------+-------------+

Here's another example that's more complex but is based on a real-world query. Consider a join query

-- Find orders that were returned
SELECT * FROM current_orders AS O, order_returns AS RET
WHERE 
  O.return_id= RET.id;

Here, the optimizer can infer the condition "return_id IS NOT NULL". If most of the orders are not returned (and so have NULL for return_id), one can use range access to scan only those orders that had a return.

Controlling the Optimization

The optimization is not enabled by default. One can enable it like so

SET optimizer_switch='not_null_range_scan=ON';

Optimizer Trace

TODO.

See Also

• MDEV-15777 - JIRA bug report which resulted in the optimization

• NULL Filtering Optimization is a related optimization in MySQL and MariaDB. It uses inferred NOT NULL conditions to perform filtering (but not index access)

_{This page is licensed: CC BY-SA / Gnu FDL}

optimizer_switch is a server variable that one can use to enable/disable specific optimizations.

Syntax

To set or unset the various optimizations, use the following syntax:

SET [GLOBAL|SESSION] optimizer_switch='cmd[,cmd]...';

The cmd takes the following format:

There is no need to list all flags - only those that are specified in the command will be affected.

Available Flags

Below is a list of all optimizer_switch flags available in MariaDB:

1. ↑ replaced split_grouping_derived, introduced in MariaDB 10.3.1

Defaults

See Also

• Quickly finding optimizer_switch values that are on or off

• The optimizer converts certain big IN predicates into IN subqueries

• optimizer_adjust_secondary_key_cost

• Optimizer hints in SELECT

_{This page is licensed: CC BY-SA / Gnu FDL}

optimizer_adjust_secondary_key_costs

• Description: Gives the user the ability to affect how the costs for secondary keys using ref are calculated in the few cases when MariaDB 10.6 up to MariaDB 10.11 makes a sub-optimal choice when optimizing ref access, either for key lookups or GROUP BY. ref, as used by EXPLAIN, means that the optimizer is using key-lookup on one value to find the matching rows from a table. Unused from MariaDB 11.0. In MariaDB 10.6.18 the variable was changed from a number to a set of strings and disable_forced_index_in_group_by (value 4) was added.

• Scope: Global, Session

• Dynamic: Yes

• Data Type: set

• Default Value: fix_reuse_range_for_ref, fix_card_multiplier

• Range: 0 to 63 or any combination of adjust_secondary_key_cost, disable_max_seek or disable_forced_index_in_group_by, fix_innodb_cardinality,fix_reuse_range_for_ref, fix_card_multiplier

• Introduced: MariaDB 10.6.17, MariaDB 10.11.7

MariaDB [securedb]> select @@version;
+-----------------------------------+
| @@version             |
+-----------------------------------+
| 10.6.20-16-MariaDB-enterprise-log |
+-----------------------------------+
1 row in set (0.001 sec)

MariaDB [securedb]> select @@optimizer_adjust_secondary_key_costs;
+---------------------------------------------+
| @@optimizer_adjust_secondary_key_costs   |
+---------------------------------------------+
| fix_reuse_range_for_ref,fix_card_multiplier |
+---------------------------------------------+

MariaDB starting with 11.0

optimizer_adjust_secondary_key_costs will be obsolete starting from MariaDB 11.0 as the new optimizer in 11.0 does not have max_seek optimization and is already using cost based choices for index usage with GROUP BY.

The value for optimizer_adjust_secondary_key_costs is one of more of the following:

One can set all options with:

SET @@optimizer_adjust_secondary_key_costs='all';

Explanations of the old behavior in MariaDB 10.x

The reason for the max_seek optimization was originally to ensure that MariaDB would use a key instead of a table scan. This works well for a lot of queries, but can cause problems when a table scan is a better choice, such as when one would have to scan more than 1/4 of the rows in the table (in which case a table scan is better).

See Also

• The optimizer_switch system variable.

_{This page is licensed: CC BY-SA / Gnu FDL}

Basics

Off (0) by default, when enabling this optimization, MariaDB will consider a join order that may shorten query execution time based on the ORDER BY ... LIMIT n clause. For small values of n, this may improve performance.

Set the value of optimizer_join_limit_pref_ratio to a non-zero value to enable this option (higher values are more conservative, recommended value is 100), or set to 0 (the default value) to disable it.

Detailed description

Problem setting

By default, the MariaDB optimizer picks a join order without considering the ORDER BY ... LIMIT clause, when present.

For example, consider a query looking at latest 10 orders together with customers who made them:

SELECT *
FROM
  customer,ORDER
WHERE
  customer.name=ORDER.customer_name
ORDER BY
  ORDER.DATE DESC
LIMIT 10

The two possible plans are:customer->orders:

+------+-------------+----------+------+---------------+---------------+---------+---------------+------+----------------------------------------------+
| id   | select_type | table    | type | possible_keys | key           | key_len | ref           | rows | Extra                                        |
+------+-------------+----------+------+---------------+---------------+---------+---------------+------+----------------------------------------------+
|    1 | SIMPLE      | customer | ALL  | name          | NULL          | NULL    | NULL          | 9623 | Using where; Using temporary; Using filesort |
|    1 | SIMPLE      | orders   | ref  | customer_name | customer_name | 103     | customer.name | 1    |                                              |
+------+-------------+----------+------+---------------+---------------+---------+---------------+------+----------------------------------------------+

and orders->customer:

+------+-------------+----------+-------+---------------+------------+---------+----------------------+------+-------------+
| id   | select_type | table    | type  | possible_keys | key        | key_len | ref                  | rows | Extra       |
+------+-------------+----------+-------+---------------+------------+---------+----------------------+------+-------------+
|    1 | SIMPLE      | orders   | index | customer_name | order_date | 4       | NULL                 | 10   | Using where |
|    1 | SIMPLE      | customer | ref   | name          | name       | 103     | orders.customer_name | 1    |             |
+------+-------------+----------+-------+---------------+------------+---------+----------------------+------+-------------+

The customer->orders plan computes a join between all customers and orders, saves that result into a temporary table, and then uses filesort to get the 10 most recent orders. This query plan doesn't benefit from the fact that just 10 orders are needed.

However, in contrast, the orders->customers plan uses an index to read rows in the ORDER BY order. The query can stop execution once it finds 10 order-and-customer combinations. This is much faster than computing the entire join. Under this plan, and when this new optimization, we can leverage ORDER BY ... LIMIT to stop early, when we have the 10 combinations.

Plans with LIMIT shortcuts are difficult to estimate

It is fundamentally difficult to produce a reliable estimate for ORDER BY ... LIMIT shortcuts. Let's take an example from the previous section to see why. This query searches for last 10 orders that were shipped by air:

SELECT *
FROM
  customer,ORDER
WHERE
  customer.name=ORDER.customer_name 
  AND ORDER.shipping_method='Airplane'
ORDER BY
  ORDER.DATE DESC
LIMIT 10

Suppose we know beforehand that 50% of orders are shipped by air. Assuming there's no correlation between date and shipping method, orders->customer plan will need to scan 20 orders before we find 10 that are shipped by air. But if there is correlation, then we may need to scan up to (total_orders*0.5 + 10) before we find first 10 orders that are shipped by air. Scanning about 50% of all orders can be expensive.

This situation worsens when the query has constructs whose selectivity is not known. For example, suppose the WHERE condition was

order.shipping_method='%Airplane%'

in this case, we can't reliably say whether we will be able to stop after scanning #LIMIT rows or we will need to enumerate all rows before we find #LIMIT matches.

Providing guidelines to the optimizer

Due to these challenges, the optimization is not enabled by default.

When running a mostly OLTP workload such that query WHERE conditions have suitable indexes or are not very selective, then any ORDER BY ... LIMIT queries will typically find matching rows quickly. In this case, it makes sense to give the following guidance to the optimizer:

Do consider the query plan using LIMIT short-cutting 
and prefer it if it promises at least X times speedup.

The value of X is given to the optimizer via optimizer_join_limit_pref_ratio setting. Higher values carry less risk. The recommended value is 100: prefer the LIMIT join order if it promises at least 100x speedup.

References

• MDEV-34720 introduces optimizer_join_limit_pref_ratio optimization

• MDEV-18079 is about future development that would make the optimizer handle such cases without user guidance.

_{This page is licensed: CC BY-SA / Gnu FDL}

The problem space

Let's say you have "news articles" (rows in a table) and want a web page showing the latest ten articles about a particular topic.

Variants on "topic":

• Category

• Tag

• Provider (of news article)

• Manufacturer (of item for sale)

• Ticker (financial stock)

Variants on "news article"

• Item for sale

• Blog comment

• Blog thread

Variants on "latest"

• Publication date (unix_timestamp)

• Most popular (keep the count)

• Most emailed (keep the count)

• Manual ranking (1..10 -- 'top ten')

Variants on "10" - there is nothing sacred about "10" in this discussion.

The performance issues

Currently you have a table (or a column) that relates the topic to the article. The SELECT statement to find the latest 10 articles has grown in complexity, and performance is poor. You have focused on what index to add, but nothing seems to work.

• If there are multiple topics for each article, you need a many-to-many table.

• You have a flag "is_deleted" that needs filtering on.

• You want to "paginate" the list (ten articles per page, for as many pages as necessary).

The solution

First, let me give you the solution, then I will elaborate on why it works well.

• One new table called, say, Lists.

• Lists has exactly 3 columns: topic, article_id, sequence

• Lists has exactly 2 indexes: PRIMARY KEY(topic, sequence, article_id), INDEX(article_id)

• Only viewable articles are in Lists. (This avoids the filtering on "is_deleted", etc)

• Lists is InnoDB. (This gets "clustering".)

• "sequence" is typically the date of the article, but could be some other ordering.

• "topic" should probably be normalized, but that is not critical to this discussion.

• "article_id" is a link to the bulky row in another table(s) that provide all the details about the article.

The queries

Find the latest 10 articles for a topic:

SELECT  a.*
    FROM  Articles a
    JOIN  Lists s ON s.article_id = a.article_id
    WHERE  s.topic = ?
    ORDER BY  s.sequence DESC
    LIMIT  10;

You must not have any WHERE condition touching columns in Articles.

When you mark an article for deletion; you must remove it from Lists:

DELETE  FROM  Lists
    WHERE  article_id = ?;

I emphasize "must" because flags and other filtering is often the root of performance issues.

Why it works

By now, you may have discovered why it works.

The big goal is to minimize the disk hits. Let's itemize how few disk hits are needed. When finding the latest articles with 'normal' code, you will probably find that it is doing significant scans of the Articles table, failing to quickly home in on the 10 rows you want. With this design, there is only one extra disk hit:

• 1 disk hit: 10 adjacent, narrow, rows in Lists -- probably in a single "block".

• 10 disk hits: The 10 articles. (These hits are unavoidable, but may be cached.) The PRIMARY KEY, and using InnoDB, makes these quite efficient.

OK, you pay for this by removing things that you should avoid.

• 1 disk hit: INDEX(article_id) - finding a few ids

• A few more disk hits to DELETE rows from Lists. This is a small price to pay -- and you are not paying it while the user is waiting for the page to render.

See also

Rick James graciously allowed us to use this article in the documentation.

Rick James' site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: lists

_{This page is licensed: CC BY-SA / Gnu FDL}

The Desire

You have a website with news articles, or a blog, or some other thing with a list of things that might be too long for a single page. So, you decide to break it into chunks of, say, 10 items and provide a [Next] button to go the next "page".

You spot OFFSET and LIMIT in MariaDB and decide that is the obvious way to do it.

SELECT  *
        FROM  items
        WHERE  messy_filtering
        ORDER BY  date DESC
        OFFSET  $M  LIMIT $N

Note that the problem requirement needs a [Next] link on each page so that the user can 'page' through the data. He does not really need "GoTo Page #". Jump to the [First] or [Last] page may be useful.

The Problem

All is well -- until you have 50,000 items in a list. And someone tries to walk through all 5000 pages. That 'someone' could be a search engine crawler.

Where's the problem? Performance. Your web page is doing "SELECT ... OFFSET 49990 LIMIT 10" (or the equivalent "LIMIT 49990,10"). MariaDB has to find all 50,000 rows, step over the first 49,990, then deliver the 10 for that distant page.

If it is a crawler ('spider') that read all the pages, then it actually touched about 125,000,000 items to read all 5,000 pages.

Reading the entire table, just to get a distant page, can be so much I/O that it can cause timeouts on the web page. Or it can interfere with other activity, causing other things to be slow.

Other Bugs

In addition to a performance problem, ...

• If an item is inserted or deleted between the time you look at one page and the next, you could miss an item, or see an item duplicated.

• The pages are not easily bookmarked or sent to someone else because the contents shift over time.

• The WHERE clause and the ORDER BY may even make it so that all 50,000 items have to be read, just to find the 10 items for page 1!

What to Do?

Hardware? No, that's just a bandaid. The data will continue to grow and even the new hardware won't handle it.

Better INDEX? No. You must get away from reading the entire table to get the 5000th page.

Build another table saying where the pages start? Get real! That would be a maintenance nightmare, and expensive.

Bottom line: Don't use OFFSET; instead remember where you "left off".

# First page (latest 10 items):
    SELECT ... WHERE ... ORDER BY id DESC LIMIT 10
# Next page (second 10):
    SELECT ... WHERE ... AND id < $left_off ORDER BY id DESC LIMIT 10

With INDEX(id), this suddenly becomes very efficient.

Implementation -- Getting Rid of OFFSET

You are probably doing this now: ORDER BY datetime DESC LIMIT 49990,10 You probably have some unique id on the table. This can probably be used for "left off".

Currently, the [Next] button probably has a url something like ?topic=xyz&page=4999&limit=10 The 'topic' (or 'tag' or 'provider' or 'user' or etc) says which set of items are being displayed. The product of page*limit gives the OFFSET. (The "limit=10" might be in the url, or might be hard-coded; this choice is not relevant to this discussion.)

The new variant would be ?topic=xyz&id=12345&limit=10. (Note: the 12345 is not computable from 4999.) By using INDEX(topic, id) you can efficiently say

WHERE topic = 'xyz'
      AND id >= 1234
    ORDER BY id
    LIMIT 10