Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > MySQL > Задачка на собеседовании..


Автор: Kurt 2.9.2005, 22:46
Вспомнил, как ходил в прошлом году на собеседование. Мне тогда дали такую задачку:
есть таблица:
Код

CREATE TABLE mtest (
  vdate date default NULL,
  vname varchar(10) default NULL,
  vval float default NULL
)

Это таблица изменений цен на валюту (пусть, для простоты, это цена покупки).
Например, есть такие данные:
Цитата
+------------+-------+------+
| vdate      | vname | vval |
+------------+-------+------+
| 2000-01-02 | USD  | 20.5 |
| 2000-01-04 | EURO  | 21.5 |
| 2000-06-04 | EURO  | 25.5 |
| 2001-03-07 | USD  |  30 |
| 2005-01-07 | USD  |  17 |
| 2005-04-14 | EURO  |  23 |
+------------+-------+------+

Задача: получить актуальную стоимость каждой валюты в формате
"дата_последнего_изменения, название_валюты, цена"
То есть в данном примере ответ:
Цитата
| 2005-01-07 | USD  |  17 |
| 2005-04-14 | EURO  |  23 |

Задачу предлагалось решить на MSSQL2000 и я как-то вывертелся через вложенный запрос, что явно очень не понравилось моим "экзаменаторам".
Прошли годы. На то место я не устроился, о чем, правда, не сожалею.
Однако, вот теперь задумался, как решить такую задачу на MySQL 3.23 - то есть до появления вложенных запросов?

Автор: Sardar 3.9.2005, 00:05
Цитата(Kurt @ 2.9.2005, 21:46)
получить актуальную стоимость каждой валюты

Это по последней дате? А разве нельзя сгруппировать по типу валюты, отсортировав по дате и снять первую строку с каждой группы?

Автор: Kurt 3.9.2005, 00:26
Одним запросом? (меня просили одним)
А ну, покажи, что-то я наверное совсем туплю..

Автор: Sardar 3.9.2005, 00:59
Цитата(Kurt @ 2.9.2005, 23:26)
А ну, покажи, что-то я наверное совсем туплю..

Да я сам туплю...
Пока порешал созданием временной таблицы... Но пятой точкой чую что можно одним запросом и эффективно...

Автор: Secandr 3.9.2005, 07:56
Может так:
Код

SELECT t1.vval, t2.vval FTOM mtest 't1', mtest  't2' WHERE t1.vname='EURO', t2.vname ='USD' ORDER BY t1.vdate DESC ,t2.vdate DESC LIMIT 0,1


Или ещё проще:
Код

SELECT * FROM mtest ORDER BY vdate DESC

И разобрать средствами php, допустим.

Автор: Kurt 3.9.2005, 13:33
Цитата
SELECT t1.vval, t2.vval FTOM mtest 't1', mtest  't2' WHERE t1.vname='EURO', t2.vname ='USD' ORDER BY t1.vdate DESC ,t2.vdate DESC LIMIT 0,1

Secandr
Количество валют нежестко задано. Их может быть две (как у меня в примере), а момет быть 50.
Поэтому этот запрос не будет решением.

Цитата

Или ещё проще:
Выделить всёкод SQL
Код

SELECT * FROM mtest ORDER BY vdate DESC

И разобрать средствами php, допустим.

Согласен. Но меня просили получить результат одним запросом. Без привлечения сторонних технологий типа PHP, ASP etc.

Автор: Secandr 3.9.2005, 19:47
надо попробовать, есть пара дурных идей...

Автор: Zipo 4.9.2005, 14:51
Тут вся трудность в дефолтной сортировке по дате. Физически данные будут храниться отсорированные по дате нарастающе (ASC). Т.к. заполняя таблицу мы каждый раз вводим дату большую чем предыдущая.
В MySQL данные храняться так же как и в MSSQL таблицах при отсутствии кластерного индекса.
Я не встречал создание индексов с указанием направления сортировки. В MySQL этого вроде и нету.
Задача решается таким запросом:
Код

SELECT vdate, vname, vval FROM (
       SELECT
             *
       FROM mtest
       ORDER BY vdate DESC
       ) AS tb
GROUP BY vname


Т.е. мы сортируем таблицу в нужном нам направлении по дате. Потом группируем по валюте и в итоге получим, то, что хотели.
Если кто знает как создать индекс с указанием направления сортировки (что бы данные физически хранились отсортированные по дате на DESC), то от вложеного запроса можно избавиться.

Автор: Kurt 4.9.2005, 16:17
Zipo
К сожалению, задача таким запросом не решится. Более того, он даже не будет выполнен, т.к. синтаксически не верен.
У меня нет под рукой MySQL 4.1 (чтоб вложенные запросы работали), но я проверил свою догадку на MSSQL2000.
Во-первых, MSSQL не разрешает сортировку в подзапросе. Если не ошибаюсь, MySQL это также запрещает.
А во-вторых, даже если не обращать внимание на сортировку, то:
Цитата
..
Column 'tb.vdate' is invalid in the select list because it is not contained in either an aggregate function or the GROUP BY clause.
..
Column 'tb.vval' is invalid in the select list because it is not contained in either an aggregate function or the GROUP BY clause.

То есть столбцы таблицы должны быть упомянуты либо в агрегатной ф-ции, либо в group by.
Уверен, это же правило распространяется и на другие СУБД.

P.S. В тестовой таблице, что мне предлагали, даты были перемешаны в случайном порядке. То есть не обязательно нижняя дата для каждой валюты больше верхней даты. Это просто я в примере так написал.

Автор: Zipo 4.9.2005, 17:09
Я не писал если бы не проверил. У меня MySQL 4.1.7
Запрос корректно отрабатывает у меня.
Знаю, что MySQL не позволяет использовать LIMIT во вложенном запросе. О сортировках подобного не слышал.

Цитата
То есть столбцы таблицы должны быть упомянуты либо в агрегатной ф-ции, либо в group by.


Это скорее всего тоже ограничение MySQL 3.23
MySQL при группировке по определенным столбцам дает значения колонкам которые не вошли в группировку из первой записи которую он нашел эквивалентной группе. Группа у нас это валюта. Остальные поля получают значение из первой найденной строки для этой группы. Поэтому я и обратил Ваше внимание на сортировку.

В MSSQL сортировку использовать нельзя если во вложенном запросе нету TOP. С группировкой в MSSQL так непроходит.

Автор: Zipo 4.9.2005, 17:30
Для MSSQL оптимальным скорее всего будет процедура

Код

DECLARE @CountVal int
SELECT @CountVal = count(DISTINCT vname) FROM mtest;
EXEC ('SELECT TOP ' + @CountVal + ' vdate, vname, vval FROM mtest ORDER BY vdate DESC;')


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

Автор: S.A.P. 4.9.2005, 19:37
Код

SELECT MAX( vdate ) , vname, vval
FROM `mtest` 
GROUP BY vname


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

Автор: Kurt 4.9.2005, 20:53
Zipo
Хм.. Ваше решение в MSSQL через процедуру очень интересно. Возьму на вооружение. smile Спасибо. Хотя, конечно, это ограничение:
Цитата
Это конечно при условии, что обновление позиции происходит для всех валют. Т.е. не может быть обновление одной вылюты а потом другой через неделю.

сильно снижает практическое применение такого решения.
А вот с MySQL. Как бы добиться правильного результата на MySQL 3.23. Не знаю почему, но почти во всех (даже самых современных) дистрибутивах Linux я встречаю именно 3.23, кроме того, на многих хостингах также используется эта база. Ради спортивного интереса хотелось бы все-таки решить эту задачу для MySQL 3.23.

Perchilla
Не. Не пойдет. Вот, смотри, что возвращает твой запрос:
Цитата
mysql> select max(vdate), vname, vval from mtest group by vname;
+------------+-------+------+
| max(vdate) | vname | vval |
+------------+-------+------+
| 2005-04-14 | EURO  | 20.5 |
| 2005-01-07 | USD  | 20.5 |
+------------+-------+------+
2 rows in set (0.17 sec)

Согласись, цены явно не те.

З.Ы. Вот такие вот задачки дают у нас в деревне на собеседованиях. smile

Автор: Ignat 4.9.2005, 22:06
Цитата(Kurt @ 4.9.2005, 21:53)
Вот такие вот задачки дают у нас в деревне на собеседованиях.

Не уверен, что они сами знают на нее ответ. Вполне вероятно, что это попытка решить задачку за счет соискателя.
Я тоже подумаю над этой задачкой. У меня сегодня такая-же выползла, только там четыре строки, а делать четыре запроса ломает..
Добавлено @ 22:10
Что-то мне сдается будет вроде этого, но не проверял.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate`

Автор: Kurt 4.9.2005, 22:16
Цитата(Ignat @ 4.9.2005, 22:06)
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate`

Не, не то. Смотри, что получается:
Цитата
mysql> select vdate, vname, vval from mtest group by vname order by vdate;
+------------+-------+------+
| vdate      | vname | vval |
+------------+-------+------+
| 2000-01-02 | USD  | 20.5 |
| 2000-01-04 | EURO  | 20.5 |
+------------+-------+------+
2 rows in set (0.05 sec)


Автор: Akina 5.9.2005, 08:20
Цитата(Perchilla @ 4.9.2005, 20:37)
Работает только в том случае, если курс валют не задан на перед...

WHERE vdate <= CURDATE()

Автор: Ignat 5.9.2005, 09:04
Kurt, не тот я порядок сортировки влепил, виноват.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate`DESC

Автор: Zipo 5.9.2005, 10:48
Цитата(Ignat @ 5.9.2005, 09:04)
Kurt, не тот я порядок сортировки влепил, виноват.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate`DESC

Это логически неправильное решение. Нет смысла делать сортировку после группировки.
Добавлено @ 10:53
Цитата(Kurt @ 4.9.2005, 20:53)
Zipo
Хм.. Ваше решение в MSSQL через процедуру очень интересно. Возьму на вооружение. smile Спасибо. Хотя, конечно, это ограничение:
Цитата
Это конечно при условии, что обновление позиции происходит для всех валют. Т.е. не может быть обновление одной вылюты а потом другой через неделю.

сильно снижает практическое применение такого решения.

Самый главный фактор, что бы не происходило обновление одной валюты чаще чем других. Именно в этом случае процедура отработает неправильно.
В принципе если ставить обновление валют на автомате к примеру с сайта нац. банка, то такая ситуация не произойдет. Не встречал потребностей в ручном обновлении.

Автор: Ignat 5.9.2005, 12:03
Цитата(Zipo @ 5.9.2005, 11:48)
Нет смысла делать сортировку после группировки.

Да ну? Вопрос в том, что будет отправлено клиенту.
Вначале выбираются ряды, группируются (т.е. меняется порядок, а не удаление дубликатов значений столбца), затем в пределах группировки производится сортировка, а затем уже DISTINCT.

для сомневающихся:
Цитата
При использовании выражения GROUP BY строки вывода будут сортироваться в соответствии с порядком, заданным в GROUP BY, - так, как если бы применялось выражение ORDER BY для всех полей, указанных в GROUP BY.

http://dev.mysql.com/doc/mysql/ru/select.html

Zipo, прежде чем назвать чье-то решение неправильным, следует быть уверенным в своей правоте.

Добавлено @ 12:05
Цитата(Akina @ 5.9.2005, 09:20)
WHERE vdate <= CURDATE()

для MySQL это выглядит WHERE vdate <= NOW()

Автор: Akina 5.9.2005, 12:59
Цитата(Ignat @ 5.9.2005, 13:03)
для MySQL это выглядит WHERE vdate <= NOW()

не понял... время-то вроде как не нужно...

Автор: Ignat 5.9.2005, 13:07
Akina, хм... да диалект здесь не при делах.
насколько помню, сравнение в этом случае корректно (date vs datetime). Но по смыслу котировок, могу предположить, что они обновляются куда чаще, чем раз в день smile

Автор: Akina 5.9.2005, 14:06
Ignat
Я исходил из приведенных в инит-посте данных - там нет времени.

Автор: Bikutoru 5.9.2005, 14:11
Ignat, практика показывает, что ты не совсем прав. Проверял на MySQL 3.23.52-log на данных Kurt'a
Запрос 1.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate`;

Результат:
02.01.2000 USD 20,5
04.01.2000 EURO 21,5

Запрос №2.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY `vdate` DESC;

Результат:
04.01.2000 EURO 21,5
02.01.2000 USD 20,5

Запрос №3.
Код

SELECT `vdate`, `vname`, `vval` FROM `mtest` GROUP BY `vname` ORDER BY RAND();

Результат:
04.01.2000 EURO 21,5
02.01.2000 USD 20,5
(меняющиеся друг с другом местами)

Так что
Цитата(Ignat @ 5.9.2005, 13:03)
Вопрос в том, что будет отправлено клиенту

остаётся открытым.


Автор: Ignat 5.9.2005, 14:48
Bikutoru, спасибо.

Zipo, прошу прощения за резкость.

Проверил. Вариант, который у меня заработал:
Код

SELECT * FROM mtest GROUP BY `vname` DESC;

Но не нравится мне он. Очевидно, если поле времени будет заполнено не возрастанием, то результатом будет произвольный порядок. Проверил на 120 записях с группировкой по ~30 значениям.

Автор: Zipo 5.9.2005, 15:16
Ignat:

Все дело в том, что для произведения операции группировки БД необходимо выполнить сортировку по указаному полю для группировки и только после этого БД удаляет дубликаты. Именно по этому в группировке можно указывать направление сортировки (ASC/DESC). Это дает приимущество только в случае если в качестве результата нужно получить сортированные список по полю группировки (т.е. что бы не производить еще 1 операцию сортировки методом ORDER BY).
Вы немного заблудились в реализации алгоритмов БД MySQL.

Цитата
При использовании выражения GROUP BY строки вывода будут сортироваться в соответствии с порядком, заданным в GROUP BY, - так, как если бы применялось выражение ORDER BY для всех полей, указанных в GROUP BY.


Именно об этом говориться в этой цитате.

Цитата
Вначале выбираются ряды, группируются (т.е. меняется порядок, а не удаление дубликатов значений столбца), затем в пределах группировки производится сортировка, а затем уже DISTINCT.


1. Отбираются ряды соотв. условию
2. Сортируются по полям группировки (в указаном направлении ASC/DESC)
3. Удаление дубликатов (DISTINCT)

В приделах групп сортировки не происходит. Все операции происходят в том порядке в котором они написаны в sql выражении. То, что Вы хотите логически неправильно. Этого хотеть не нужно. Абсолютно все БД из соображения скорости будут поступать по указаному мной плану.

Дальше, можете меня хоть застрелить, но я повторюсь:
Это логически неправильное решение. Нет смысла делать сортировку после группировки.

Теперь объясню почему:
ORDER BY всегда будет и выполнялся только после окончательного выполнения GROUP BY (т.е. все дубликаты уже удалены).
Делать сортировку после группировки мне видится логичным только в 1 случае, это в версиях MySQL > 4.0. По полям которые не вошли в группу GROUP BY. Почитайте в этой теме я объяснял логигу группировки MySQL > 4.0. Но это действует только в указаной версии БД, MSSQL уже ругается и выдает ошибку. Но метод реализации группировки в этой БД дает приимущестава, без потери скорости.
Добавлено @ 15:21
Цитата(Ignat @ 5.9.2005, 14:48)
Bikutoru, спасибо.

Zipo, прошу прощения за резкость.

Проверил. Вариант, который у меня заработал:
Код

SELECT * FROM mtest GROUP BY `vname` DESC;

Но не нравится мне он. Очевидно, если поле времени будет заполнено не возрастанием, то результатом будет произвольный порядок. Проверил на 120 записях с группировкой по ~30 значениям.

Этот вариант тоже логически неверен. И работать не будет. Прочитайте мои первые посты в этой теме. Вам должно стать ясно почему так происходит.

Автор: Ignat 5.9.2005, 15:26
2Kurt, перерыл документацию. Судя по всему, то что оттебя хотели:
Код

SELECT * FROM mtest
GROUP BY vname, vdate DESC
GROUP BY vname


Но в MySQL это отпадает. Обидно.
Добавлено @ 15:30
Цитата(Zipo @ 5.9.2005, 16:16)
Этот вариант тоже логически неверен. И работать не будет.

Не сомневаюсь.

Автор: Ignat 5.9.2005, 15:54
http://dev.mysql.com/doc/mysql/ru/example-maximum-column-group-row.html

Автор: Kurt 5.9.2005, 17:08
Цитата(Ignat @ 5.9.2005, 15:26)
2Kurt, перерыл документацию. Судя по всему, то что оттебя хотели:
Код

SELECT * FROM mtest
GROUP BY vname, vdate DESC
GROUP BY vname

Нет. MSSQL ругается:
Цитата
Incorrect syntax near the keyword 'DESC'.

ему второй group by не нравится. smile

Цитата(Akina)
Я исходил из приведенных в инит-посте данных - там нет времени.

Да. Времени там не было. Хотя сейчас понимаю, что по-хорошему должно быть. Но давайте все так же не учитывать время - чтоб совпадало с задачкой на собеседовании.

Автор: Ignat 5.9.2005, 17:10
Kurt, посмотри последний линк. Там хорошо раписано.

Автор: dm9 6.9.2005, 10:08
Или я чего-то не понял, или это трюк "MAX-CONCAT".

Код

SELECT 
LEFT(MAX(CONCAT(vdate, vval)), 10) AS mydate,
vname,
SUBSTRING(MAX(CONCAT(vdate, vval)), 11) AS myval
FROM mtest
GROUP BY vname;


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

http://www.mysql.ru/docs/man/example-Maximum-column-group-row.html

Igant, ты эту ссылку и привёл. Прошу прощения. Надо внимательнее читать.
Но пост удалять не буду, поскольку он содержит готовый запрос...

Автор: Kurt 6.9.2005, 13:56
Ох.. вот он какой - северный олень.. smile
Все понял, всем спасибо. smile
Из всего этого топика я вынес главную мысль - если мне когда-нибудь понадобится хранить историю валют, я буду придумывать какую-нибудь другую структуру.

Автор: Kurt 16.10.2005, 02:00
Недавно мой знакомый нашел простое и очень логичное решение этой задачи для PostgreSQL:
Код

select distinct on (vname) vdate, vname, vval 
from mtest
order by vname, vdate desc

Я удивлен, как все продумано и красиво. smile
Мне начинает нравится эта СУБД. smile

Автор: s 27.10.2005, 10:06
Заинтересовала эта задача. К сожалению с MySQL не работаю, а на MSSQL не проще будет так

Код

declare @t table ( vdate datetime, vname nchar(4), vval money )

insert into @t
    select '2000-01-02', 'USD', 20.5
    union all
    select '2000-01-04', 'EURO', 21.5
    union all
    select '2000-06-04', 'EURO', 25.5
    union all
    select '2001-03-07', 'USD', 30.0
    union all
    select '2005-01-07', 'USD', 17.0
    union all
    select '2005-04-14', 'EURO', 23.0


SELECT vdate, vname, vval FROM @t 
WHERE vdate IN ( SELECT MAX(vdate) AS max_vdate FROM @t GROUP BY vname )

Автор: Ignat 27.10.2005, 10:23
Цитата(s @ 27.10.2005, 11:06)
Заинтересовала эта задача. К сожалению с MySQL не работаю, а на MSSQL не проще будет так

Весь прикол в том, что MYSQL ранее не поддерживала подселекты и хранимки. Следовательно с такими ограничениями решить в один запрос оказывается очень сложно и не рационально.

Автор: Settler 23.4.2008, 01:27
Доброй ночи! Бился сегодня над решением этой задачи, т.к. у себя на сайте нужно было выводить пользователей и кто где находится, только вместо цены были зарегестрированные пользователи, а в место валюты айпиадрес, теперь обновляю и смотрю какую страницу яндекс индексирует))) да и вообще кто где находится))

Вот под задачу вашу запрос будет выглядеть так (я даже удивися что так просто и работает)
Код

$sql_zapros = "SELECT * FROM mtest WHERE vdate > 1 GROUP BY vname ORDER BY vval";
Таким образом таблица
+------------+-------+------+
| vdate      | vname | vval |
+------------+-------+------+
| 2000-01-02 | USD  | 20.5 |
| 2000-01-04 | EURO  | 21.5 |
| 2000-06-04 | EURO  | 25.5 |
| 2001-03-07 | USD  |  30 |
| 2005-01-07 | USD  |  17 |
| 2005-04-14 | EURO  |  23 |
+------------+-------+------+

отгруппируется ПО ДЕНЕЖНОМУ ЗНАКУ (который отсортируется относительно максимума даты) и выведеся это всё по максимальному значению цены и получится

| 2005-04-14 | EURO  |  23 |
| 2005-01-07 | USD  |  17 |


можно выводить относительно даты, в запросе ORDER BY vval меняем на vdate - в данном конкретном примере вывод не поменяется но если строк в таблице много самых разных, то вывод будет другой smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)