Вопрос заключется в том, как легче всего реализовать сабж на форуме.
Тобишь, как показать пользователю, в каких темах появились новые сообщения. Желательно, не применяя для реализации задачи отдельной таблицы БД. Нужно ли для этого установить cookie или специально их не устанавливать... Хотелось бы узнать алгоритм решения...

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

Цитата(Bastet @ 20.10.2005, 22:24)

Мне в голову приходят только дополнительные таблицы

Хорошо, как по вашему мнению их можно оптимально использовать?
Вести статистику для каждой темы, в отдельном поле записывать id пользователей, её посетивших и сбрасывать список при появлении нового сообщения... Или ещё что-нибудь в этом роде ? Тогда поле конечно не переполнится, но сортировка инф-ии займёт уйму времени загрузки скрипта, как и любые аналогичные решения...

Цитата(Bastet @ 20.10.2005, 22:24)

Как вариант - скачай бесплатный скрипт форума и посмотри, как там это реализовано.

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

Dandik

Знаю как сделать просто непрочитанные сообщения прочитанными, если юзер попадает на страницу то в таблице, в строке с его логином в поле read ставиш 1 (0 - непрочитано), от этого и пляши

Bastet

Цитата(Bastet @ 20.10.2005, 23:24)

Как вариант - скачай бесплатный скрипт форума и посмотри, как там это реализовано.

От этого голова распухне вместо кук

Цитата

Знаю как сделать просто непрочитанные сообщения прочитанными, если юзер попадает на страницу то в таблице, в строке с его логином в поле read ставиш 1 (0 - непрочитано), от этого и пляши

Хм, если ты говоришь о его логине, то можно предположить, что говоришь и о таблице всех пользователей со строкой характеризующей данного. Тогда, если у меня на форуме 100 непрочитанных сообщений, то данная одна 1-ка в поле для какого из этих 100 будет действовать ?? Или для всех сразу ? Одной такой 1-ой не обойтись в любом случае...
Хотя может, я тебя не правильно понял, разъясни поподробней...

Dandik

хм... тогда я даже незнаю, да, 1-ка для форума не подойдёт, т.к. топиков много и их количество может меняца, ну тогда попробуй куками. Т.е. если юзер прочитал топик пишеш ему куку что он прочитал, а в следущий раз удаляй старую куку и пиши новую

Оптимальный вариант.
1. Все что старее недели (к примеру) считается либюо все прочитанным, либо наоборот.
2. В поле БД в таблице пользователей пишется поле, куда заносишь прочитанные пользователем темы за период последней недели.

Цитата(Mal @ 22.10.2005, 09:30)

Оптимальный вариант. 1. Все что старее недели (к примеру) считается либюо все прочитанным, либо наоборот. 2. В поле БД в таблице пользователей пишется поле, куда заносишь прочитанные пользователем темы за период последней недели.

Нда, структура того же уровня, на которой я и остановился при решении задачи, только немного оптимальней:
Ведь т.к. перменной величиной в данной ситуации являтся тема, а не пользователь, то логичней было бы работать на стороне темы... По сему я выделил в каждой теме (ну и в форуме соответственно) поле, в которое записываю id посетевших её пользователей, при появлении нового сообщения, я это поле обнуляю... В принципе тоже самое, только если работать на стороне пользователя, то выцепление id обновлённой темы c последующим удалением из списка у каждого пользователя форума (которых может быть оччень много) потребовало бы уйму времени, впрочем это уже не важно... Просто думал, что может есть какой-либо другой способ. К тому же данный занимает немного временых ресурсов и меня в принипе устраивает.
Всем спасибки за ответы.

Куксикус, а никто не говорил, что будет легко. Программирование вообще наука не для средних умов.


Dandik, я представляю это так: есть таблица вида <id_пользователя, id_темы, дата_последнего_просмотра>. Когда пользователь читает тему, соответствующая запись обновляется. Спустя n-ное число недель с момента последнего просмотра записи убиваются.
У темы есть поле, в котором хранится дата последнего обновления (или не хранится, а вычисляется на основе даты последнего поста в ней).
Если дата последнего обновления в первой табличке меньше, чем дата обновления в теме, то топик помечается, как имеющий новые сообщения.

Такие вот мысли. Если что-то непонятно, попробую объяснить подробнее.
Насчет оптимальности варианта не знаю - только что сама придумала...

Bastet, попробуй вникнуть в мой способ (описано выше)... и сравни
Тут дело может быть в том, что:

Цитата

есть таблица вида

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

Цитата

вида <id_пользователя, id_темы, дата_последнего_просмотра>.

Размеры таблицы: кол-во пользователей * кол-во страниц, как-то жестоко это всё...
Вообщем мне, разумеется, всё понятно, просто постарайся вникнуть в мой пост предыдущий, ну или в предожение Mal Hack

Dandik,
возникае проблема:
как ты собираешься выбирать из базы новые темы? Сам-то такой способ очень хорош, но встаёт вопрос о быстродействии.
логичный вариант выборки - делать её с помощью LIKE
теперь представим, что тем много и, даже если сделать текстовый индекс, это вряд ли поможет в плане быстродействия

Цитата

Dandik, возникае проблема: как ты собираешься выбирать из базы новые темы? Сам-то такой способ очень хорош, но встаёт вопрос о быстродействии. логичный вариант выборки - делать её с помощью LIKE теперь представим, что тем много и, даже если сделать текстовый индекс, это вряд ли поможет в плане быстродействия

Хм, если ты находишься на стадии просмотра форумов, то необязательно проверять каждую тему форума, т.к. можно проверить (действительно используя оператор LIKE) поле, выделенное в таблице форумов... Ну а если поле такое создавать не хочешь, то я, например, определил время давности темы ( 2 недели ), если тема старше, то она не удостаивается просмотра и считается просмотренной для любого пользователя.
Если ты заходишь на форум, то достаточно будет проверить те темы, которые находятся на одной странице, максимум 20-25 тобишь...
Я не заметил большую мелительность скрипта из-за этого метода, как на локальном, так и на внешнем хосте...
Тут даже не в этом дело, просто по средствам данной темы я и хотел выяснить способ лучше... но никто ничего лучше не предложил, возожно у тебя есть вариант какой-нибудь?

Цитата

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

сейчас думаю над вариантом с дублированием данных о просмотренных темах в таблице пользователя. Возникает вопрос, для чего нужно дублирование?
просто возникла идея, вернее, пока только вопрос:
будет ли такой запрос:
SELECT ... WHERE thread_id NOT IN (идентификаторы просмотренных пользователем за период тем через запятую) ORDER BY .. -- оффсет с лимитом и т.д.
быстрее того, который с LIKE?

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

Гость_fastkill

Цитата

дублированием данных о просмотренных темах в таблице пользователя

Я уже говорил об этом... Дело в том, что тем всегда получается больше, чем пользователей, сл-но, если ты будешь работать на стороне таблицы пользователя, то поле индификаторов тем будет намого больше у пользователя... Более того, если ты будешь работать с индефикаторами (которые не несут в себе никакой информации о времени создания темы) ты не сможешь их удалять, а значит они будут только накапливаться. Т.е. Тема продёт и забудится, а пользователь будет в активности всегда и в его поле будет храниться инф-я о темах годовалой или более давности (с момента регистрации), каждый раз придётся перепроверять этот никому не нужный груз или реализовывать множество дополнительных запросов для обновления данного поля... Обновление же соответствующего поля на стороне темы очевидно, в момент добавления сообщения тема для всех становится обновлённой, а следоательно и поле обнуляется (Если говорить о поле пользователя , то такое радикальное обновление врят ли может быть спровацированно каким-либо действием)...

Цитата

NOT IN

Скорее всего быстрее, хотя сам я не проверял )

Довольно оптимальным будет текстовое поле в профиле пользователя, размером этак в 2^16 символов + числовое поле в которое записываем идентификатор якоря поста/сообщения. Якорь это самое старое сообщение(скорее всего самое первое на ресурсе).

Каждое сообщение имеет свой идентификатор, с каждым новым сообщением идентификатор увеличиваеться, ID удалённого сообщения не используеться по новой. Это нормальная работа MySQL (и по моему большинства других) БД.

Текстовое поле представляем огроменным битовым полем, где каждый символ это 7 бит, тогда уложимся только в читабельные символы.

Берём id проверяемого сообщения, отнимаем id якоря, делим нацело 7(символ), остаток(номер бита). Проверяем бит, установлен - значит прочитанно.

Естественно текстовое поле не должно быть забито символами, оно растёт постепенно вместе с количеством постов на ресурсе. Спустя время длинную строку сложней обновлять для БД, но всё равно это будет эффективней чем держать списки идентификаторов для каждого пользователя. Да к тому же можно плевать на точность и сдвигать якорь каждые два месяца, одновременно обрезая строку с битами.

Не видел пока ещё реализации этой идеи

Dandik,

Цитата

Дело в том, что тем всегда получается больше, чем пользователей, сл-но, если ты будешь работать на стороне таблицы пользователя, то поле индификаторов тем будет намого больше у пользователя

безусловно. Однако, как это ни странно, суммарная информация будет одинаковой
Хотя, не совсем. Так как тем больше, то их идентификаторы состоят из большего числа цифр, например, если порядок текущего id юзеров 3 (100, 101,... и т.д), то порядок тем будет, скорее всего, на один больше (по моим субъективным наблюдениям) - то есть четырёхсначное число.
Вот здесь и будет проигрыш

Цитата

Более того, если ты будешь работать с индефикаторами (которые не несут в себе никакой информации о времени создания темы) ты не сможешь их удалять, а значит они будут только накапливаться. Т.е. Тема продёт и забудится, а пользователь будет в активности всегда и в его поле будет храниться инф-я о темах годовалой или более давности (с момента регистрации)

но идея заключается также и в том, чтобы при добавлении нового сообщения прибивать соответствующие id-шники тем в поле у юзера. Тогда проблем не будет.
Зато появится новая - проигрыш в производительности при добавлении сообщения. Есть, однако, предположение, что удаление id темы из полей юзеров можно сделать одним запросом при помощи строковых функций MySQL (хотя могу ошибаться).

Цитата

Цитата NOT IN Скорее всего быстрее, хотя сам я не проверял )

у меня по ходу дела возник дурацкий вопрос :
при изпользовании NOT IN (..) в скобках будет в общем случае большой список id-ников. Порядка несколько сотен (предполагаем, что пользователь активно читает форум)
Не повлияет ли такая большая размерность списка на скорость выполнения запроса?

Sardar
оригинально нигде такого не видел
однако, проблема обсуждаемого нами решения - это не столько проблема памяти при хранении id-шников, сколько проблема потери производительности при выводе списка непрочитанных тем для данного юзера. В том решении всё делается одним SQL-запросом, хотя и тормозным
Если я правильно понимаю, надо сначала сформировать из битового представления конкретные id, а потом делать SELECT по NOT IN (список)?

Dandik,
ещё такая идея пришла на ум: в зависимости от степени посещаемости форума среднее число просмотров темы может варьироваться, и чем более популярен ресурс, тем больше будет забиваться поле темы с идентификаторами юзеров, как следствие - дольше будет выполняться поиск при LIKE, то есть имеем снежный ком
а если хранить id тем в поле с пользователями, то в этом случае, ввиду того, что человеку физически будет трудно посмотреть слишком много тем (даже отпетому флудеру ), это поле будет заполнено в среднем постоянным объёмом текста с id-шниками

Цитата

Если я правильно понимаю, надо сначала сформировать из битового представления конкретные id, а потом делать SELECT по NOT IN (список)?

В том то всё и суть что нет Определим логически что пользователь имеет некоторое пространство/мешок в который складываем id'шники прочитанных сообщений.

Обычно это реализуеться таблицей с составным первичным ключём [<id юзера>,<id мессаги>]. Работает достаточно шустро, до тех пор пока не имеем тысячу пользователей и десятки тысячь сообщений (глянь в подвал форума на первой странице для цифр ).

В моём способе реализуеться битовое множество id'шников, которое имеет досаточно малый размер. Поле TEXT в MySQL имеет максимальный размер в 2^16 символов, в битах это (2^16)*7 битов, т.е более 450 тысячь идентификаторов. Т.к. мы ограниченны размером, а мессаг может быть гораздо больше, то есть якорь - это мессага от id которой начинаеться отсчёт нашего битового поля. В итоге в профиле каждого юзера есть всего два поля: TEXT - битовое множество и ID - якорь-идентификатор.

Задача: имеем список мессаг, нужно узнать которые прочитанны, которые нет.
Решение: пробегаемся в цикле для каждой мессаги, ищем её идентификатор в битовом множестве. Если бит установлен - мессага прочитанна. Никаких обращений к БД, только один раз при загрузке профиля грузим и битовое поле.
Если мессага имеет id меньший чем у якоря (очень старая мессага), то обьявляем её прочитанной и наоборот, если id больший чем якорь+длинна_битового_множества, (то видать ты давно не сдвигал якорь ) то считаем мессагу не прочитанной.

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

Цитата

Задача: имеем список мессаг, нужно узнать которые прочитанны, которые нет.

хм.. может, чего-то не так понял, но остались вопросы:
а если список мессаг, которые предположительно (потенциально) могут быть непрочитанными, очень велик(порядка нескольких сотен, а то и тысяч)?
В то время как нам-то надо вывести всего-навсего, допустим, 20 ссылок (если столько наберётся. А так можно и меньше. Если новых нет - выводится "ничего не найдено") на новые сообщения (вернее, на темы с таковыми), плюс, если их реально больше 20, то ссылки на последующие страницы (тоже будут выводиться по 20 штук ссылок)?
Правильно ли я понимаю, что в варианте с битовыми полями надо сначала получить список потенциально-непрочитанных тем?

Гость_fastkill,

Цитата

Однако, как это ни странно, суммарная информация будет одинаковой

Действительно, по всеобщему закону сохранения... и время запросов будет равно, но только в том случае, если одновременно будут проверяться все поля пользователей... чего быть не может... Тобишь мы получим например 1000 полей (из таблицы тем) с 10 идентификаторами пользователей или же 10 полей пользователей с 1000 идентификаторами тем. Но проверять мы будет за один раз 1-о поле (1-о из 1000 или 1-о из 10 не важно, всёравно одно). На лицо выйгрыш времени в проверки короткого текстового поля над длинным.

Цитата

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

Почему же не будет, ведь id не хранят инф-ю о времени, т.ч. одним этим полем не обойтись...

Цитата

при изпользовании NOT IN (..) в скобках будет в общем случае большой список id-ников. Порядка несколько сотен (предполагаем, что пользователь активно читает форум)

так не тебе же вводить это всё от руки Разница здесь только в том, что Во втором случае работа ведётся с числом, а в первом со строой, а строковые функции всегда были, на мой взгляд, медлительней математических...
Sardar ,
Отдельную таблицу для реализации данной функции - слишком много, придётся делать параллельный запрос к этой таблице при входе (не считая запрос пользователя)...
Я так понимаю, что побитовым представлением ты хочешь укоротить запись списка id тем и все (+ флаг времени обновления, для обновления данного битового текстового поля...Кстати не совсем понятно, какими действиями нужно провоцировать скрипт на обновление, неужели обновлять при каждом заходе...). Так вот, если подобное представление нужно лишь для уменьшения веса указанного выше списка, то почему бы таким образом не укоротить список пользователей (который и так не длинный, т.к. мы выяснили, что тем всегда больше, чем пользователей) В поле каждой темы, в этом случае и сработает главное преумущество - простота обновления (обнуление данного списка). Если я, конено правильно понял, хотя скорее нет, т.к не сталкивася с подобного рода хранением инф-и... если это намного выгоднее, то почему всё хранение id не реализовано таким образом ? Расскажи поподробнее про данный метод, каким образом заполнить и считать поле БД, организованное подобным образом..

Цитата(Dandik @ 27.10.2005, 17:45)

Отдельную таблицу для реализации данной функции - слишком много, придётся делать параллельный запрос к этой таблице при входе (не считая запрос пользователя)...

Если это было ко мне, то всё не правильно понято
Вообще чем больше мы знаем о природе данных, тем эффективней можно с ними работать. Например если все новые мессаги получают id больший чем старые(что и происходит), то по идентификатору можно отсортировать по "возрасту" список мессаг.

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

Третье, битовое поле описанное мной выше считываеться один раз. Далее по нему можно узнать всё необходимое. При чём храниться оно может в профиле пользователя (там где логин, пароль и прочая инфа), хотя можно и вынести в отдельную таблицу на связи 1:1.

Если ещё не понятно, то возьми образно в руку число, это будет твой первый идентификатор(самое старое сообщение). Возьми первый бит битового поля и прибавь его к числу в руке, получили следующий идентификатор. Таким образом прибавляя к "якорю" порядковый номер бита, ты "перемещаешся" по идентификаторам, значение же бита указывает состояние, для нас это (не)прочитанно. Естественно что все операции происходять на скриптах(это побитовый сдвиг, деление и деление по модулю очень быстрые операции ), к БД повторю обращаемся один раз при прочтении битового поля.

Больше пояснять не буду, если ещё не ясно, то я бессилен

Цитата(FastKill @ 27.10.2005, 17:35)

Правильно ли я понимаю, что в варианте с битовыми полями надо сначала получить список потенциально-непрочитанных тем?

Зачем мне этот список? Читая обьяснение выше ясно что самое битовое поле это список id'шников мессаг.

Задача: выбрать 50 последних не прочитанных сообщений
Решение:
Найти идентификатор самого последнего сообщения(операция со сложностью O(1) мгновенная)
Находим позицию идентификатора в битовом поле
От позиции читаем биты "назад", записываем идентификаторы биты которых равны 0(не прочитанно)
Когда список наберёт 50 идентификаторов или если битовое поле закончиться, выбираем все идентификаторы из БД.

Думаю на этом примере станет ясно

Sardar, все хорошо, но ты забыл одну весчь: признак прочитанности должен сбрасываться, если в теме появляется новое сообщение. Причем у всех. А поскольку мы наперед не знаем, кто эту тему уже читал, то придется сканировать всех! юзеров. К тому же, учитывая, что мы храним данные в хитром битовом формате, то в самом лучшем случае мы напишем хранимую процедуру, а если таковые не поддерживаются, то придется каждого юзера загружать по очереди, расшифровывать битовый массив - и при необходимости выдирать запись о теме и сохранять обратно в базе. Это, извините, работать просто не будет.

Теперь мое предложение. Я считаю, что идеальный формат хранения - это таблица вида:

Код

create table view_log (   thread_id numeric not null,   user_id numeric not null,   last_viewed datetime not null,   primary key (thread_id, user_id) ) create index idx_vl_user on view_log(user_id); create index idx_vl_last_viewed on view_log(last_viewed);

Теперь оценим количество записей в такой таблице (на примере Винграда). Имеем 50,000 топиков. Каждый топик за все время когда-либо просмотрит, скажем, 100 человек. Это 5 миллионов записей. Не мало, но и не сильно много. Поскольку все поля проиндексированы, то выборки/апдейты будут происходить мгновенно. Но что делать, если пространство у нас ограничено?

А очень просто: нам ведь не нужно вести историю от царя Гороха. Я думаю, журнал посещенных страниц за последний месяц будет вполне приемлемым компромисом. Прикидываем: 100 новых топиков в день на 100 юзеров, которые заглянут в него в течение месяца - итого 10,000 записей. Десять тысяч - это совершенно детский размер, и это, учтем, мы считали для такого популятного и активного форума как Винград.

Теперь рассмотрим типичные операции:

1. Подсветить на странице прочитанные юзером темы как прочитанные

Поскольку тем на странице - ограниченное количество (default=20), то можно легко проитерировать и составить селект вида:

Код

select * from view_log   where user_id = 1234 and thread_id in (123, 234, 345, 456, 567б, ...); -- всего в списке будет 20 топиков

Выполняется за доли секунды.


2. Сбросить признак прочитанности при добавлении в топик нового поста

Для всех, кто когда-либо читал данную тему, она должна стать "непрочитанной":

Код

delete from view_log   where thread_id = 12345;

3. При каждом просмотре темы обновлять время последнего просмотра

Код

update view_log   set last_viewed = sysdate()   where thread_id = 12345 and user_id = 234;

На самом деле время последнего просмотра - признак необязательный, если мы всего лишь хотим иметь информацию "прочитан/непрочитан". Но уж коль скоро мы заморачиваемся с такой таблицей, то почему бы не добавить и дату. Тогда мы элементарно сможем добавить такие полезные фичи (как на Винграде):

- кто сейчас просматривает тему

Код

select * from view_log   where thread_id = 12345     and last_viewed > (sysdate() - 5min)

Логика, конечно, упрощенная (кто заходил за последние 5 минут), но вполне понятная и разумная.

- когда и где юзер был последний раз

Ну и так далее. Пишу подробно, потому что мне скоро самому предстоит делать форум, так что это для меня нечто вроде чернового спека

Ну и, разумеется, интересно было бы услышать здоровую конструктивную критику

Цитата(Stampede @ 27.10.2005, 21:42)

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

Мдям, а я в голове держу список почты, обычное мыло, а не список топов на форуме, звиняюсь

Цитата(Stampede @ 27.10.2005, 21:42)

Это, извините, работать просто не будет.

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

Подумаем как можно всё таки эффективно прикрутить битовое поле к форуму, состоящему из: подфорумов, содержащих топики, содержащие посты (позже увидим что структура форума не важна).

Задача: найти на форуме(таком как этот) все новые топы и свежие форумы. Реализовать кнопку "перейти к первому не прочитанному".

Решение:
Топик содержит посты, каждый новый пост имеет идентификатор больший чем все другие посты в топе(упорядоченны по возрастанию). Это логично, т.к. посты между топиками не передвигаються (перемещаем топы, не посты). При добавлении постов их идентификаторы всегда max_id+1. Не важно что разница между предпоследним и последним постом в топе может быть больше 1.

Тогда берём самый последний пост в топе и проверяем его на битовом поле. Если пост не прочитан, значит топ свежий. Если форум имеет хотя бы один свежий топ, до и форум свежий. Эта вся инфа нужна при листинге форумов и постов.

Теперь как перейти к первому не прочитанному сообщению. Достаём последние 100 идентификаторов постов в топе (это первичные ключи, значение сразу из индекса берёться, без обращения к данным). Ищем с конца списка id первого прочитанного поста.
Если нашли, то следующий id в списке это первый не прочитанный, к нему и идём
Иначе выбираем следующие 100 со смещением от конца. Это редко будет происходить.

Мне нравиться идея

Ребят, я вот до сих пор никак не пойму зачем создавать для этой функции новую таблицу, с полями времени, пользователя, когда можно всё сделать в таблице темы... И по сути сам запрос включить в стандартный запрос на выборку тем из БД, тобишь в цикл вывода тем. В этом случае все временные ресурсы будут затрачены на дополнительном условии в выборке тем (проверка поля длинной, как уже было сказано не более 100 id (в основном менее. т.к. подразумивается частое обнуление поля)). Кстати само обнуление тоже не потребует отдельного запроса, а просто лишь дополнит UPDATE темы при её при обновлении. Отсюда получим, что реализация задачи не потребует ни одного лишнего запроса, ни создания отдельной таблицы...
Вот расскажите мне, тёмному, в чём могут быть минусы данного подхода?