Скорость выборки

а что этот запрос делает:

>select key1 from t1 where :value between v1 and v2;

я так и не смог понять :(

> я так и не смог понять :(

Вместо :value подставляется число, и ищется запись, где это число находится в промежутке между v1 и v2.

Для этой задачи юзать SQL неоптимально.

Для всех этих (key, v1, v2) поделим пространство bigint на множество отрезков значениями v1, v2. То есть если у нас

(key, v1, v2) такие:
(1, 4, 7)
(2, 5, 8)
(3, 6, 10),

то будут отрезки:
от 4 до 5, от 5 до 6, от 6 до 7, от 7 до 8 и от 8 до 10.

Каждому их этих отрезков мы можем сопоставить множество ключей таким образом:

(4,5) -> 1
(5,6) -> 1,2
(6,7) -> 1,2,3
(7,8) -> 2,3
(8,10) -> 3

Далее, чтобы вычислить список ключей по :value, двоичным поиском ищем по отрезкам тот, в который этот :value попадает.

Хотя, может я ошибаюсь, и

create index idx1 on t1 (v1, v2);

делает то же самое. Было бы интересно узнать.

Ваш index не используется почти,
ибо он уменьшает `зону seq scan` всего в 2 раза,
(подумайте сами почему).

Так или иначе делается большой seq scan и mysql конечно же умирает от ТАКОГО кол-ва одновременныйх seq scan.

Могу порекомендовать перейти на postgresql 8.3 http://postgresmen.ru/articles/view/78
именно из-за фичи Synchronized Scans («синронизованные просмотры»)
у вас станет всё хорошо (или как минимум много лучше).

В Mysql ещё не очень удобный explain analyze (не видно плана запроса), в общем я поэксперементировал на postgresql 8.3 (для просмотра всех планов).


==== теперь немного info почему у вас seq scan-ы ====

создал темповую табличку, положил туда t1(rand(1000)), t2(rand(4000)).

x=# SELECT count(*) FROM a;
count
-------
10000
(1 row)

x=# \di
List of relations
Schema | Name | Type | Owner | Table
--------+----------+-------+-------------+-------
public | t1_idx | index | max_posedon | a
public | t1t2_idx | index | max_posedon | a
public | t2_idx | index | max_posedon | a
(3 rows)

(создал все возможные и так и сяк index-ы)


x=# EXPLAIN ANALYZE SELECT * FROM a WHERE 600 BETWEEN "t1" and "t2";
QUERY PLAN
------------------------------------------------------------------------------- ---------------------
Seq Scan on a (cost=0.00..200.00 rows=4344 width=12) (actual time=0.019..9.866 rows=4328 loops=1)
Filter: ((600 >= t1) AND (600 <= t2))
Total runtime: 15.616 ms
(3 rows)

x=# EXPLAIN ANALYZE SELECT * FROM a WHERE 10 BETWEEN "t1" and "t2";
QUERY PLAN
------------------------------------------------------------------------------- ------------------------------------
Bitmap Heap Scan on a (cost=5.20..57.05 rows=122 width=12) (actual time=0.164..0.410 rows=115 loops=1)
Recheck Cond: (10 >= t1)
Filter: (10 <= t2)
-> Bitmap Index Scan on t1_idx (cost=0.00..5.17 rows=123 width=0) (actual time=0.138..0.138 rows=118 loops=1)
Index Cond: (10 >= t1)
Total runtime: 0.611 ms

x=# EXPLAIN ANALYZE SELECT * FROM a WHERE 2900 BETWEEN "t1" and "t2";
QUERY PLAN
------------------------------------------------------------------------------- ----------------------------
Index Scan using t2_idx on a (cost=0.00..8.27 rows=1 width=12) (actual time=0.020..0.020 rows=0 loops=1)
Index Cond: (2900 <= t2)
Filter: (2900 >= t1)
Total runtime: 0.057 ms
(4 rows)

видно что index-ы `полезны` тока где-то на границах значений, иначе бесполезны. (Опять же подумав понятно почему).

Нужен или значительно более сложный метод, или (в вашем случае) добится того, чтобы много seq scan-ов одновременно работали хорошо.
Именно поэтому postgresql 8.3 вам бы подошёл.

До этого был postgres 8.3. При таком количестве запросов он тоже тупил не по-детски.

Вот интересно было бы узнать, как подобное в GeoIP реализовано. Там примерно такая же хрень, насколько я понимаю.

именно 8.3? там версия очень кретична.

возможно надо копать в сторону gist gin индексов, (а возможно что-то уже такое есть). Ну и вопрос, какая предметная область
(каковы диапозоны для t1 и t2, в принципе для частной between задачи, думаю можно что-то придумать).

в мускуле есть типы для хранения геоданных. задай диапазоны в виде прямоугольников и ищи все прямоугольники содержащие заданную точку.

в GeoIP
там своя база в виде дерева
и на полутора милионах там будет только несколько сравнений
для того чтобы найти диапазон

И насколько понимаю, самое сложное в такой задаче - построить дерево, которое по возможности должно быть сбалансированным, а в случае с отрезками и прямоугольниками этого добиться не так просто... Кстати, похожая задача выборки возникает в случае редактора диаграмм, ну это так, к слову.

Возможно, что исходная задачка не самая подходящая для реляционной базы (хотя я не специалист в последнем). Даже в случае деревьев есть свои сложности. Например, придумали k-d деревья, чтобы получить некое подобие бинарных деревьев, когда переменных критериев больше одного (как в исходном случае). Есть и другие способы.

В общем, хватает заморочек... если автор желает получить эффективное решение.

Можно ещё предложить метод припарок:

select key1 from t1 where (v1 between :value - const and value) and (:value between v1 and v2)

Если ничего не найдёт, то тогда уже исходный запрос. Индекс нужен по v1. Рассчитано на то, чтобы попытаться сократить область поиска. Const подбирается вручную.

PS. честно говоря, не пробовал

Ну а ты что хотел? Тебе нужно построить Interval Tree (в Гугл). Места будет занимать O(n = кол-во интервалов), запрос будет O(log n + кол-во найденных интервалов). С всего 1.5M записей проще всего не выделываться с MySQL и хранить дерево в памяти. Если все равно хочется трахаться с DB — есть реляционная реализация Interval Tree: RI-Tree (http://www.dbs.informatik.uni-muenchen.de/Forschung/CAD/presentations/RI-Tree...).