Категория с большим количеством страниц (огромные смещения) (как работает stackoverflow?)

Question

Я думаю, что мой вопрос можно решить, просто зная, например, как работает stackoverflow.

Например, эта страница загружается за несколько мс (https://stackoverflow.com/questions?page=61440&sort=newest

Единственный запрос, который я могу придумать для этой страницы, это что-то вроде SELECT * FROM stuff ORDER BY date DESC LIMIT {pageNumber}*{stuffPerPage}, {pageNumber}*{stuffPerPage}+{stuffPerPage}

Для выполнения такого запроса может потребоваться несколько секунд, но страница переполнения стека загружается почти мгновенно. Это не может быть кэшированный запрос, так как этот вопрос публикуется с течением времени и перестраивает кэш каждый раз, когда вопрос публикуется, просто безумие.

Итак, как, по вашему мнению, это работает?

(чтобы упростить вопрос, давайте забудем про ORDER BY) Пример (таблица полностью кэшируется в оперативной памяти и хранится на диске ssd)

mysql> select * from thread limit 1000000, 1;
1 row in set (1.61 sec)

mysql> select * from thread limit 10000000, 1;
1 row in set (16.75 sec)

mysql> describe select * from thread limit 1000000, 1;
+----+-------------+--------+------+---------------+------+---------+------+----------+-------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows     | Extra |
+----+-------------+--------+------+---------------+------+---------+------+----------+-------+
|  1 | SIMPLE      | thread | ALL  | NULL          | NULL | NULL    | NULL | 64801163 |       |
+----+-------------+--------+------+---------------+------+---------+------+----------+-------+

mysql> select * from thread ORDER BY thread_date DESC limit 1000000, 1;
1 row in set (1 min 37.56 sec)


mysql> SHOW INDEXES FROM thread;
+--------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table  | Non_unique | Key_name | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| thread |          0 | PRIMARY  |            1 | newsgroup_id | A         |      102924 |     NULL | NULL   |      | BTREE      |         |               |
| thread |          0 | PRIMARY  |            2 | thread_id    | A         |    47036298 |     NULL | NULL   |      | BTREE      |         |               |
| thread |          0 | PRIMARY  |            3 | postcount    | A         |    47036298 |     NULL | NULL   |      | BTREE      |         |               |
| thread |          0 | PRIMARY  |            4 | thread_date  | A         |    47036298 |     NULL | NULL   |      | BTREE      |         |               |
| thread |          1 | date     |            1 | thread_date  | A         |    47036298 |     NULL | NULL   |      | BTREE      |         |               |
+--------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
5 rows in set (0.00 sec)

Answer 1

Создайте индекс BTREE для столбца даты , и запрос будет выполнен в бризе .

CREATE INDEX date ON stuff(date) USING BTREE

---

ОБНОВЛЕНИЕ: Вот тест, который я только что сделал:

CREATE TABLE test( d DATE, i INT, INDEX(d) );

Заполнил таблицу 2 000 000 строк различными уникальными i s и d s

mysql> SELECT * FROM test LIMIT 1000000, 1;
+------------+---------+
| d          | i       |
+------------+---------+
| 1897-07-22 | 1000000 |
+------------+---------+
1 row in set (0.66 sec)

mysql> SELECT * FROM test ORDER BY d LIMIT 1000000, 1;
+------------+--------+
| d          | i      |
+------------+--------+
| 1897-07-22 | 999980 |
+------------+--------+
1 row in set (1.68 sec)

А вот интересное наблюдение:

mysql> EXPLAIN SELECT * FROM test ORDER BY d LIMIT 1000, 1;
+----+-------------+-------+-------+---------------+------+---------+------+------+-------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | test  | index | NULL          | d    | 4       | NULL | 1001 |       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------+

mysql> EXPLAIN SELECT * FROM test ORDER BY d LIMIT 10000, 1;
+----+-------------+-------+------+---------------+------+---------+------+---------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+---------+----------------+
|  1 | SIMPLE      | test  | ALL  | NULL          | NULL | NULL    | NULL | 2000343 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+---------+----------------+

MySql использует индекс для OFFSET 1000, но не для 10000.

Еще интереснее, если я сделаю FORCE INDEX, запрос займет больше времени:

mysql> SELECT * FROM test FORCE INDEX(d) ORDER BY d LIMIT 1000000, 1;
+------------+--------+
| d          | i      |
+------------+--------+
| 1897-07-22 | 999980 |
+------------+--------+
1 row in set (2.21 sec)

Answer 2

Я думаю, что StackOverflow не нужно достигать строк со смещением 10000000. Приведенный ниже запрос должен быть достаточно быстрым, если у вас есть индекс на date и числа в предложении LIMIT взяты из реальных примеров, а не миллионов :)

SELECT * 
FROM stuff 
ORDER BY date DESC 
LIMIT {pageNumber}*{stuffPerPage}, {stuffPerPage}

UPDATE:

Если записи в таблице относительно редко удаляются (как в StackOverflow), тогда вы можете использовать следующее решение:

SELECT * 
FROM stuff 
WHERE id between 
    {stuffCount}-{pageNumber}*{stuffPerPage}+1 AND 
    {stuffCount}-{pageNumber-1}*{stuffPerPage}
ORDER BY id DESC 

Где {stuffCount}:

SELECT MAX(id) FROM stuff

Если у вас есть несколько удаленных записей в базе данных, то на некоторых страницах будет меньше записей, чем {stuffPerPage}, но это не должно быть проблемой. StackOverflow также использует некоторый неточный алгоритм. Например, попробуйте перейти на первую страницу и на последнюю страницу, и вы увидите, что обе страницы возвращают 30 записей на страницу. Но математически это чепуха.

Решения, предназначенные для работы с большими базами данных, часто используют некоторые хаки, которые обычно незаметны для обычных пользователей.

---

В настоящее время разбиение страниц на миллионы записей не является модным, поскольку это непрактично. В настоящее время популярно использовать бесконечную прокрутку (автоматическую или ручную с нажатием кнопки). Это имеет больше смысла, и страницы загружаются быстрее, потому что их не нужно перезагружать. Если вы считаете, что старые записи могут быть полезны и для ваших пользователей, то неплохо было бы создать страницу со случайными записями (с бесконечной прокруткой тоже). Это было мое мнение:)