Xpoint
   [напомнить пароль]

Выбрать следующий/предыдущий элемент в произвольно сортированном списке

Метки: [без меток]
2011-04-18 02:49:33 [обр] lavan(0/7)[досье]

Требуется решить задачу в общем виде для выборки следующего/предыдущего элемента списка.

Предположим у нас есть список

SELECT id FROM table ORDER BY a [DESC|ASC], b [DESC|ASC], c [DESC|ASC];

Требуется найти id_next, id_prev которые являются следующим/предыдущим для данного id из этого списка.
В Интернете есть решения для простого случая, когда есть сортировка по одному числовому полю, это не интересно.

На практике у меня есть таблица новостей, которая сортируется сразу по трём параметрам: по типу новости (FIXED|HOT|NORMAL), дате в обратном порядке
и уникальному id (на случай, если даты совпадают).

Не предлагать делать выборку всего списка и искать в этом списке соседей, хочу узнать у экспертов, есть ли (быстрое) решение на SQL.

Спасибо за ответы, полагаю задача встречалась многим.

спустя 7 часов [обр] Филипп Ткачев(0/115)[досье]
Вам необходимо менять сортировку и добавить условия выборки для поля id и классический LIMIT 1 в конец.
Для вашей задачи даже есть вроде бы готовый паттерн. Поищите книгу http://www.amazon.com/SQL-Desi......rogramming-Focus/dp/0977671542
Она должна помочь.
спустя 4 минуты [обр] Филипп Ткачев(0/115)[досье]

Смысл примерно такой:

$br_id - текущий id

следующий

SELECT * FROM news WHERE news.id > $br_id ORDER BY news.id LIMIT 1

предыдущий

SELECT * FROM news WHERE news.id < $br_id ORDER BY news.id DESC LIMIT 1
спустя 47 минут [обр] Thirteensmay(0/157)[досье]

lavan[досье] В общем виде для этого существуют оконные функции.

select id,
lag(id) over (order by col1, col2) as previd,
lead(id) over (order by col1, col2) as nextid
from mytable

Но они поддерживаются не всеми СУБД, в частности не поддерживаются MySQL, но поддерживаются PostgreSQL, Oracle, MSSQL.
См. например http://www.postgresql.org/docs/9.0/static/functions-window.html

Другого варианта средствами чистого SQL насколько я знаю нет.

спустя 9 часов [обр] lavan(0/7)[досье]

В итоге получился такой запрос для id_next :

SELECT id FROM table WHERE a > 'A' OR (a = 'A' AND (b < 'B' OR (b = 'B' AND c < 'C')))
ORDER a ASC, b DESC, c DESC 
LIMIT 1;

где A, B, C - значения полей для текущего id.

Остаётся вопрос, на сколько это производительно по сравнению с выборкой всего списка и поиска в массиве значения.
Спасибо за LAG OVER, будем ждать в новых версиях MySQL.

спустя 3 часа 11 минут [обр] Thirteensmay(0/157)[досье]
С точки зрения производительности на мой взгляд все нормально, эти условия будут выполняться быстро, основной затык в сортировке а она будет полюбому. Оконные функции не будут быстрее, приблизительно одинаково, если только не просчитывать все сразу, их плюс скорее в понятности и технологичности, там вообще много фишек можно делать. А вот выгребать данные в скрипт и перебирать там - писец, я бы даже и смотреть не стал, куча накладных расходов. Тут может быть другой вариант, перебрать в хранимой процедуре, но у мускуля, а я так понял у вас он, с этим тоже не все гладко, впрочем процедуру перебора написать можно. По идее она не должна быть сильно медленнее вашего запроса и оконных функций, но запросов вполне возможно придется выполнять несколько а в хранимке оба значения можно выяснить за один проход, в результате может получится быстрее, не знаю как в мускуле, в старших базах хранимки обычно компилируются в машинный код и выполняются неотрывно от сервера, со всеми вытекающими. Но вообще я бы не парился, то что у вас есть вполне нормально, в любом случае это все несколько миллисекунд плюс минус, за исключением перебора во внешнем скрипте ;)
спустя 14 минут [обр] Thirteensmay(0/157)[досье]
Кстати, если таки жаба со скоростью вас заест, сортировка фиксированная, и вы можете дополнить структуру базы и алгоритм заполнения, то можно предусмотреть для сортировки отдельное уникальное числовое поле с индексом, и заполнять его соответствующим образом при занесении записи, тогда будет максимально быстро ;)
спустя 53 минуты [обр] Thirteensmay(0/157)[досье]
Ну или даже несколько таких полей, для нескольких наиболее типичных сортировок, а что не в них то вышеприведенным способом
спустя 12 часов [обр] Филипп Ткачев(0/115)[досье]
IMHO, можно ограничиться составным индексом по сортируемым полям.
Powered by POEM™ Engine Copyright © 2002-2005