爲下一個元素和上一個元素優化查詢

Question

我正在尋找檢索記錄的下一個和上一個記錄而不運行完整查詢的最佳方法。我有一個完全實施的解決方案，並想知道是否有更好的方法來做到這一點。

假設我們正在爲虛構的蔬菜水果店建立一個網站。除了他的HTML頁面，他每週都想在自己的網站上發佈一系列特別優惠。他希望這些報價位於實際的數據庫表中，用戶必須能夠通過三種方式對報價進行分類。

每個項目還必須有一個詳細信息頁面，其中提供了更多的文字信息以及「上一個」和「下一個」按鈕。取決於用戶爲列表選擇的排序，「上一個」和「下一個」按鈕需要指向相鄰條目。

alt text http://www.pekkagaiser.com/stuff/Sort.gif?

顯然，「下一個」按鈕「西紅柿，I類」必須「蘋果，類1」，在第一個例子中，「梨，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

所以，你有兩個任務：項目（選擇具有不同的ORDER BY）

1. 構建排序列表
2. 顯示每個項目的詳細信息（從與可能的緩存數據庫的詳細信息）。

什麼問題？

PS：如果有序列表可能太大，您只需要實現PAGER功能。可能有不同的實現，例如您可能希望將「限制5」添加到查詢中並提供「顯示下一個5」按鈕。按下該按鈕時，添加「WHERE price < 0.89 LIMIT 5」等條件。

Answer 2

這是一個想法。當雜貨商插入/更新新報價時，而不是在最終用戶選擇要查看的數據時，您可以將昂貴的操作卸載到更新中。這看起來像是一種處理排序數據的非動態方式，但它可能會提高速度。而且，正如我們所知，性能和其他編碼因素之間總是存在折衷。

創建一個表來容納每個優惠和每個排序選項的下一個和上一個。 （或者，您也可以存儲在這個報價表，如果你將永遠有三個排序選項 - 查詢速度是一個很好的理由進行非規範化數據庫）

所以，你將有這些列：

• 排序型（未排序，價錢，類和價格說明）
• 要約ID
• 上一頁ID
• 一張ID

當從數據庫查詢商品詳情頁面的詳細信息時，NextID和PrevID將成爲結果的一部分。因此，每個詳細信息頁面只需要一個查詢。

每次插入，更新或刪除商品時，都需要運行驗證sorttype表的完整性/準確性的流程。

Answer 3

我不知道我是否理解正確的，所以如果沒有，就請告訴我;）

假設，認爲吉文斯是排序列表中查詢和當前在該列表中的偏移，即我們有$query和$n。

一個很明顯的解決方案，以儘量減少查詢，將是一次獲取所有數據：

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

這份聲明取以前，目前並從數據庫在當前排序順序的下一個元素並將關聯的信息放入相應的變量中。

但是，由於這個解決方案太簡單了，我以爲我誤解了一些東西。

Answer 4

我也曾經做過這個惡夢。即使對於10k項目列表，您目前的方法似乎也是最好的解決方案。在http會話中緩存列表視圖的ID，然後使用它顯示（個性化到當前用戶）previous/next。這種方式效果很好，特別是在過濾和排序項目的初始列表而不僅僅是3的方法過多時。
此外，通過存儲整個ID列表，您可以顯示"you are at X out of Y"可用性增強文本。

順便說一下，這也是JIRA所做的。

直接回答你的問題：

• 是的，這是很好的做法，因爲它擴展不含任何添加代碼的複雜性，當你的過濾器/排序和項目類型烏鴉更加複雜。我將它用於帶有「無限」過濾器/排序變化的250k產品的生產系統中。將可緩存ID修改爲1000也是一種可能性，因爲用戶很可能永遠不會點擊prev或下一次超過500次（他很可能會返回並細化搜索或分頁）。
• 我不知道更好的方法。但如果有限的這種類型是一個公共站點（沒有http會話），那麼我很可能反規範化。
• Dunno。
• 是的，排序緩存聽起來不錯。在我的項目中，我稱之爲「上一個/下一個搜索結果」或「搜索結果導航」。
• Dunno。

Answer 5

一般來說，我將索引中的數據非規範化。它們可能存儲在相同的行中，但我幾乎總是檢索我的結果ID，然後爲數據單獨行程。這使緩存數據變得非常簡單。在PHP中延遲較低且帶寬較高的情況下，這一點並不重要，但如果您有高延遲，低帶寬應用程序（如AJAX網站，其中大部分網站使用JavaScript呈現），此策略非常有用。

我總是緩存結果列表和結果本身。如果任何操作影響列表查詢的結果，則刷新列表結果的緩存。如果有任何事情影響結果本身，則會刷新這些特定結果。這使我可以更新任何一個，而不必重新生成所有內容，從而實現有效的緩存。

由於我的結果列表很少發生變化，因此我同時生成了所有列表。這可能會使初始響應稍微慢一點，但它簡化了緩存刷新（所有列表都存儲在單個緩存項中）。

因爲我有整個列表緩存，找到相鄰的項目而不重訪數據庫是微不足道的。幸運的是，這些項目的數據也將被緩存。這在JavaScript中排序數據時特別方便。如果我已經在客戶端上緩存了一個副本，我可以立即採取措施。

具體回答你的問題：

• 是的，這是一個奇妙的想法，找出提前鄰居，或任何信息的客戶端有可能進入未來，特別是在成本現在很低，重新計算的成本很高。那麼這僅僅是額外的預計算和存儲與速度的折衷。
• 在性能和簡單性方面，避免將事物捆綁在一起，這些東西在邏輯上是不同的。索引和數據是不同的，可能會在不同的時間發生變化（例如，添加新數據會影響索引，但不會影響現有數據），因此應單獨訪問。從單線程的角度來看，這可能效率稍低，但每次將某些東西捆綁在一起時，就會失去緩存有效性和異步性（縮放的關鍵是異步）。
• 提前獲取數據的術語是預取。預取可以在訪問時或在後臺進行，但在實際需要預取數據之前。與預先計算一樣。這是現在成本的折衷，存儲成本和需要時的成本。
• 「排序緩存」是一個適當的名稱。
• 我不知道。

此外，當你緩存的東西，緩存他們在最通用的水平可能。有些內容可能是用戶特定的（例如搜索查詢的結果），其他用戶可能是用戶不可知的，例如瀏覽目錄。兩者都可以從緩存中受益。目錄查詢可能會頻繁並且每次都會節省一點，搜索查詢可能會很昂貴，並且可以節省很多次。

Answer 6

有許多方法可以做到這一點，皮膚的諺語貓。所以這裏有幾個我的。

如果您的原始查詢代價昂貴，您說它是，然後創建另一個表可能是一個內存表填充您的昂貴和很少運行主查詢的結果。

然後可以在每個視圖上查詢第二個表，排序和設置適當的排序順序一樣簡單。

根據需要重新填充第一個表的結果，從而保持數據新鮮，但最大限度地減少了使用昂貴的查詢。

或者，如果你想避免連接到數據庫，那麼你可以將所有的數據存儲在一個php數組中，並使用memcached存儲它。這將是非常快的，並且如果您的列表不是太大，就會節省資源。並可以很容易地分類。

DC

Answer 7

基本假設：

• 特價是每週
• 我們可以預期，該網站很少......可能每天改變？
• 我們可以控制對數據庫的更新用乙醚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 8

你可以保存有序列表的row numbers到views，你可以在（current_rownum-1）和（current_rownum + 1）行數達到列表中的一個和下一個項目。

Answer 9

問題/ datastructur被命名爲雙向圖，或者你可以說你有幾個鏈表。

如果你認爲它是一個鏈表，你可以在items表中爲每個排序和prev/next鍵添加字段。但是DB人會爲此而殺了你，就像GOTO。

如果你認爲它是一個（雙向）的方向圖，你可以選擇傑西卡的答案。存在的主要問題是訂單更新是昂貴的操作。

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

如果您將一個項目位置更改爲新訂單A，C，B，D，則必須更新4行。

Answer 10

我有一個有點類似於傑西卡的想法。但是，不是將鏈接存儲到下一個和上一個排序項目，而是存儲每個排序類型的排序順序。要查找上一條或下一條記錄，只需獲取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 11

道歉，如果我誤解了，但我想你想保留用戶訪問服務器之間的有序列表。如果是這樣，你的答案很可能在於你的緩存策略和技術，而不是數據庫查詢/模式優化。

我的方法是在數組第一次被檢索後序列化（）數組，然後將其緩存到單獨的存儲區;無論是memcached/APC/hard-drive/mongoDb /等，並通過他們的會話數據單獨保留每個用戶的緩存位置詳細信息。實際的存儲後端自然取決於數組的大小，這一點你不會詳細討論，但是memcached可以在多個服務器上進行擴展，並且在更大的延遲成本下可以進一步提高mongo。

你也沒有指出在現實世界中有多少排序排列;例如你需要爲每個用戶緩存單獨的列表，還是你可以全局緩存每個排序，然後通過PHP過濾掉你不需要的內容？在你給的例子中，我只是緩存兩個排列，並在會話數據中存儲我需要反序列化（）的兩個中的哪一個。

當用戶返回站點時，請檢查緩存數據的Time To Live值，如果仍然有效，請重新使用它。我還會在INSERT/UPDATE/DELETE上運行一個觸發器，以便在特殊的表格中設置時間戳字段。這將立即指示緩存是否過時，並且查詢需要以非常低的查詢成本重新運行。關於僅使用觸發器設置單個字段的好處是，無需擔心從該表中刪除舊的/多餘的值。

這是否合適取決於所返回數據的大小，修改頻率以及服務器上可用的緩存技術。