为下一个和上一个元素优化查询

Question

我正在寻找在不运行完整查询的情况下检索记录的下一个和上一个记录的最佳方法。我已经有了完全实现的解决方案，并想知道是否有更好的方法来完成这个任务。

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

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

_{(source: pekkagaiser.com)}

显然，“西红柿，一级”的“下一个”按钮在第一个例子中应该是“苹果，一级”，在第二个例子中应该是“梨，一级”，而在第三个例子中则没有。

在详细视图中的任务是确定下一个和上一个项目，而无需每次运行查询，并且仅有列表的排序顺序可用（假设我们通过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
      );

显然，这是一种昂贵的方法，仅适用于有限数量的记录，且会创建冗余数据。但是在现实世界中，创建列表的查询非常耗费时间（确实如此）。在每个详细视图中运行它是不可行的，因此需要进行缓存。

我的问题：

• 您认为查找变化查询顺序的相邻记录是否是一种好的做法？

• 您知道在性能和简单性方面是否有更好的做法吗？您知道什么可以使此方法完全过时吗？

• 在编程理论中，有没有称之为这个问题的名字？

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

• 有没有公认的、常见的模式来解决这个问题？他们被称为什么？

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

如果有什么不清楚的地方，请留言，我会进行澄清。

发起一个悬赏 - 可能还有更多关于这个问题的信息。

- Pekka

---

@Tomalak 啊，太遗憾了！我将在SO上提出一个功能请求。 - Pekka

我花了一些时间才弄清楚真正的问题所在。我认为情况是用户处于详细视图，并希望查看下一条记录，其中“下一个”取决于他之前选择的排序顺序。而且查询已排序列表然后查询下一个记录的详细信息是低效的。相反，您只想查询下一个记录的详细信息。 - Fantius

@Tomalak 这是问题吗？http://meta.stackexchange.com/questions/1777/what-html-tags-are-allowed-on-stack-overflow-server-fault-and-super-user - fncomp

我不清楚您想如何分配资源。数据库查询是否每次只获取5个连续的项目？数据库查询是否获取所有内容，但是排序稍后在结果上执行（这意味着服务器必须缓存结果）？这应该在服务器端还是客户端（JavaScript）上进行？ - Heinrich Apfelmus

将前50个记录的ID和上一条记录的ID缓存到Memcached或其他缓存中，如何看待这种做法？ - Halil Özgür

Answer 1

这里有一个想法。您可以将昂贵的操作转移到超市管理员插入/更新新优惠时进行更新，而不是在最终用户选择要查看的数据时进行更新。这可能看起来像一种非动态处理排序数据的方法，但它可能会增加速度。正如我们所知道的那样，性能和其他编码因素之间总是存在权衡。

创建一个表格，为每个优惠和每个排序选项保存下一个和上一个。(或者，如果您始终拥有三个排序选项，则可以将其存储在优惠表中--查询速度是规范化数据库的一个很好的原因)。

因此，您将拥有以下列：

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

查询从数据库获取优惠详情页面的详细信息时，NextID 和 PrevID 将成为结果的一部分。因此，您只需要为每个详细页面运行一个查询。

每次插入、更新或删除优惠时，您都需要运行一个过程来验证排序类型表的完整性/准确性。

- Jessica

---

这个想法非常有趣，使得概念可以扩展到更大的列表。它需要额外的“清洁工作”（例如删除链中已删除项目的引用等），但这可以在数据更改时处理。非常好，我会考虑一下！ - Pekka

我喜欢这个想法。听起来是触发器/存储过程的好选择。 - poisson

反规范化在这里非常有效。但是，如果您需要对许多不同的项目类型进行过滤和排序，那么它将变得更加复杂。 - cherouvim

这是一个不错的解决方案，但它对于缓存过滤器无效（尽管这不是问题的一部分）。"排序缓存"表结构更适合此用途。细节见上。仍然很棒。 - Rudie

此外，我很好奇除了（查询）速度之外，规范化数据的另一个好理由是什么。 - Rudie

Answer 2

我有一个与Jessica相似的想法。然而，与其存储到下一个和上一个排序项的链接，你可以存储每个排序类型的排序顺序。为了找到前一个或后一个记录，只需获取拥有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的想法少。然而，正如你所意识到的那样，更新一行数据的成本显著更高，因为你必须重新计算和存储所有排序顺序。但是，根据你的情况，如果数据更新很少，特别是如果它们总是批量发生，那么这个方案可能是最好的。

即

once_per_day
  add/delete/update all records
  recalculate sort orders

希望这对您有所帮助。

- Adukra

---

这个解决方案还有一些方便的副作用。1：您可以轻松知道自己是否处于排序列表的头部（sortOrder = 0）或尾部（sortOrder = listLength）。2：您可以轻松地跳过大于1的增量（通过查询具有sortX = currentSort + 5的行来向前跳过5条记录）。 - Adukra

嘿！我们在我的网站http://www.wethepixels.com上使用了类似的方法来浏览列表。我们有许多需要排序的列表，就像这个一样。这种方法非常快速和有效率。我强烈推荐使用这种方法！ - JT703

Answer 3

我也曾经为此而做过噩梦。你目前的方法似乎是最佳解决方案，即使对于包含10k个条目的列表也是如此。将列表视图的ID缓存到HTTP会话中，然后使用它来显示（针对当前用户的）上一个/下一个。特别是当有太多的方式来筛选和排序初始项目列表而不仅仅是3种时，这种方法非常有效。
此外，通过存储整个ID列表，您可以显示一个“您在X/Y处”的增强型文本。

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

直接回答您的问题：

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

- cherouvim

Answer 4

一般来说，我会将数据从索引中去规范化。它们可能存储在同一行中，但我几乎总是先检索我的结果 ID，然后单独获取数据。这使得缓存数据非常简单。在 PHP 中不是很重要，因为延迟低、带宽高，但在具有高延迟、低带宽的应用程序（例如 AJAX 网站，其中许多网站都是使用 JavaScript 渲染）中，这种策略非常有用。

我总是单独缓存结果列表和结果本身。如果任何事情影响了列表查询的结果，则会刷新列表结果的缓存。如果任何事情影响了结果本身，那么特定的结果将被刷新。这使我能够更新任何一个而无需重新生成所有内容，从而实现有效的缓存。

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

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

具体回答您的问题：

- 是的，提前找到邻居或客户端可能下一步访问的任何信息是个好主意，特别是如果成本现在很低，重新计算的成本很高。然后它只是一个额外的预先计算和存储与速度之间的折衷。 - 在性能和简单性方面，避免将逻辑上不同的东西联系在一起。索引和数据是不同的，可能在不同的时间进行更改（例如添加新数据将影响索引，但不会影响现有数据），因此应分别访问它们。从单线程的角度来看，这可能略微效率低下，但每当您将某些东西联系在一起时，就会失去缓存效果和异步性（扩展的关键是异步性）。 - 提前获取数据的术语是预取。预取可以在访问时或在实际需要预取数据之前在后台进行。同样适用于预计算。这是成本、存储成本和获取所需成本的权衡。 - “排序缓存”是一个恰当的名称。 - 我不知道。 - 此外，在缓存时，请尽可能以最通用的级别进行缓存。某些内容可能是特定于用户的（例如搜索查询的结果），而其他内容可能是与用户无关的，例如浏览目录。两者都可以从缓存中受益。目录查询可能很频繁，并每次节省一些，而搜索查询可能很昂贵，并在几次节省了很多。

- Mark Rose

Answer 5

我不确定我是否理解正确，如果不是，请告诉我;)

假设我们已经有了排序列表的查询和当前偏移量，即我们有一个$query和一个$n。

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

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

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

但由于这个解决方案过于简单，我认为自己可能误解了什么。

- NikiC

---

我对没有明显原因和解释就被踩的事情感到非常恼火。 - NikiC

Answer 6

基本假设：

• 特价商品每周更新
• 我们可以预期网站变化不频繁...可能是每天？
• 我们可以通过API或触发器来控制对数据库的更新

如果网站每天都会更改，建议在夜间静态生成所有页面。每个排序顺序的一个查询迭代并创建所有相关页面。即使有动态元素，很可能也可以通过包含静态页面元素来解决它们。这将提供最佳的页面服务和无数据库负载。事实上，您甚至可以生成单独的页面和包含在页面中的上一页/下一页元素。这可能会在200种排序方式时变得更加疯狂，但我非常喜欢它。

?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，等等）。只要你的缓存不超过容量限制，你将可以按照主键的方式从内存中获取简单的值。

这种方法在选择和更新/插入方法上需要一些额外的编码，但应该是相对较少的。最后，你将查询[tomatoes类1的id].price.next。如果这个键存在于缓存中，那么太好了。否则，将其插入缓存并显示。

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

抱歉我的尾随答案有点无用，但我认为我的叙述解决方案应该非常有用。

- Jeff Ferland

Answer 7

有很多种方法可以做到这一点，就像剥一只谚语中的猫皮一样。所以这里是我的一些方法。

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

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

根据需要重新填充第二个表格，使用来自第一个表格的结果，从而保持数据新鲜，但最小化使用昂贵的查询。

或者，如果您想避免甚至连接到数据库，那么您可以将所有数据存储在php数组中，并使用memcached进行存储。这将非常快速，并且只要您的列表不太大，就会节省资源，并且可以轻松排序。

DC

- DeveloperChris

Answer 8

你可以将有序列表的行数保存到视图中，然后可以通过(current_rownum-1)和(current_rownum+1)行号访问列表中前一个和后一个项。

- inf3rno

Answer 9

这个问题/数据结构被称为双向图，或者你可以说你有几个链接列表。

如果你把它看作是一个链接列表，你可以为每个排序和prev/next键添加项目表字段。但数据库管理员会因此而杀了你，就像GOTO一样。

如果你把它看作是一个（双向）图，那么你可以采用Jessica的答案。主要问题在于顺序更新是昂贵的操作。

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

如果您将一个项目的位置更改为新的顺序A、C、B、D，那么您将需要更新4行。

- Beffa

Answer 10

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

我的方法是，在第一次检索数组后对其进行serialize()，然后将其缓存在单独的存储区域中；无论是memcached/APC/硬盘/mongoDb等等，并通过他们的会话数据单独保留其缓存位置详细信息。实际的存储后端自然取决于数组的大小，您没有详细说明，但是memcached可以在多个服务器上扩展，mongo甚至可以在稍微更高的延迟成本下进一步扩展。

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

当用户返回网站时，检查缓存数据的生存时间值并在仍然有效时重复使用它。我还会在INSERT/UPDATE/DELETE上运行触发器以获取特殊优惠信息，只需在单独的表中设置一个时间戳字段。这将立即指示缓存是否过时，并且查询需要重新运行非常低的查询成本。仅使用触发器设置单个字段的好处在于无需担心修剪该表中旧/冗余值。

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

- Matt