User:Catrope/SQL talk
Indexes (AKA keys)
[edit]mysql> SHOW CREATE TABLE page; [snip] | page | CREATE TABLE `page` ( `page_id` int(8) unsigned NOT NULL AUTO_INCREMENT, `page_namespace` int(11) NOT NULL DEFAULT '0', `page_title` varbinary(255) NOT NULL DEFAULT '', `page_restrictions` tinyblob NOT NULL, `page_counter` bigint(20) unsigned NOT NULL DEFAULT '0', `page_is_redirect` tinyint(1) unsigned NOT NULL DEFAULT '0', `page_is_new` tinyint(1) unsigned NOT NULL DEFAULT '0', `page_random` double unsigned NOT NULL DEFAULT '0', `page_touched` varbinary(14) NOT NULL DEFAULT '', `page_latest` int(8) unsigned NOT NULL DEFAULT '0', `page_len` int(8) unsigned NOT NULL DEFAULT '0', PRIMARY KEY (`page_id`), UNIQUE KEY `name_title` (`page_namespace`,`page_title`), KEY `page_random` (`page_random`), KEY `page_len` (`page_len`), KEY `page_redirect_namespace_len` (`page_is_redirect`,`page_namespace`,`page_len`) ) ENGINE=InnoDB AUTO_INCREMENT=35610364 DEFAULT CHARSET=binary |
Index on a single field
[edit]ORDER BY without index
[edit]mysql> EXPLAIN SELECT * FROM page ORDER BY page_touched LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | 1 | SIMPLE | page | ALL | NULL | NULL | NULL | NULL | 26647370 | Using filesort | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ 1 row in set (0.00 sec)
Bad signs:
- type=ALL: full table scan
- key=NULL: no index used
- Using filesort
Query execution:
- Retrieve all 26M rows
- Sort them by page_touched
- Return first 10
ORDER BY with index
[edit]mysql> EXPLAIN SELECT * FROM page ORDER BY page_len LIMIT 10; +----+-------------+-------+-------+---------------+----------+---------+------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+----------+---------+------+------+-------+ | 1 | SIMPLE | page | index | NULL | page_len | 4 | NULL | 10 | | +----+-------------+-------+-------+---------------+----------+---------+------+------+-------+ 1 row in set (0.00 sec)
Filesort is gone, type=index, key=page_len, and rows=10
Query execution:
- Look at page_len index (pre-sorted list of row pointers ordered by page_len)
- Grab 10 row pointers off the top
- Retrieve those rows and return them
WHERE without index
[edit]mysql> EXPLAIN SELECT * FROM page WHERE page_is_new=0 LIMIT 1; +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ | 1 | SIMPLE | page | ALL | NULL | NULL | NULL | NULL | 26647485 | Using where | +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ 1 row in set (0.00 sec)
Query execution:
- Iterate over all rows, in any order
- For each row:
- If page_namespace=0, return row and stop
- If not, continue to next row
- If no rows match, return empty result
Worst case: no rows match, entire table is scanned
WHERE with index
[edit]mysql> EXPLAIN SELECT * FROM page WHERE page_id=12345 LIMIT 1; +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ | 1 | SIMPLE | page | const | PRIMARY | PRIMARY | 4 | const | 1 | | +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ 1 row in set (0.00 sec)
Seeing const is usually good
Query execution:
- Use binary search to find the row with page_id=12345
- This scans at most 1+log(26M) = 27 rows
- If found, return the row, otherwise return an empty result
WHERE .. LIMIT N
[edit]mysql> EXPLAIN SELECT * FROM page WHERE page_id >= 12345 ORDER BY page_id LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+----------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+----------+-------------+ | 1 | SIMPLE | page | range | PRIMARY | PRIMARY | 4 | NULL | 13323844 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+----------+-------------+ 1 row in set (0.00 sec)
This is a bug in MySQL: rows=13M is wrong. Note type=range
Query execution:
- Use binary search to find the row with page_id=12345 (or the first one that's higher)
- Return that row plus the next 9
Examples of indexed and unindexed queries
[edit]Assuming there is an index on foo:
- Good: WHERE foo = 'abc'
- Bad: WHERE foo != 'abc'
- Good: WHERE foo > 'abc' ORDER BY foo (or >= , <= , < , BETWEEN)
- Bad: WHERE foo > 'abc' ORDER BY bar
- Good: WHERE foo LIKE 'abc%'
- Bad: WHERE foo LIKE '%abc' (or anything else that isn't a prefix match)
- Good: WHERE foo LIKE 'abc%' ORDER BY foo
- Bad: WHERE foo LIKE 'abc%' ORDER BY bar
mysql> EXPLAIN SELECT * FROM image WHERE img_name='Flag_of_Canada.svg'; +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ | 1 | SIMPLE | image | const | PRIMARY | PRIMARY | 257 | const | 1 | | +----+-------------+-------+-------+---------------+---------+---------+-------+------+-------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM image WHERE img_name != 'Flag_of_Canada.svg' +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 814940 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ 1 row in set (0.00 sec) -- rows=400K is wrong mysql> EXPLAIN SELECT * FROM image WHERE img_name > 'Flag_of_Canada.svg' ORDER BY img_name LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 407464 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+ 1 row in set (0.00 sec) -- You have to explicitly trigger a worst case here (img_name > 'z' is rare, img_name > 'A' is common) mysql> EXPLAIN SELECT * FROM image WHERE img_name > 'z' ORDER BY img_sha1 LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 1150 | Using where; Using filesort | +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ 1 row in set (0.00 sec) -- rows=1144 is wrong mysql> EXPLAIN SELECT * FROM image WHERE img_name LIKE 'Flag_of_%' ORDER BY img_name LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 1144 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM image WHERE img_name LIKE '%Canada.svg' ORDER BY img_name LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | image | index | NULL | PRIMARY | 257 | NULL | 10 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM image WHERE img_name LIKE 'Flag%' ORDER BY img_sha1 LIMIT 10; +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 1144 | Using where; Using filesort | +----+-------------+-------+-------+---------------+---------+---------+------+------+-----------------------------+ 1 row in set (0.00 sec)
Index on two fields
[edit]This works just like a phone book:
CREATE INDEX name ON phonebook (lastname, firstname);
Note that the order matters. We're sorting by lastname first, then by firstname:
| lastname | firstname | ||
|---|---|---|---|
| Roberts | Daniel | ||
| Roberts | John | ||
| Robertson | Adam | ||
| Robertson | John | ... | ... |
Examples of indexed and unindexed queries
[edit]- Good: ORDER BY lastname, firstname
- Bad: ORDER BY firstname, lastname
- Good: ORDER BY lastname DESC, firstname DESC
- Bad: ORDER BY lastname ASC, firstname DESC
- Good: WHERE lastname = 'Roberts' AND firstname = 'Daniel'
- Bad: WHERE lastname = 'Roberts' OR firstname = 'Adam'
- Good: WHERE lastname = 'Roberts' ORDER BY firstname
- Bad: WHERE firstname = 'John' ORDER BY lastname
- Good: WHERE lastname = 'Roberts' AND firstname > 'Daniel' ORDER BY firstname (or >= , <= , < , BETWEEN)
- Bad: WHERE firstname = 'John' AND lastname > 'Roberts' ORDER BY lastname
- Good: WHERE lastname = 'Roberts' AND firstname LIKE 'D%' ORDER BY firstname
- Bad: WHERE firstname = 'John' AND lastname LIKE 'R%' ORDER BY lastname
mysql> EXPLAIN SELECT * FROM page ORDER BY page_namespace, page_title LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ | 1 | SIMPLE | page | index | NULL | name_title | 261 | NULL | 10 | | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM page ORDER BY page_title, page_namespace LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | 1 | SIMPLE | page | ALL | NULL | NULL | NULL | NULL | 26647899 | Using filesort | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM page ORDER BY page_namespace DESC, page_title DESC LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ | 1 | SIMPLE | page | index | NULL | name_title | 261 | NULL | 10 | | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------+ 1 row in set (0.00 sec) -- Note that ASC is the default, so this is really namespace ASC, title DESC mysql> EXPLAIN SELECT * FROM page ORDER BY page_namespace, page_title DESC LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ | 1 | SIMPLE | page | ALL | NULL | NULL | NULL | NULL | 26647905 | Using filesort | +----+-------------+-------+------+---------------+------+---------+------+----------+----------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM page WHERE page_namespace=0 AND page_title='Wikimania' LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+-------------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+-------------+------+-------+ | 1 | SIMPLE | page | const | name_title | name_title | 261 | const,const | 1 | | +----+-------------+-------+-------+---------------+------------+---------+-------------+------+-------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM page WHERE page_namespace=0 OR page_title='Wikimania' LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ | 1 | SIMPLE | page | ALL | name_title | NULL | NULL | NULL | 26647913 | Using where | +----+-------------+-------+------+---------------+------+---------+------+----------+-------------+ 1 row in set (0.00 sec) -- rows is wrong, this one is quite efficient mysql> EXPLAIN SELECT * FROM page WHERE page_namespace=2 ORDER BY page_title LIMIT 10; +----+-------------+-------+------+---------------+------------+---------+-------+---------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------------+---------+-------+---------+-------------+ | 1 | SIMPLE | page | ref | name_title | name_title | 4 | const | 4506840 | Using where | +----+-------------+-------+------+---------------+------------+---------+-------+---------+-------------+ 1 row in set (0.00 sec) -- rows is wrong, this one is inefficient. The index is still used to sort by page_namespace though mysql> EXPLAIN SELECT * FROM page WHERE page_title='Catrope' ORDER BY page_namespace LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+ | 1 | SIMPLE | page | index | NULL | name_title | 261 | NULL | 10 | Using where | +----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+ 1 row in set (0.00 sec) -- rows is wrong, this one is actually quite efficient mysql> EXPLAIN SELECT * FROM page WHERE page_namespace = 0 AND page_title >= 'Wikimania' ORDER BY page_title LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ | 1 | SIMPLE | page | range | name_title | name_title | 261 | NULL | 681676 | Using where | +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM page WHERE page_title = 'Wikimania' AND page_namespace >= 1 ORDER BY page_namespace LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+----------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+----------+-------------+ | 1 | SIMPLE | page | range | name_title | name_title | 261 | NULL | 13323968 | Using where | +----+-------------+-------+-------+---------------+------------+---------+------+----------+-------------+ 1 row in set (0.00 sec) -- rows is wrong, this one is actually quite efficient mysql> EXPLAIN SELECT * FROM page WHERE page_namespace = 0 AND page_title LIKE 'W%' ORDER BY page_title LIMIT 10; +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ | 1 | SIMPLE | page | range | name_title | name_title | 261 | NULL | 610080 | Using where | +----+-------------+-------+-------+---------------+------------+---------+------+--------+-------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM image WHERE img_user_text LIKE 'J%' ORDER BY img_timestamp; +----+-------------+-------+-------+------------------------+------------------------+---------+------+--------+-----------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+------------------------+------------------------+---------+------+--------+-----------------------------+ | 1 | SIMPLE | image | range | img_usertext_timestamp | img_usertext_timestamp | 257 | NULL | 112420 | Using where; Using filesort | +----+-------------+-------+-------+------------------------+------------------------+---------+------+--------+-----------------------------+ 1 row in set (0.01 sec)
Things you shouldn't do
[edit]- Run queries that return a potentially unlimited number of rows
- Retrieving millions of rows from the DB is slow
- Sending them from the DB to PHP is slow
- Processing them in PHP is slow and can lead to memory exhaustion
- Sending the huge HTML result to the client is slow
- So always use LIMIT
- Run queries that scan a potentially unlimited number of rows
- Like full table scans, and some of the stuff below
- Run unindexed queries :)
- Unindexed WHERE on a condition that is rarely false (e.g. WHERE rev_deleted=0) is sometimes fine
- Filesort is never OK. ORDER BY must always be indexed
- ORDER BY an expression is unindexed and therefore bad
- Use OFFSET (or LIMIT n, m which is equivalent to LIMIT m OFFSET n)
- Doesn't scale: LIMIT 10 OFFSET 5000 scans 5010 rows
- Instead, use something like WHERE foo_id>=12345 for paging (be sure to use a unique index for this!)
- Use COUNT(), SUM(), etc., they scan a potentially unlimited number of rows
- MAX(indexed_field) with no WHERE is fast though
mysql> EXPLAIN SELECT * FROM revision WHERE rev_user_text='Catrope' AND rev_deleted=0 ORDER BY rev_timestamp LIMIT 10; +----+-------------+----------+------+--------------------+--------------------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+----------+------+--------------------+--------------------+---------+-------+------+-------------+ | 1 | SIMPLE | revision | ref | usertext_timestamp | usertext_timestamp | 257 | const | 1044 | Using where | +----+-------------+----------+------+--------------------+--------------------+---------+-------+------+-------------+ 1 row in set (0.01 sec) mysql> EXPLAIN SELECT * FROM image ORDER BY img_width/img_height LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+--------+----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+--------+----------------+ | 1 | SIMPLE | image | ALL | NULL | NULL | NULL | NULL | 814945 | Using filesort | +----+-------------+-------+------+---------------+------+---------+------+--------+----------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM image ORDER BY img_name LIMIT 10 OFFSET 5000; +----+-------------+-------+-------+---------------+---------+---------+------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------+ | 1 | SIMPLE | image | index | NULL | PRIMARY | 257 | NULL | 5010 | | +----+-------------+-------+-------+---------------+---------+---------+------+------+-------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT COUNT(*) FROM image WHERE img_name LIKE 'F%'; +----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 71364 | Using where; Using index | +----+-------------+-------+-------+---------------+---------+---------+------+-------+--------------------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT AVG(img_size) FROM image; +----+-------------+-------+-------+---------------+----------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+----------+---------+------+--------+-------------+ | 1 | SIMPLE | image | index | NULL | img_size | 4 | NULL | 814946 | Using index | +----+-------------+-------+-------+---------------+----------+---------+------+--------+-------------+ 1 row in set (0.04 sec) -- Special case: img_size is indexed, so the row with the highest img_size in the entire table is easy to find mysql> EXPLAIN SELECT MAX(img_size) FROM image; +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ | 1 | SIMPLE | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away | +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ 1 row in set (0.00 sec) mysql> EXPLAIN SELECT MAX(img_size) FROM image WHERE img_name LIKE 'F%'; +----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+ | 1 | SIMPLE | image | range | PRIMARY | PRIMARY | 257 | NULL | 71364 | Using where | +----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+ 1 row in set (0.00 sec)