задачка на сообразительность

[Найч]

задачка на сообразительность

Есть таблица

[sql]
CREATE TABLE `test` (
`id` int(11) NOT NULL auto_increment,
`type` tinyint(4) default '0',
PRIMARY KEY (`id`)
);
[/sql]
с таким набором данных

mysql> select * from test;
+----+------+
| id | type |
+----+------+
|  1 |    2 |
|  2 |    2 |
|  3 |    3 |
|  4 |    2 |
|  5 |    2 |
|  6 |    2 |
|  7 |    3 |
|  8 |    2 |
|  9 |    2 |
| 10 |    3 |
| 11 |    2 |
| 12 |    2 |
| 13 |    2 |
| 14 |    2 |
| 15 |    3 |
| 16 |    2 |
| 17 |    2 |
| 18 |    2 |
| 19 |    3 |
| 20 |    2 |
| 21 |    2 |
| 22 |    2 |
| 23 |    3 |
................

где type, предположим, имеет несколько возможных значений. Для простоты скажем что только два: 2 и 3.
Задача - выбрать минимальное количество строк, отсортированных по id начиная с 1, в которых есть три строки с type=3. Т.е. по достижении 10й строки количество троек становится равным 3 и это и есть правильный ответ.

mysql> select * from test;
+----+------+
| id | type |
+----+------+
|  1 |    2 |
|  2 |    2 |
|  3 |    3 |
|  4 |    2 |
|  5 |    2 |
|  6 |    2 |
|  7 |    3 |
|  8 |    2 |
|  9 |    2 |
| 10 |    3 |

Ваши предложения как это сделать средствами мускула? Считаем, что числа в поле type расположены случайным образом и никакой зависимости между ними нет. Вариант с курсором + временная таблица не рассматриваем

Тестовые данные
[sql]
insert into test (type) values (2),(2),(3),(2),(2),(2),(3),(2),(2),(3),(2),(2),(2),(2),(3),(2),(2),(2),(3),(2),(2),(2),(3),(2),(2),(2),(3),(2),(2),(2),(2),(3),(2),(2),(2),(2),(2),(2),(3),(2),(2),(2),(2),(2),(3),(3),(2);
[/sql]

 

[Sender]

что-то типа:

select * from table where id <= (select id from table where type_id=3 order by id limit 1 offset 3);

нет?

 

[Найч]

да, с маленькой поправкой

[sql]
select * from test where id <= (select id from test where type=3 order by id limit 1 offset 2);
[/sql]

еще опции?

 

[zerkms]

аналогичное решение, только с IN и без offset во вложенном подзапросе

ps: такие задачи обычно показывают, что реляционные СУБД потому и реляционные, что не навигационные ))

 

[Найч]

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

 

[Gas]

Можно ещё с помощью пользовательских переменных сделать + having, но кода будет больше. И я бы этот вариант сделал 2-мя запросами, потому что подзапрос вычисляется для каждой строки таблицы test, а не один раз.

 

[Найч]

можешь продемонстрировать вариант с переменными?

 

[zerkms]

потому что подзапрос вычисляется для каждой строки таблицы test, а не один раз.

тут ещё вилами по воде писано как mysql будет оптимизировать not-correlated subquery

 

[Gas]

SELECT * FROM test WHERE id <= ( SELECT if(SLEEP(1), id, id) FROM test WHERE TYPE = 3 ORDER BY id LIMIT 1 offset 2 );

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

 

[Найч]

mysql> SELECT * FROM test WHERE id <= ( SELECT if(SLEEP(1), id, id) FROM test WHERE TYPE = 3 ORDER BY id LIMIT 1 offset 2 );
+----+------+
| id | type |
+----+------+
|  1 |    2 |
|  2 |    2 |
|  3 |    3 |
|  4 |    2 |
|  5 |    2 |
|  6 |    2 |
|  7 |    3 |
|  8 |    2 |
|  9 |    2 |
| 10 |    3 |
+----+------+
10 rows in set (47.09 sec)

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

 

[Gas]

Следовательно, подзапрос выполняется только один раз

почему один раз? функция sleep в подзапросе выполняется 47 раз, так как время запроса 47 сек, правда я на 100% не уверен что правильно это трактую, но мне кажется логично сделать вывод о выполнениии подзапроса столько раз, сколько раз выполняется какая-то его часть.

 

[Найч]

ах да, согласен
здесь это не принципиально, решение понятно.
Твой вариант с переменными?

 

[Gas]

set @i:=0;
select * from 
(
  select *, if(3=`type` or @i>=3, @i:=@i+1, @i) as flag 
  from test 
  order by id
) as t 
having flag <= 3;

но сам бы я так не делал даже вариант с временной таблицей лучше )

 

[Найч]

лучше? А мне нравится курсор + тмп таблица

 

[Sender]

Автор оригинала: zerkms
аналогичное решение, только с IN и без offset во вложенном подзапросе

можно продемонстрировать? никак не могу представить решение с in и без offset

 

[zerkms]

я неправильно прочитал задание, отменяется IN

 

[Sender]

Автор оригинала: Найч
А можно ли придумать решение с единичным проходом по множеству и стопом в нужном месте?

Разве что вводить переменную храняющую id третьей записи с type_id=3, и ее обслуживать