Меню
Что нового?

InnoDB. Перебор BTREE индекса?

  • Автор темы Автор темы Найч
  • Дата начала Дата начала

Найч

Алгоритмик :-)
InnoDB. Перебор BTREE индекса?

Есть два мнения по поводу этого плана запроса

mysql> explain select max(comment_id) from comments;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| 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)

1. Для получения максимального значения индекс будет сканироваться (ака поиск по индексу)
2. Данные хранятся в заголовке индекса, следовательно, никакого поиска - просто читаем нужное значение

Кто-нибудь может ткнуть пальцем в литературу, где освещается подобный вопрос? В пользу второго мнения гуглятся предположения разных людей, достоверного пока не нашел

Спасибо
 
как раз про эту дискуссию я и упоминал ;)
Таблица ИнноДБ (вроде в заголовке указал, мож незаметно)
Майк неуверенно добавил, что это "если он правильно помнит". Таких "вроде помнящих" мнений немало :)
select comment_id from comments order by commend_id desc limit 1
Нажмите для раскрытия...
а вот тут эксплейн показывает перебор всех элементов индекса

Насколько я помню (с) в каждом листе btree хранит максимальный и минимальный элемент, т.е. для получения максимального надо просто прочитать это значение с корневого листа. Ищу подтверждения или опровержения.
Если что - http://en.wikipedia.org/wiki/B-tree
 
Найч
тоже помнится что нет скана индекса. Проверил экспериментально на таблице в 4M записей innodb - результат мгновенный в отличие от count(*), да и план count'а - rows: 4M, Using index

-~{}~ 09.06.08 20:03:

а вот тут эксплейн показывает перебор всех элементов индекса
Нажмите для раскрытия...
то что показывает перебор - это неправда :) оптимизатор mysql'я не учитывает limit'ы.
 
а как-то все равно ;)
если он пошел гулять по индексу - уже разница с единственным чтением корневого листа. Или из какого-либо хедера.
Как теорема Ферма - вроде очевидно, а доказательств на поверхности нет :)
 
ну как бы перебор да, но на самом деле из индекса понятно где у нас "верх" и "низ" и операция моментальная - при лимит 1 перебор остановится на первом "прямом" попадании в начало/хвост индекса

а MIN() может быть оптимальнее на myisam (засчет оптимизации "взять из заголовка", также как с count(*)) но никак не на innodb по причине версионной природы последнего. так же как с любыми другими агрегатками

ну и если дальше мыслить логически, не для всех же ключей myisam будет писать счетчик в хедер таблицы. для PK - возможно, и если там автоинкремент - то стопудово (кстати, как тут дела с автоинкрементным PK на InnoDB - тоже вопрос требующий поразмыслить), а просто для какого-то индекса в любом случае в него надо залезить и получаем один и тот же хрен что с order+limit - и это в лучшем случае.

-~{}~ 09.06.08 23:06:

UPD: проверка показывает, что для таблицы вида
PHP: 
+-------+------------+------+-----+---------+----------------+
| id    | bigint(20) | NO   | PRI | NULL    | auto_increment |
| id1   | bigint(20) | YES  | UNI | NULL    |                |
| id2   | bigint(20) | YES  | MUL | NULL    |                |
explain select max() дает Select tables optimized away для любого из полей, при любом engine, и даже внутри транзакции. Кажется, либо explain гонит, либо я чего-то не понимаю :)

-~{}~ 09.06.08 23:08:

UPD2: ХОЧУ EXPLAIN ANALYZE! :)

-~{}~ 09.06.08 23:10:

Кстати.

t1 = myisam, t2 = innodb:

PHP: 
mysql> explain select count(*) from test.t1;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| 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 count(*) from test.t2;
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | t2    | index | NULL          | PRIMARY | 8       | NULL |   10 | Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
1 row in set (0.00 sec)

тут жеж ведь все как и ожидалось. не, я правда нифига не понимаю.

-~{}~ 09.06.08 23:16:

Так, кажется я начинаю понимать. Select count(*) на btree требует пробега по индексу, select min() или max() - просто заглянуть в индекс. Когда мы работаем в транзации, делается некая hotcopy этого btree из которого мы тем не менее все может достать явно. Получается что "Select tables optimized away" означает "это может быть что угодно, что мы читаем напрямую", чтоли?
 
fixxxer, в твоем примере с explain select count(*) from test.t1, "Select tables optimized away" означает только то, что для MyISAM таблиц значение для count(*) хранится и не требует никакой оптимизации.
 
да это понятно дело, потому и приведено в рамках общих рассуждений, я тут сам с собой разговаривал ;)

вообще, конечно, не хватает детализации, пока вот дотумкал о внутреннем устройстве btree... хочется инфы в эксплейне поподробнее, чем "оно там где-то хранится" ;)
 
А возник такой вопрос по b-tree структуре (в частности myisam).

Выполняю
[sql]
flush status;select id from `table` order by id desc limit 1;show status like 'Key_read_requests';
[/sql]

Полученное значение Key_read_requests говорит о глубине b-tree или нет?

Значения параметра на таблицах, какие попались под руку:
rows: 800, Key_read_requests=2
rows: 100K-460K, Key_read_requests=3
rows: 1.9M, Key_read_requests=4
 
Войдите или зарегистрируйтесь для ответа.
Сверху