MySQL Presentations: Some Algorithms Used by MySQL

Some algorithms used by MySQL

Table handlers
Benefits of using MyISAM tables
Benefits of using Berkeley DB (BDB) tables
How SELECT works
The query optimizer
New DISTINCT optimization

Table handlers

All access to the data goes through a well defined table handler interface. This gives MySQL the benefit of having many very different backends with different characteristic:

Type	Comment
ISAM	The old table format
MyISAM	The new table format that is based on ISAM but optimized for SQL
MERGE	A UNION view over many identical MyISAM tables
HEAP	Tables in memory
BDB	Berkeley DB transactional table format

Table representation

In MySQL a database is represented by a directory and tables as files
The table definition is stored in a separate file (table_name.frm) and depending on the table handler the index and data may be stored in 0, 1 or 2 other files.
This makes it easy to copy, move, backup or delete databases with system utilities.
Having different files for each table reduces the possibility for table corruption to spread from one crashed table to others.

MyISAM tables

Based on the old reliable B-tree ISAM table format.
OS and architecture independent; Easy to copy data between platforms.
Doesn't support transactions.
The data is stored in a .MYD file and all index are stored in a .MYI file.
Supports fixed record and dynamic record formats.
Very compact data representation; No need to allocate extra space while running an update.
Scanning data is fast as we can use sequential reads.
Scanning on index is fast is the index doesn't contain data.
All indexes are equally fast.
Table locks.
Tables can be checked, repaired and optimized with the standalone tool myisamchk.
One can use the SQL commands CHECK, REPAIR, OPTIMIZE and ANALYZE on MyISAM tables.
ANALYZE updates the cardinality for each index which helps the optimizer to decide which index to use.

Berkeley DB tables

New table format in MySQL 3.23.15.
The MySQL / Berkeley interface is still not tested by a large user base.
Berkeley DB tables are coded and maintained by Sleepycat.
Berkeley DB has been around a long time, is widely used and known to be very scalable and very robust.
The data and index are stored in a .db file.
Supports internally fixed record and dynamic record formats, but currently MySQL is only using the dynamic record format.
Table scanning is slower than for MyISAM files.
The primary key is much faster than other keys.
Fast if one searches on columns that is only part of one key + the primary key.
One should never have to check or repair the tables.
Page locks or table locks.
One can optimize a table with ALTER TABLE.
We will put up a speed comparison between MySQL tables and Berkeley DB tables on www.mysql.com soon.
We are working with Sleepycat to even more optimization to the MySQL / Berkeley DB interface.

How SELECT works

Find one table to scan and use the other tables as lookup tables.
If we are using GROUP BY either sort the table according to GROUP BY or create a temporary table with the GROUP BY as a unique key.
If we are using an GROUP BY or ORDER BY on expressions that are not part of the first table then create a temporary table for the result.

The query optimizer stages

The range optimizer finds out which keys to use.
The join optimizer finds out in which order to read the tables.
Read all tables which only one matching row.
Join the rest of the tables in one pass.

The range optimizer

Estimates how many rows will be found within a set of given ranges. The following examples assumes we have defined an index over (k1,k2).

SELECT * FROM a WHERE k1=1	k1=1
SELECT * FROM a WHERE k1>=1 AND k1 <= 10 AND OS='Linux'	1<= k1 <= 10
SELECT * FROM a WHERE k1>=1 AND k1 <= 10 OR k1 > 5 and k1 <20	1<= k1 < 20
SELECT * FROM a WHERE k1 IN (1,2) AND k2 = 10 OR k1 > 10	(k1,k2) = (1,10) OR (k1,k2) = (2,10) OR k1 > 10
SELECT * FROM a WHERE k1>=1 and k1 <= 10 and k2>=1 and k2<=10	(1,1) <= (k1,k2) <= (10,10)

The join optimizer

Tries all table combinations to minimize the number of rows to read.
Uses the key distribution (from ANALYZE TABLE) to estimate how many rows will be matched.
If the key distribution is not updated, assume that the matching rows are proportional to the size difference between the tables.
EXPLAIN shows the result from the join optimizer.

The different join types

system	Table has only one row
const	At most one row to be read
eq_ref	Read by unique key
ref	Read by not unique key or by key part
range	Read rows within a key range
index	Scan the index tree
ALL	Scan the data file

Learn to use EXPLAIN

Use EXPLAIN on every query that you think is too slow!

mysql> explain select t3.DateOfAction, t1.TransactionID
    -> from t1 join t2 join t3
    -> where t2.ID = t1.TransactionID and t3.ID = t2.GroupID
    -> order by t3.DateOfAction, t1.TransactionID;
+-------+--------+---------------+---------+---------+------------------+------+---------------------------------+
| table | type   | possible_keys | key     | key_len | ref              | rows | Extra                           |
+-------+--------+---------------+---------+---------+------------------+------+---------------------------------+
| t1    | ALL    | NULL          | NULL    |    NULL | NULL             |   11 | Using temporary; Using filesort |
| t2    | ref    | ID            | ID      |       4 | t1.TransactionID |   13 |                                 |
| t3    | eq_ref | PRIMARY       | PRIMARY |       4 | t2.GroupID       |    1 |                                 |
+-------+--------+---------------+---------+---------+------------------+------+---------------------------------+

New DISTINCT optimization

Here is a typical query used by one of our users:

SELECT distinct resume_main.server_id,
                resume_main.resume_id,
                date_format(resume_main.incoming,"%d.%m.%Y") as incoming,
                WEEKDAY(resume_main.incoming) as weekday,
                resume_main.title
                FROM resume_main,
resume_region,
resume_language_skills,
resume_profession,
resume_industry
WHERE resume_main.appkind = 1
 AND resume_main.language_id = 2
 AND resume_region.region_id = 220
 AND resume_main.resume_id = resume_region.resume_id
                  AND resume_main.server_id = resume_region.server_id
 AND resume_main.experience_profession = 3
 AND resume_language_skills.language_id = 2
 AND resume_main.resume_id = resume_language_skills.resume_id
                  AND resume_main.server_id = resume_language_skills.server_id
 AND resume_profession.profession_id in (2,59)
 AND resume_main.resume_id = resume_profession.resume_id
                  AND resume_main.server_id = resume_profession.server_id
 AND resume_industry.industry in (30,29)
 AND resume_main.resume_id = resume_industry.resume_id
                  AND resume_main.server_id = resume_industry.server_id
 AND resume_main.incoming >= FROM_UNIXTIME(967759200)
 ORDER BY resume_main.incoming LIMIT 75,25;

How the query is optimized

Create a temporary HEAP table with an unique key on the selected expressions.
Scan the resume_main table based on the best available key.
Use key lookups on the other tables.
When we find the first matching row combination, write the row to the temporary table, ignoring duplicate key errors.
Don't read more rows from the lookup tables as they can't create a new distinct key.
Read the next row from the resume_main table.
Repeat the above steps until all matching rows are found.
Sort the temporary table until the 100 first rows are sorted.
Return the result to the client.