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

Question

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

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

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

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

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

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

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

Мой текущий подход в моей 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, извлекаю столбец items, анализирую его, ищу идентификатор текущего элемента и возвращаю предыдущего и следующего соседа.

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

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

Мои вопросы:

• Как вы думаете, является ли хорошей практикой поиск соседних записей для различных порядков запросов?

• Знаете ли вы лучшие практики с точки зрения производительности и простоты? Знаете ли вы что-то, что делает это полностью устаревшим?

• В теории программирования есть имя для этой проблемы?

• Подходит ли и понятно ли название "Кэш сортировки" для этой техники?

• Существуют ли какие-либо общепринятые модели для решения этой проблемы? Как они называются?

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

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

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

Answer 1

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

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

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

• Тип сортировки (несортированный, цена, класс и цена)
• Предложение ID
• Предыдущий ID
• Следующий ID

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

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

Answer 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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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

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

Answer 8

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

Answer 9

Основные предположения:

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

Если сайт меняется ежедневно, я предлагаю, чтобы все страницы генерировались статически за одну ночь. Один запрос для каждого порядка сортировки перебирает и создает все связанные страницы. Даже если есть динамические элементы, есть вероятность, что вы можете обратиться к ним, включив статические элементы страницы. Это обеспечит оптимальный сервис страниц и не будет загружать базу данных. Фактически, вы можете создать отдельные страницы и элементы prev / next, которые будут включены в страницы. Это может быть сумасшедшим с 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 популярен для такого рода вещей (каламбур!). Когда что-то передается в базу данных, вы можете запустить триггер, чтобы обновить кеш с правильными значениями. Сделайте это так же, как если бы ваш обновленный элемент существовал в трех связанных списках - при необходимости измените связь (this.next.prev = this.prev и т. Д.). Исходя из этого, до тех пор, пока ваш кэш не переполнится, вы будете извлекать простые значения из памяти в виде первичного ключа.

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

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

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

Answer 10

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

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

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

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

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

DC