php - 优化下一个和上一个元素的查询

Question

我正在寻找在不运行完整查询的情况下检索记录的下一个和上一个记录的最佳方法。我有一个完全实施的解决方案，并且想知道是否有更好的方法可以做到这一点。

假设我们正在为一个虚构的蔬菜水果商建立一个网站。除了他的 HTML 页面，他每周都想在他的网站上发布一份特别优惠列表。他希望这些报价驻留在实际的数据库表中，并且用户必须能够以三种方式对报价进行排序。

每个项目还必须有一个详细信息页面，其中包含有关报价的更多文本信息以及“上一个”和“下一个”按钮。“上一个”和“下一个”按钮需要根据用户为列表选择的排序指向相邻的条目。

_{（来源：pekkagaiser.com）}

显然，“Tomatoes, Class I”的“下一个”按钮在第一个示例中必须是“Apples, class 1”，在第二个示例中必须是“Pears, class I”，而在第三个示例中没有。

详细视图中的任务是确定下一个和上一个项目，而无需每次都运行查询，将列表的排序顺序作为唯一可用的信息（假设我们通过 GET 参数得到?sort=offeroftheweek_price，并忽略安全隐患） .

显然，简单地将下一个和前一个元素的 ID 作为参数传递是想到的第一个解决方案。毕竟，此时我们已经知道 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列实际上填充了数字 ID。

在详细信息页面中，我现在访问相应的sortingcache记录，获取items列，展开它，搜索当前项目 ID，并返回上一个和下一个邻居。

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

这显然很昂贵，仅适用于有限数量的记录并创建冗余数据，但让我们假设在现实世界中，创建列表的查询非常昂贵（确实如此），在每个详细视图中运行它都没有这个问题，需要一些缓存。

我的问题：

• 您认为这是找出不同查询顺序的相邻记录的好习惯吗？

• 您知道性能和简单性方面的更好做法吗？你知道什么使这完全过时吗？

• 在编程理论中，这个问题有名字吗？

• “排序缓存”这个名称对于这种技术是否合适且易于理解？

• 是否有任何公认的通用模式来解决这个问题？他们叫什么？

注意：我的问题不是关于构建列表，或者如何显示详细视图。这些只是例子。我的问题是在无法重新查询时确定记录邻居的基本功能，以及到达那里的最快和最便宜的方式。

如果有不清楚的地方，请发表评论，我会澄清。

开始赏金 - 也许有更多关于这方面的信息。

Answer 1

这是一个想法。您可以在杂货店插入/更新新商品而不是最终用户选择要查看的数据时将昂贵的操作卸载到更新。这似乎是一种处理排序数据的非动态方式，但它可能会提高速度。而且，正如我们所知，性能和其他编码因素之间总是需要权衡取舍。

创建一个表格来保存每个报价和每个排序选项的下一个和上一个。（或者，如果您始终拥有三个排序选项，您可以将其存储在报价表中——查询速度是非规范化数据库的一个很好的理由）

所以你会有这些列：

• 排序类型（未排序、价格、类别和价格描述）
• 优惠编号
• 上一个 ID
• 下一个 ID

当从数据库中查询商品详细信息页面的详细信息时，NextID 和 PrevID 将成为结果的一部分。因此，每个详细信息页面只需要一个查询。

每次插入、更新或删除商品时，您都需要运行一个流程来验证 sorttype 表的完整性/准确性。

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

这个解决方案会产生非常短的查询时间，并且会比 Jessica 的想法占用更少的磁盘空间。但是，我确信您意识到，更新一行数据的成本明显更高，因为您必须重新计算和存储所有排序顺序。但是，根据您的情况，如果数据更新很少，特别是如果它们总是批量发生，那么这个解决方案可能是最好的。

IE

once_per_day
  add/delete/update all records
  recalculate sort orders

希望这是有用的。

Answer 3

我也和这个做噩梦。即使对于 10k 个项目的列表，您当前的方法似乎也是最佳解决方案。在 http 会话中缓存列表视图的 ID，然后使用它来显示（个性化给当前用户）上一个/下一个。这很有效，特别是当有太多方法来过滤和排序初始项目列表而不是只有 3 种时。
此外，通过存储整个 ID 列表，您可以显示"you are at X out of Y"可用性增强文本。

顺便说一句，这也是JIRA所做的。

直接回答您的问题：

• 是的，这是一种很好的做法，因为当您的过滤器/排序和项目类型变得更复杂时，它可以在不增加任何代码复杂性的情况下进行扩展。我在一个生产系统中使用它，其中包含 250k 条具有“无限”过滤/排序变化的文章。将可缓存的 ID 修剪为 1000 也是一种可能性，因为用户很可能永远不会点击 prev 或 next 超过 500 次（他很可能会返回并细化搜索或分页）。
• 我不知道更好的方法。但是，如果种类有限并且这是一个公共站点（没有http会话），那么我很可能会去规范化。
• 不知道。
• 是的，排序缓存听起来不错。在我的项目中，我将其称为“搜索结果的上一个/下一个”或“搜索结果的导航”。
• 不知道。

Answer 4

一般来说，我对索引中的数据进行非规范化。它们可能存储在相同的行中，但我几乎总是检索我的结果 ID，然后对数据进行单独的旅行。这使得缓存数据非常简单。在延迟低且带宽高的 PHP 中，它并不那么重要，但是当您有一个高延迟、低带宽的应用程序时，这种策略非常有用，例如一个 AJAX 网站，其中大部分网站都是用 JavaScript 呈现的。

我总是分别缓存结果列表和结果本身。如果有任何事情影响列表查询的结果，则会刷新列表结果的缓存。如果有任何事情影响结果本身，则会刷新这些特定结果。这使我无需重新生成所有内容即可更新其中任何一个，从而实现有效的缓存。

由于我的结果列表很少更改，因此我会同时生成所有列表。这可能会使初始响应稍微慢一些，但它简化了缓存刷新（所有列表都存储在单个缓存条目中）。

因为我已经缓存了整个列表，所以无需重新访问数据库就可以轻松找到相邻项目。幸运的是，这些项目的数据也将被缓存。这在 JavaScript 中对数据进行排序时特别方便。如果我已经在客户端缓存了一个副本，我可以立即采取行动。

具体回答您的问题：

• 是的，提前找出邻居或客户接下来可能访问的任何信息是一个绝妙的主意，尤其是在现在成本低且重新计算成本高的情况下。然后，它只是在额外的预先计算和存储与速度之间进行权衡。
• 在性能和简单性方面，避免将逻辑上不同的事物捆绑在一起。索引和数据不同，可能会在不同的时间发生变化（例如添加新数据会影响索引，但不会影响现有数据），因此应该单独访问。从单线程的角度来看，这可能效率稍低，但是每次将某些东西捆绑在一起时，都会失去缓存的有效性和异步性（扩展的关键是异步性）。
• 提前获取数据的术语是预取。预取可以在访问时或在后台发生，但在实际需要预取数据之前。预计算也是如此。现在需要权衡成本、存储成本和在需要时获取的成本。
• “排序缓存”是一个恰当的名称。
• 我不知道。

此外，当您缓存内容时，请尽可能以最通用的级别缓存它们。有些内容可能是用户特定的（例如搜索查询的结果），而其他内容可能与用户无关，例如浏览目录。两者都可以从缓存中受益。目录查询可能很频繁，每次节省一点，而搜索查询可能很昂贵，几次节省很多。

Answer 5

我不确定我是否理解正确，所以如果没有，请告诉我；）

假设，给定的是排序列表的查询和该列表中的当前偏移量，即我们有 a$query和 an $n。

最小化查询的一个非常明显的解决方案是一次获取所有数据：

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

该语句以当前排序顺序从数据库中获取前一个、当前和下一个元素，并将相关信息放入相应的变量中。

但是由于这个解决方案太简单了，我想我误解了一些东西。

Answer 6

有很多方法可以做到这一点，就像给众所周知的猫剥皮一样。所以这是我的几个。

如果您的原始查询很昂贵（如您所说），那么创建另一个表，可能是一个内存表，用您的昂贵且很少运行主查询的结果填充它。

然后可以在每个视图上查询第二个表，排序就像设置适当的排序顺序一样简单。

根据需要，使用第一个表中的结果重新填充第二个表，从而保持数据新鲜，但最大限度地减少昂贵查询的使用。

或者，如果您想避免连接到数据库，那么您可以将所有数据存储在一个 php 数组中并使用 memcached 存储它。这将非常快，并且如果您的列表不是太大，那么资源效率会很高。并且可以轻松排序。

直流

Answer 7

抱歉，如果我误解了，但我认为您希望在用户访问服务器之间保留有序列表。如果是这样，您的答案很可能在于您的缓存策略和技术，而不是数据库查询/架构优化。

我的方法是在第一次检索到数组后对其进行序列化（），然后将其缓存到单独的存储区域；无论是 memcached/APC/hard-drive/mongoDb/ 等，并通过他们的会话数据单独为每个用户保留其缓存位置详细信息。实际的存储后端自然取决于阵列的大小，您不会对此进行详细介绍，但是 memcached 可以在多个服务器上很好地扩展，而 mongo 甚至可以进一步扩展，但延迟成本会稍高一些。

您也没有指出现实世界中有多少排序排列；例如，您是否需要为每个用户缓存单独的列表，或者您是否可以按排序排列全局缓存，然后通过 PHP 过滤掉您不需要的内容？在您给出的示例中，我将简单地缓存两个排列并将我需要 unserialize() 的两个排列存储在会话数据中。

当用户返回站点时，检查缓存数据的生存时间值，如果仍然有效，则重新使用它。我还会在 INSERT/UPDATE/DELETE 上运行一个触发器，用于仅在单独的表中设置时间戳字段的特价商品。这将立即指示缓存是否过时并且需要以非常低的查询成本重新运行查询。仅使用触发器设置单个字段的好处是无需担心从该表中删除旧/冗余值。

这是否合适取决于返回数据的大小、修改频率以及服务器上可用的缓存技术。

Answer 8

The problem / datastructur is named bi-directional graph or you could say you've got several linked lists.

If you think of it as a linked list, you could just add fields to the items table for every sorting and prev / next key. But the DB Person will kill you for that, it's like GOTO.

If you think of it as a (bi-)directional graph, you go with Jessica's answer. The main problem there is that order updates are expensive operations.

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

If you change one items position to the new order A, C, B, D, you will have to update 4 rows.

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 在这类事情上很受欢迎（双关语！）。当某些内容被推送到数据库时，您可以发出触发器以使用正确的值更新缓存。以与您的更新项目存在于 3 个链接列表中相同的方式执行此操作——根据需要重新链接（this.next.prev = this.prev 等）。从那时起，只要您的缓存没有溢出，您就会以主键的方式从内存中提取简单的值。

此方法将在 select 和 update / insert 方法上进行一些额外的编码，但它应该是相当少的。最后，你会抬头看[id of tomatoes class 1].price.next。如果该密钥在您的缓存中，则为黄金。如果没有，插入缓存并显示。

• 您认为这是找出不同查询顺序的相邻记录的好习惯吗？是的。对预期的即将到来的请求执行前瞻是明智的。
• 您知道性能和简单性方面的更好做法吗？你知道什么使这完全过时吗？希望以上
• 在编程理论中，这个问题有名字吗？优化？
• “排序缓存”这个名称对于这种技术是否合适且易于理解？我不确定具体的合适名称。它是缓存，它是一种缓存，但我不确定告诉我你有一个“排序缓存”会立即传达理解。
• 是否有任何公认的通用模式来解决这个问题？他们叫什么？缓存？

抱歉，我的拖尾答案有点没用，但我认为我的叙述解决方案应该很有用。

Answer 10

您可以将有序列表的行号保存到views中，您可以在 (current_rownum-1) 和 (current_rownum+1) 行号下访问列表中的上一个和下一个项目。

Answer 11

所以你有两个任务：

1. 构建排序的项目列表（具有不同 ORDER BY 的 SELECT）
2. 显示每个项目的详细信息（从可能缓存的数据库中选择详细信息）。

问题是什么？

PS：如果有序列表可能太大，您只需要实现 PAGER 功能。可能有不同的实现，例如您可能希望将“LIMIT 5”添加到查询中并提供“显示下一个 5”按钮。按下此按钮时，会添加“WHERE price < 0.89 LIMIT 5”之类的条件。