Оптимизация запросов для следующего и предыдущего элементов

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

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

Каждый элемент также должен иметь страницу с подробной текстовой информацией о предложении и кнопками "предыдущий" и "следующий". Кнопки "предыдущий" и "следующий" должны указывать на соседние записи в зависимости от сортировки, выбранной пользователем для списка.

_{(источник: pekkagaiser.com)}

Очевидно, что кнопка "Далее" для "Помидоры, класс I" должна быть "Яблоки, класс 1" в первом примере, "Груши, класс I" во втором и ни одной в третьем.

Задача в подробном представлении состоит в том, чтобы определить следующий и предыдущий элементы без выполнения запроса каждый раз с порядком сортировки списка в качестве единственной доступной информации (допустим, мы получаем это через параметр GET ?sort=offeroftheweek_price и игнорируем последствия для безопасности).

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

Мой текущий подход в моей CMS использует то, что я назвал "сортировочный кеш". Когда список загружен, я сохраняю позиции элементов в записях в таблице с именем sortingcache.

name (VARCHAR)             items (TEXT)

offeroftheweek_unsorted    Lettuce; Tomatoes; Apples I; Apples II; Pears
offeroftheweek_price       Tomatoes;Pears;Apples I; Apples II; Lettuce
offeroftheweek_class_asc   Apples II;Lettuce;Apples;Pears;Tomatoes

очевидно, столбец items действительно заполнен числовыми идентификаторами.

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

array("current"   => "Tomatoes",
      "next"      => "Pears",
      "previous"  => null
      );

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

Мои вопросы:

Как вы думаете, это хорошая практика, чтобы найти соседние записи для различных порядков запросов?
Знаете ли вы лучшие практики с точки зрения производительности и простоты? Знаете ли вы что-то, что делает это полностью устаревшим?
В теории программирования есть имя для этой проблемы?
Является ли название "Кэш сортировки" подходящим и понятным для данной техники?
Существуют ли общепризнанные, общие модели для решения этой проблемы? Как они называются?

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

Если что-то неясно, пожалуйста, оставьте комментарий, и я уточню.

Начиная щедрость - может быть, есть еще какая-то информация об этом там.

Ответ 1

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

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

Итак, у вас будут следующие столбцы:

Тип сортировки (без сортировки, цены, класса и цены)
Идентификатор предложения
Prev ID
Следующий идентификатор

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

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

Ответ 2

У меня есть идея, немного похожая на Джессику. Однако вместо сохранения ссылок на следующий и предыдущий элементы сортировки вы сохраняете порядок сортировки для каждого типа сортировки. Чтобы найти предыдущую или следующую запись, просто введите строку с SortX = currentSort ++ или SortX = currentSort -.

Пример:

Type     Class Price Sort1  Sort2 Sort3
Lettuce  2     0.89  0      4     0
Tomatoes 1     1.50  1      0     4
Apples   1     1.10  2      2     2
Apples   2     0.95  3      3     1
Pears    1     1.25  4      1     3

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

то есть.

once_per_day
  add/delete/update all records
  recalculate sort orders

Надеюсь, это полезно.

Ответ 3

У меня были и кошмары с этим. Ваш текущий подход, по-видимому, является лучшим решением даже для списков из 10 тыс. Предметов. Кэширование идентификаторов представления списка в сеансе http, а затем использование этого для отображения (персонализированного для текущего пользователя) предыдущего/следующего. Это хорошо работает, особенно когда существует слишком много способов фильтрации и сортировки исходного списка элементов, а не только 3.
Кроме того, сохраняя список всех идентификаторов, вы получаете текст "you are at X out of Y", расширяющий удобство использования.

Кстати, это то, что делает JIRA.

Чтобы ответить на ваши вопросы:

Да, это хорошая практика, потому что она масштабируется без какой-либо дополнительной сложности кода, когда ваш фильтр/сортировка и типы элементов сложнее. Я использую его в производственной системе с 250-килограммовыми статьями с "бесконечными" фильтрами/вариантами сортировки. Обрезка кэшируемых идентификаторов до 1000 также возможна, так как пользователь, скорее всего, никогда не нажмет на предыдущую или следующую более 500 раз (он, скорее всего, вернется и уточнит поиск или paginate).
Я не знаю лучшего способа. Но если виды, где они ограничены, и это был общедоступный сайт (без сеанса http), то я, скорее всего, денормализую.
Незнайка.
Да, сортировка кеша звучит хорошо. В моем проекте я называю это "предыдущий/следующий по результатам поиска" или "навигация по результатам поиска".
Незнайка.

Ответ 4

В общем, я денормализую данные из индексов. Они могут храниться в одних и тех же строках, но я почти всегда извлекаю идентификаторы результатов, а затем делаю отдельную поездку для данных. Это делает кеширование данных очень простым. Это не так важно в PHP, где латентность низкая и пропускная способность высокая, но такая стратегия очень полезна, когда у вас есть приложение с высокой пропускной способностью с низкой пропускной способностью, такое как веб-сайт AJAX, где большая часть сайта отображается в JavaScript.

Я всегда кэширую списки результатов и результаты сами по себе. Если что-либо влияет на результаты запроса списка, кеш результатов списка обновляется. Если что-то влияет на результаты сами, эти конкретные результаты обновляются. Это позволяет мне обновлять один из них без необходимости регенерировать все, что приводит к эффективному кэшированию.

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

Поскольку у меня есть весь список, кешированный, тривиально найти соседние элементы, не пересматривая базу данных. Если повезет, данные для этих элементов также будут кэшироваться. Это особенно удобно при сортировке данных в JavaScript. Если у меня уже есть копия, кэшированная на клиенте, я могу прибегнуть мгновенно.

Чтобы ответить на ваши вопросы конкретно:

Да, это фантастическая идея, чтобы узнать соседей раньше времени или любую информацию, к которой клиент, скорее всего, получит доступ, особенно если стоимость сейчас низкая, а стоимость пересчета высока. Тогда это просто компромисс между дополнительными предварительными расчетами и хранением по сравнению с скоростью.
С точки зрения производительности и простоты избегайте связывания вещей, которые являются логически разными. Индексы и данные отличаются друг от друга, скорее всего, будут изменены в разное время (например, добавление новой базы данных повлияет на индексы, но не на существующие данные), и, следовательно, их следует получить отдельно. Это может быть немного менее эффективным с однопоточной точки зрения, но каждый раз, когда вы связываете что-то вместе, вы теряете эффективность кеширования и асинхронность (ключ к масштабированию - асинхронность).
Термин для получения данных заблаговременно - это предварительная выборка. Предварительная выборка может произойти во время доступа или в фоновом режиме, но до того, как на самом деле необходимы предварительно выбранные данные. Аналогично с предварительным расчетом. Это компромисс между стоимостью, стоимостью хранения и стоимостью при необходимости.
"Сортировка кеша" - это имя apt.
Я не знаю.

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

Ответ 5

Я не уверен, правильно ли я понял, так что если нет, просто скажите мне;)

Скажем, что givens являются запросом для отсортированного списка и текущего смещения в этом списке, то есть мы имеем $query и $n.

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

list($prev, $current, $next) = DB::q($query . ' LIMIT ?i, 3', $n - 1)->fetchAll(PDO::FETCH_NUM);

Этот оператор извлекает предыдущий, текущий и следующий элементы из базы данных в текущем порядке сортировки и помещает связанную информацию в соответствующие переменные.

Но поскольку это решение слишком просто, я предполагаю, что я что-то не понял.

Ответ 6

Существует так много способов сделать это, как для кожи пресловутого кота. Итак, вот пара моих.

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

Затем эту вторую таблицу можно запросить на каждом представлении, а сортировка будет такой же простой, как установка соответствующего порядка сортировки.

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

В качестве альтернативы, если вы хотите избежать соединения с db, вы можете сохранить все данные в массиве php и сохранить его с помощью memcached. это будет очень быстро и при условии, что ваши списки не слишком велики, будет ресурсоэффективным. и может быть легко отсортирована.

Ответ 7

Основные допущения:

Скидки еженедельно
Мы можем ожидать, что сайт изменится нечасто... возможно, ежедневно?
Мы можем контролировать обновления базы данных с помощью эфира API или отвечать через триггеры

Если сайт меняется ежедневно, я предлагаю, чтобы все страницы статически генерировались в одночасье. Один запрос для каждого порядка сортировки выполняет итерацию и делает все связанные страницы. Даже если есть динамические элементы, есть вероятность, что вы можете адресовать их, включив в них элементы статической страницы. Это обеспечит оптимальное обслуживание страниц и отсутствие загрузки базы данных. Фактически, вы могли бы создать отдельные страницы и предыдущие/следующие элементы, которые включены в страницы. Это может быть более сумасшедшим с 200 способами сортировки, но с 3 я большой поклонник этого.

?sort=price
include(/sorts/$sort/tomatoes_class_1)
/*tomatoes_class_1 is probably a numeric id; sanitize your sort key... use numerics?*/

Если по какой-то причине это невозможно, я прибегаю к запоминанию. Memcache популярен для такого рода вещей (каламбур!). Когда что-то подталкивается к базе данных, вы можете выпустить триггер для обновления кеша с правильными значениями. Сделайте это таким же образом, как если бы ваш обновленный элемент существовал в 3 связанных списках - переименуйте соответственно (this.next.prev = this.prev и т.д.). Из-за этого, пока ваш кеш не переполняется, вы будете вытаскивать простые значения из памяти в первичном ключе.

Этот метод потребует некоторого дополнительного кодирования для методов выбора и обновления/вставки, но он должен быть довольно минимальным. В итоге вы будете искать [id of tomatoes class 1].price.next. Если этот ключ находится в вашем кеше, то золотой. Если нет, вставьте в кеш и покажите.

Считаете ли вы, что это хорошая практика для поиска соседних записей для разных запросов? Да. Целесообразно выполнять прогноз ожидаемых предстоящих запросов.
Знаете ли вы лучшие практики с точки зрения производительности и простоты? Знаете ли вы что-то, что делает это полностью устаревшим? Надеюсь, что выше.
В теории программирования есть ли название этой проблемы? Оптимизация?
Является ли имя "Сортировочный кэш" подходящим и понятным для этой техники? Я не уверен в конкретном подходящем имени. Это кеширование, это кеш-ролик, но я не уверен, что говорю, что у вас есть "сортировочный кеш", который передаст мгновенное понимание.
Есть ли признанные общие шаблоны для решения этой проблемы? Как они называются? Кэширование?

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

Ответ 8

Вы можете сохранить номера строк упорядоченных списков в views, и вы можете достигнуть предыдущего и следующего элементов в списке под (current_rownum-1) и (current_rownum + 1) номера строк.

Ответ 9

Проблема/datastructur называется двунаправленным графиком или вы можете сказать, что у вас есть несколько связанных списков.

Если вы считаете это связанным списком, вы можете просто добавить поля в таблицу элементов для каждой сортировки и предыдущего/следующего ключа. Но DB Person убьет вас за это, как GOTO.

Если вы думаете о нем как (би-) направленном графике, вы идете с ответом Джессики. Основная проблема заключается в том, что обновления заказов - дорогостоящие операции.

 Item Next Prev
   A   B     -
   B   C     A
   C   D     B
   ...

Если вы измените позицию одного элемента на новый порядок A, C, B, D, вам нужно будет обновить 4 строки.

Ответ 10

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

Мой подход состоял бы в том, чтобы сериализовать() массив после его первого поиска, а затем кэшировать его в отдельную область хранения; будь то memcached/APC/hard-drive/mongoDb/и т.д. и сохраняют свои данные о местоположении кэша для каждого пользователя отдельно через свои данные сеанса. Фактический объем хранилища, естественно, будет зависеть от размера массива, о котором вы подробно не рассказываете, но memcached масштабируется на нескольких серверах и mongo еще больше при немного большей задержке.

Вы также не указываете, сколько перестановок сортировки есть в реальном мире; например вам нужно кэшировать отдельные списки для каждого пользователя или вы можете глобально кэшировать на сортировку сортировки, а затем отфильтровывать то, что вам не нужно с помощью PHP?. В примере, который вы даете, я просто кэширую обе перестановки и сохраняю, какой из двух я нуждался в unserialize() в данных сеанса.

Когда пользователь вернется на сайт, проверьте значение Time To Live кэшированных данных и повторно используйте его, если они все еще действительны. У меня также есть триггер, запущенный на INSERT/UPDATE/DELETE для специальных предложений, которые просто устанавливают поле метки времени в отдельной таблице. Это немедленно укажет, был ли кеш устаревшим, а запрос нужно повторно запустить для очень низкой стоимости запроса. Самое замечательное в использовании триггера для установки одного поля - не нужно беспокоиться об обрезке старых/избыточных значений из этой таблицы.

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

Ответ 11

Итак, у вас есть две задачи:

построить отсортированный список элементов (SELECT с разными ORDER BY)
Показать сведения о каждом элементе (SELECT детали из базы данных с возможным кэшированием).

В чем проблема?

PS: если упорядоченный список может быть слишком большим, вам просто нужна функциональность PAGER. Могут быть разные реализации, например. вы можете добавить "LIMIT 5" в запрос и предоставить кнопку "Показать следующие 5". Когда эта кнопка нажата, добавляется условие "Цена WHERE < 0.89 LIMIT 5".