Задача
Быстро найти записи, где заданное (пользователем) значение находится между значениями полей.
Требования (если вы не сможете этого проделать в своём случае, дальше можно не читать)
Перевести таблицу, в которой идет поиск, на MyISAM или создать дополнительную таблицу на MyISAM, заполняемую при изменении первой триггерами или вручную.
Примеры
Найти звонки, начавшиеся, длившиеся или оконченные в определенное время.
Выяснить принадлежность IP адреса определенному региону по БД GeoIP.
Выяснить тариф звонка по определенному номеру назначения.
Выяснить тариф звонка по определенному номеру назначения в определенное время суток.
Выяснить тариф звонка по определенному номеру назначения в определенный момент времени (если хранятся все изменения тарифов во времени).
Найти биржевые ордера, открытые до или в и закрытые в или после определенного времени.
Формально
Оптимизировать запросы
SELECT ... FROM t WHERE :value BETWEEN col1 AND col2
SELECT ... FROM t WHERE :value BETWEEN col1 AND col2 AND :another_value BETWEEN col3 AND col4
на примере "Выяснить тариф звонка по определенному номеру назначения в определенный момент времени (если хранятся все изменения тарифов во времени)"
+ Подготовим данные
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
>mysql --host=localhost --user=... --password
Enter password: ...
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 4
Server version: 5 . 1 . 35 -community-debug MySQL Community Server - Debug (GPL)
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.
mysql> USE test;
Database changed
mysql> CREATE TABLE price(
-> id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
-> start_number BIGINT NOT NULL
-> COMMENT 'destination number first (inclusive)',
-> end_number BIGINT NOT NULL
-> COMMENT 'destination number last (inclusive)',
-> start_d DATE NOT NULL
-> COMMENT 'price became active (inclusive)',
-> end_d DATE NOT NULL
-> COMMENT 'price became inactive (inclusive)',
-> price DECIMAL( 10 , 6 ) NOT NULL DEFAULT 1 ,
-> # notice, we create all possible index combinations
-> # however these indexes won`t help us much
-> INDEX(start_number),
-> INDEX(end_number),
-> INDEX(start_d),
-> INDEX(end_d),
-> INDEX(start_number, end_number),
-> INDEX(end_number, start_number),
-> INDEX(start_d, end_d),
-> INDEX(end_d, start_d),
-> INDEX(start_number, end_number, start_d, end_d),
-> INDEX(start_number, end_number, end_d, start_d),
-> INDEX(end_number, start_number, start_d, end_d),
-> INDEX(end_number, start_number, end_d, start_d),
-> INDEX(start_d, end_d, start_number, end_number),
-> INDEX(end_d, start_d, start_number, end_number),
-> INDEX(start_d, end_d, end_number, start_number),
-> INDEX(end_d, start_d, end_number, start_number)
-> )
-> ENGINE = InnoDB
-> COMMENT 'historized pricelist by destination';
Query OK, 0 rows affected ( 0 . 08 sec)
Заполним произвольными данными
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
mysql> DELIMITER $$
mysql> CREATE FUNCTION fill_price(
-> # period to generate pricelist for
-> first_d DATE,
-> last_d DATE,
-> # how many days a price stays actual
-> # random-generated between min and max for each price
-> days_actual_min INT,
-> days_actual_max INT,
-> # how many numbers there are in a price entry
-> # random-generated between min and max for each price
-> step_min INT,
-> step_max INT
-> )
-> RETURNS INT
-> COMMENT 'fills pricelist with randomly generated rates'
-> BEGIN
-> DECLARE last_number BIGINT DEFAULT 99999999999 ;
->
-> DECLARE cnt INT DEFAULT 0 ;
->
-> DECLARE start_d DATE;
-> DECLARE end_d DATE;
-> DECLARE start_number BIGINT DEFAULT 0 ;
-> DECLARE end_number BIGINT;
->
-> WHILE start_number < last_number DO
-> SET end_number = start_number
-> + FLOOR(step_min + RAND() * (step_max - step_min));
-> SET start_d = first_d;
-> WHILE start_d < last_d DO
-> SET end_d = start_d
-> + INTERVAL FLOOR(
-> days_actual_min
-> + RAND() * (days_actual_max - days_actual_min)
-> ) DAY;
-> INSERT INTO price(start_d, end_d, start_number, end_number)
-> VALUES(start_d, end_d, start_number, end_number);
-> SET cnt = cnt + 1 ;
-> SET start_d = end_d + INTERVAL 1 DAY;
-> END WHILE;
-> SET start_number = end_number + 1 ;
-> END WHILE;
->
-> RETURN cnt;
-> END$$
Query OK, 0 rows affected ( 0 . 00 sec)
mysql> DELIMITER ;
mysql> SELECT fill_price(
-> @first_d, @last_d, 30 , 60 , 10000000 , 1000000000
-> ) entries
-> FROM (
-> SELECT @first_d := '2008-01-01' + INTERVAL 0 DAY first_d,
-> @last_d := '2010-12-31' + INTERVAL 0 DAY last_d
-> ) v;
+---------+
| entries |
+---------+
| 5133 |
+---------+
1 row in set ( 9 . 58 sec)
mysql> DROP FUNCTION fill_price;
Query OK, 0 rows affected ( 0 . 00 sec)
+ Обычные запросы работают плохо
индексы не сильно помогают: разброс дат-номеров достаточно равномерен и избавившись от full table scan всё равно приходится просматривать достаточное количество записей, из-за этого производительности в большинстве случаев недостаточно
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
mysql> SELECT @destination_number := FLOOR(RAND() * 99999999999 ) number,
-> @d := @first_d + INTERVAL FLOOR(
-> RAND()
-> * DATEDIFF(@last_d, @first_d)
-> ) DAY d
-> FROM (SELECT @desination_number := 0 , @d := '0000-00-00') v;
+-------------+------------+
| number | d |
+-------------+------------+
| 81110108904 | 2010 - 11 - 17 |
+-------------+------------+
1 row in set ( 0 . 00 sec)
mysql> EXPLAIN EXTENDED
-> SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
-> FROM price p
-> WHERE @destination_number BETWEEN p.start_number AND p.end_number
-> AND @d BETWEEN p.start_d AND p.end_d;
+----+-------------+-------+-------+--------------------+---------+---------+------+------+----------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+-------+--------------------+---------+---------+------+------+----------+-------------+
| 1 | SIMPLE | p | range | start_number, | end_d_3 | 3 | NULL | 394 | 100 . 00 | Using where |
| | | | | end_number, | | | | | | |
| | | | | start_d,end_d, | | | | | | |
| | | | | start_number_2, | | | | | | |
| | | | | end_number_2, | | | | | | |
| | | | | start_d_2,end_d_2, | | | | | | |
| | | | | start_number_3, | | | | | | |
| | | | | start_number_4, | | | | | | |
| | | | | end_number_3, | | | | | | |
| | | | | end_number_4, | | | | | | |
| | | | | start_d_3,end_d_3, | | | | | | |
| | | | | start_d_4,end_d_4 | | | | | | |
+----+-------------+-------+-------+--------------------+---------+---------+------+------+----------+-------------+
1 row in set, 1 warning ( 0 . 01 sec)
mysql> SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
-> FROM price p
-> WHERE @destination_number BETWEEN p.start_number AND p.end_number
-> AND @d BETWEEN p.start_d AND p.end_d;
+--------------+-------------+------------+------------+----------+
| start_number | end_number | start_d | end_d | price |
+--------------+-------------+------------+------------+----------+
| 80985716868 | 81183917450 | 2010 - 11 - 07 | 2010 - 12 - 23 | 1 . 000000 |
+--------------+-------------+------------+------------+----------+
1 row in set ( 0 . 02 sec)
Просмотреть 394 строки из 5133 (=~7%) - не очень хороший результат. При равномерном распределении и росте количества строк, процент выбираемых от общего числа строк не сильно изменится. Будет 100 000 строк - придется просмотреть 7000. Будет 1 млн. - придется просмотреть 70 тыс. Т. о. по мере накопления данных в таблице, запрос будет работать всё медленнее и медленнее. Посмотрим, что с этим можно сделать. + Использование RTree индексов
В MySQL есть сильно урезанная поддержка RTree индексов. Речь идет о (геометрических) spatial-индексах для MyISAM таблиц. К сожалению, для других типов таблиц данные индексы не поддерживаются и скорее всего в ближайшее время не будут.
Преобразуем наш прайс-лист в MyISAM и добавим LINESTRING колонку
1.
2.
3.
4.
mysql> ALTER TABLE price
-> ENGINE = MyISAM,
-> ADD COLUMN start_end_number_d LINESTRING NOT NULL;
Query OK, 5133 rows affected ( 1 . 35 sec)
Records: 5133 Duplicates: 0 Warnings: 0
1.
2.
3.
4.
5.
6.
7.
mysql> UPDATE price p
-> SET p.start_end_number_d
-> = LINESTRING(
-> POINT(p.start_number, p.start_d),
-> POINT(p.end_number, p.end_d)
-> );
Query OK, 5133 rows affected ( 0 . 89 sec)
Rows matched: 5133 Changed: 5133 Warnings: 0
1.
2.
3.
mysql> ALTER TABLE price
-> ADD SPATIAL INDEX(start_end_number_d);
Query OK, 5133 rows affected ( 3 . 51 sec)
Records: 5133 Duplicates: 0 Warnings: 0
RTree-индекс идеально подходит для такого типа запросов, просматривается всегда ровно столько строк, сколько будет в результате запроса.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
mysql> EXPLAIN EXTENDED
-> SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
-> FROM price p
-> WHERE MBRContains(
-> start_end_number_d,
-> POINT(@destination_number, DATE(@d))
-> );
+----+-------------+-------+-------+--------------------+--------------------+---------+------+------+----------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+-------+--------------------+--------------------+---------+------+------+----------+-------------+
| 1 | SIMPLE | p | range | start_end_number_d | start_end_number_d | 34 | NULL | 1 | 100 . 00 | Using where |
+----+-------------+-------+-------+--------------------+--------------------+---------+------+------+----------+-------------+
1 row in set, 1 warning ( 0 . 01 sec)
mysql> SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
-> FROM price p
-> WHERE MBRContains(
-> start_end_number_d,
-> POINT(@destination_number, DATE(@d))
-> );
+--------------+-------------+------------+------------+----------+
| start_number | end_number | start_d | end_d | price |
+--------------+-------------+------------+------------+----------+
| 80985716868 | 81183917450 | 2010 - 11 - 07 | 2010 - 12 - 23 | 1 . 000000 |
+--------------+-------------+------------+------------+----------+
1 row in set ( 0 . 00 sec)
+ Одним скриптом 1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
USE test;
CREATE TABLE price(
id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
start_number BIGINT NOT NULL
COMMENT 'destination number first (inclusive)',
end_number BIGINT NOT NULL
COMMENT 'destination number last (inclusive)',
start_d DATE NOT NULL
COMMENT 'price became active (inclusive)',
end_d DATE NOT NULL
COMMENT 'price became inactive (inclusive)',
price DECIMAL( 10 , 6 ) NOT NULL DEFAULT 1 ,
# notice, we create all possible index combinations
# however these indexes won`t help us much
INDEX(start_number),
INDEX(end_number),
INDEX(start_d),
INDEX(end_d),
INDEX(start_number, end_number),
INDEX(end_number, start_number),
INDEX(start_d, end_d),
INDEX(end_d, start_d),
INDEX(start_number, end_number, start_d, end_d),
INDEX(start_number, end_number, end_d, start_d),
INDEX(end_number, start_number, start_d, end_d),
INDEX(end_number, start_number, end_d, start_d),
INDEX(start_d, end_d, start_number, end_number),
INDEX(end_d, start_d, start_number, end_number),
INDEX(start_d, end_d, end_number, start_number),
INDEX(end_d, start_d, end_number, start_number)
)
ENGINE = InnoDB
COMMENT 'historized pricelist by destination';
DELIMITER $$
CREATE FUNCTION fill_price(
# period to generate pricelist for
first_d DATE,
last_d DATE,
# how many days a price stays actual
# random-generated between min and max for each price
days_actual_min INT,
days_actual_max INT,
# how many numbers there are in a price entry
# random-generated between min and max for each price
step_min INT,
step_max INT
)
RETURNS INT
COMMENT 'fills pricelist with randomly generated rates'
BEGIN
DECLARE last_number BIGINT DEFAULT 99999999999 ;
DECLARE cnt INT DEFAULT 0 ;
DECLARE start_d DATE;
DECLARE end_d DATE;
DECLARE start_number BIGINT DEFAULT 0 ;
DECLARE end_number BIGINT;
WHILE start_number < last_number DO
SET end_number = start_number
+ FLOOR(step_min + RAND() * (step_max – step_min));
SET start_d = first_d;
WHILE start_d < last_d DO
SET end_d = start_d
+ INTERVAL FLOOR(
days_actual_min
+ RAND() * (days_actual_max – days_actual_min)
) DAY;
INSERT INTO price(start_d, end_d, start_number, end_number)
VALUES(start_d, end_d, start_number, end_number);
SET cnt = cnt + 1 ;
SET start_d = end_d + INTERVAL 1 DAY;
END WHILE;
SET start_number = end_number + 1 ;
END WHILE;
RETURN cnt;
END$$
DELIMITER ;
SELECT fill_price(
@first_d, @last_d, 30 , 60 , 10000000 , 1000000000
) entries
FROM (
SELECT @first_d := '2008-01-01' + INTERVAL 0 DAY first_d,
@last_d := '2010-12-31' + INTERVAL 0 DAY last_d
) v;
DROP FUNCTION fill_price;
SELECT @destination_number := FLOOR(RAND() * 99999999999 ) number,
@d := @first_d + INTERVAL FLOOR(
RAND()
* DATEDIFF(@last_d, @first_d)
) DAY d
FROM (SELECT @desination_number := 0 , @d := '0000-00-00') v;
EXPLAIN EXTENDED
SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
FROM price p
WHERE @destination_number BETWEEN p.start_number AND p.end_number
AND @d BETWEEN p.start_d AND p.end_d;
SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
FROM price p
WHERE @destination_number BETWEEN p.start_number AND p.end_number
AND @d BETWEEN p.start_d AND p.end_d;
ALTER TABLE price
ENGINE = MyISAM,
ADD COLUMN start_end_number_d LINESTRING NOT NULL;
UPDATE price p
SET p.start_end_number_d
= LINESTRING(
POINT(p.start_number, p.start_d),
POINT(p.end_number, p.end_d)
);
ALTER TABLE price
ADD SPATIAL INDEX(start_end_number_d);
EXPLAIN EXTENDED
SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
FROM price p
WHERE MBRContains(
start_end_number_d,
POINT(@destination_number, DATE(@d))
);
SELECT p.start_number, p.end_number, p.start_d, p.end_d, p.price
FROM price p
WHERE MBRContains(
start_end_number_d,
POINT(@destination_number, DATE(@d))
);
DROP TABLE price;
|
