28

完全なクエリを実行せずに、レコードの次のレコードと前のレコードを取得するための最良の方法を探しています。私は完全に実装されたソリューションを用意しており、これを行うためのより良いアプローチがあるかどうかを知りたいと思います。

架空の八百屋のウェブサイトを構築しているとしましょう。彼のHTMLページに加えて、毎週、彼は自分のサイトで特別オファーのリストを公開したいと考えています。彼は、これらのオファーを実際のデータベーステーブルに配置することを望んでおり、ユーザーは3つの方法でオファーを並べ替えることができる必要があります。

すべてのアイテムには、オファーに関するより多くのテキスト情報と「前へ」および「次へ」ボタンを含む詳細ページも必要です。「前へ」ボタンと「次へ」ボタンは、ユーザーがリストに選択した並べ替えに応じて、隣接するエントリを指す必要があります。

代替テキスト
（出典：pekkagaiser.com）

明らかに、「トマト、クラスI」の「次へ」ボタンは、最初の例では「リンゴ、クラス1」、2番目の例では「梨、クラスI」、3番目の例ではなしである必要があります。

詳細ビューのタスクは、毎回クエリを実行せずに、リストの並べ替え順序を唯一の利用可能な情報として使用して、次の項目と前の項目を決定することです（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
      );

これは明らかに高価であり、限られた数のレコードに対してのみ機能し、冗長なデータを作成しますが、現実の世界では、リストを作成するためのクエリは非常に高価であり（実際）、すべての詳細ビューで実行することはできません。質問、そしていくつかのキャッシングが必要です。

私の質問：

  • これは、さまざまなクエリ順序の隣接レコードを見つけるための良い方法だと思いますか？

  • パフォーマンスとシンプルさの点でより良い方法を知っていますか？これを完全に時代遅れにする何かを知っていますか？

  • プログラミング理論では、この問題の名前はありますか？

  • 「キャッシュの並べ替え」という名前は、この手法に適していて理解できるものですか。

  • この問題を解決するための認識された一般的なパターンはありますか？彼らは何と呼ばれている？

注：私の質問は、リストの作成や詳細ビューの表示方法に関するものではありません。これらは単なる例です。私の質問は、再クエリが不可能な場合にレコードのネイバーを決定する基本的な機能と、そこに到達するための最速かつ最も安価な方法です。

不明な点がございましたら、コメントを残してください。明確にします。

賞金を開始する-多分これに関するいくつかのより多くの情報がそこにあります。

4

11 に答える 11

16

ここにアイデアがあります。エンドユーザーが表示するデータを選択するときではなく、食料雑貨店が新しいオファーを挿入/更新するときに、コストのかかる操作を更新にオフロードすることができます。これは、並べ替えデータを処理するための非動的な方法のように見えるかもしれませんが、速度が上がる可能性があります。そして、私たちが知っているように、パフォーマンスと他のコーディング要素の間には常にトレードオフがあります。

各オファーと各ソートオプションの次と前を保持するテーブルを作成します。（または、常に3つのソートオプションがある場合は、これをオファーテーブルに格納できます。クエリ速度はデータベースを非正規化する良い理由です）

したがって、次の列があります。

  • 並べ替えタイプ（並べ替えなし、価格、クラス、価格の説明）
  • オファーID
  • 前のID
  • 次のID

オファー詳細ページの詳細情報がデータベースから照会されると、NextIDとPrevIDが結果の一部になります。したがって、詳細ページごとに1つのクエリのみが必要になります。

オファーが挿入、更新、または削除されるたびに、sorttypeテーブルの整合性/精度を検証するプロセスを実行する必要があります。

于 2010-02-22T19:20:57.693 に答える
4

私はジェシカのものと幾分似た考えを持っています。ただし、前後の並べ替えアイテムへのリンクを保存する代わりに、各並べ替えタイプの並べ替え順序を保存します。前または次のレコードを見つけるには、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 のアイデアよりも占有するディスク スペースが少なくてすみます。ただし、お気づきだと思いますが、すべての並べ替え順序を再計算して保存する必要があるため、1 行のデータを更新するコストは著しく高くなります。ただし、状況によっては、データの更新がまれで、特に常に大量に発生する場合は、このソリューションが最適な場合があります。

すなわち

once_per_day
  add/delete/update all records
  recalculate sort orders

これが役に立つことを願っています。

于 2011-02-13T02:30:02.957 に答える
2

私もこれで悪夢を見ました。あなたの現在のアプローチは、10,000 個のアイテムのリストに対しても最適なソリューションのようです。http セッションでリスト ビューの ID をキャッシュし、それを使用して (現在のユーザーに合わせてパーソナライズされた) 前/次を表示します。これは、アイテムの最初のリストを 3 つではなくフィルター処理およびソートする方法が多すぎる場合に特に有効です。
また、ID リスト全体を保存することで、"you are at X out of Y"使いやすさを向上させるテキストを表示できます。
JIRAの前/次

ちなみに、これはJIRAも同様です。

質問に直接答えるには:

  • はい、フィルター/並べ替えとアイテムの種類がより複雑になったときに、コードの複雑さを増すことなくスケーリングできるため、良い習慣です。「無限」のフィルター/並べ替えのバリエーションを持つ 250k の記事を含む実稼働システムで使用しています。キャッシュ可能な ID を 1000 にトリミングすることも可能です。ユーザーが前または次を 500 回以上クリックすることはほとんどないためです (ユーザーはおそらく戻って検索を絞り込むか、ページネーションを行うでしょう)。
  • 私はより良い方法を知りません。しかし、限定されていて、これが公開サイト (http セッションのない) である場合は、おそらく非正規化するでしょう。
  • わからない。
  • はい、キャッシュの並べ替えは良さそうです。私のプロジェクトでは、「検索結果の前/次」または「検索結果のナビゲーション」と呼んでいます。
  • わからない。
于 2011-02-07T20:04:35.120 に答える
2

一般に、インデックスからデータを非正規化します。それらは同じ行に格納されている可能性がありますが、ほとんどの場合、結果 ID を取得してから、データを別の場所に移動します。これにより、データのキャッシュが非常に簡単になります。待ち時間が短く、帯域幅が広い PHP ではそれほど重要ではありませんが、このような戦略は、サイトの大部分が JavaScript でレンダリングされる AJAX Web サイトなど、待ち時間が長く、帯域幅が狭いアプリケーションの場合に非常に役立ちます。

私は常に結果のリストと結果自体を別々にキャッシュします。リスト クエリの結果に何らかの影響がある場合は、リスト結果のキャッシュが更新されます。結果自体に何らかの影響がある場合、それらの特定の結果が更新されます。これにより、すべてを再生成することなくいずれかを更新できるため、効果的なキャッシュが実現します。

結果のリストはめったに変更されないため、すべてのリストを同時に生成します。これにより、最初の応答が少し遅くなる可能性がありますが、キャッシュの更新が簡素化されます (すべてのリストが 1 つのキャッシュ エントリに格納されます)。

リスト全体がキャッシュされているため、データベースを再確認せずに隣接するアイテムを見つけるのは簡単です。運が良ければ、それらのアイテムのデータもキャッシュされます。これは、JavaScript でデータを並べ替える場合に特に便利です。クライアントに既にコピーがキャッシュされている場合は、すぐに頼ることができます。

質問に具体的に答えるには：

  • はい、事前にネイバーを見つけたり、クライアントが次にアクセスする可能性のある情報を見つけたりすることは素晴らしいアイデアです。特に、現在のコストが低く、再計算のコストが高い場合はそうです。次に、追加の事前計算とストレージと速度のトレードオフにすぎません。
  • パフォーマンスと単純さの観点から、論理的に異なるものを結び付けることは避けてください。インデックスとデータは異なり、異なる時期に変更される可能性が高いため (たとえば、新しいデータムの追加はインデックスに影響しますが、既存のデータには影響しません)、個別にアクセスする必要があります。これはシングル スレッドの観点からは少し効率が悪いかもしれませんが、何かを結び付けるたびに、キャッシュの有効性と非同期性が失われます (スケーリングの鍵は非同期性です)。
  • 事前にデータを取得するための用語は、プリフェッチです。プリフェッチは、アクセス時またはバックグラウンドで発生する可能性がありますが、プリフェッチされたデータが実際に必要になる前です。事前計算も同様です。これは、現在のコスト、ストレージ コスト、および必要なときに取得するコストのトレードオフです。
  • 「ソート キャッシュ」という名前がぴったりです。
  • 知らない。

また、物事をキャッシュするときは、可能な限り一般的なレベルでキャッシュしてください。ユーザー固有のもの (検索クエリの結果など) もあれば、カタログの閲覧など、ユーザーに依存しないものもあります。どちらもキャッシュの恩恵を受けることができます。カタログ クエリは頻繁に実行されるため、毎回少しずつ節約できます。また、検索クエリはコストが高く、数回で大幅に節約できる場合があります。

于 2011-02-09T07:00:57.337 に答える
1

私が正しく理解したかどうかわからないので、そうでない場合は教えてください ;)

与えられたものは、ソートされたリストのクエリとそのリストの現在のオフセットであるとしましょう。つまり、$queryと があり$nます。

クエリを最小限に抑えるための非常に明白な解決策は、すべてのデータを一度に取得することです。

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

そのステートメントは、現在のソート順でデータベースから前、現在、および次の要素をフェッチし、関連する情報を対応する変数に入れます。

しかし、この解決策は単純すぎるため、何か誤解していると思います。

于 2011-02-07T19:31:44.707 に答える
0

基本的な仮定：

  • スペシャルは毎週
  • サイトが頻繁に変更されることはないと予想できます...おそらく毎日ですか？
  • API を使用してデータベースの更新を制御したり、トリガーを介して応答したりできます。

サイトが毎日変更される場合は、すべてのページを一晩で静的に生成することをお勧めします。並べ替え順序ごとに 1 つのクエリが繰り返され、関連するすべてのページが作成されます。動的要素がある場合でも、静的ページ要素を含めることで対処できる可能性があります。これにより、最適なページ サービスが提供され、データベースの負荷がなくなります。実際、別のページと、ページに含まれる前/次の要素を生成することもできます。これは 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。そのキーがキャッシュにある場合は、ゴールデンです。そうでない場合は、キャッシュに挿入して表示します。

  • これは、さまざまなクエリ順序で隣接するレコードを見つけるための良い方法だと思いますか? はい。予想される今後のリクエストに対して先読みを実行することをお勧めします。
  • パフォーマンスとシンプルさの点でより良いプラクティスを知っていますか? これを完全に時代遅れにする何かを知っていますか? 願わくば上記
  • プログラミング理論では、この問題に名前はありますか? 最適化？
  • 「ソートキャッシュ」という名前は、この手法に適切で理解しやすいものですか? 特定の適切な名前がわかりません。それはキャッシングであり、一種のキャッシュですが、「ソート キャッシュ」があると言ってすぐに理解できるかどうかはわかりません。
  • この問題を解決するための認識された一般的なパターンはありますか? 彼らは何と呼ばれている？キャッシング？

申し訳ありませんが、テーリングの回答は役に立たないものですが、私の物語の解決策は非常に役立つはずです.

于 2011-02-11T17:13:22.647 に答える
0

これを行うには、ことわざの猫の皮を剥ぐのと同じくらい多くの方法があります。それで、ここに私のものをいくつか示します。

元のクエリが高価であると言う場合は、おそらく別のテーブルを作成し、高価でめったに実行されないメインクエリの結果を入力します。

この 2 番目のテーブルは、すべてのビューでクエリを実行でき、適切な並べ替え順序を設定するだけで簡単に並べ替えることができます。

必要に応じて、最初のテーブルの結果を 2 番目のテーブルに再入力し、データを最新の状態に保ちながら、コストのかかるクエリの使用を最小限に抑えます。

あるいは、データベースへの接続さえ避けたい場合は、すべてのデータを php 配列に保存し、memcached を使用して保存することができます。これは非常に高速であり、リストが大きすぎなければリソース効率が高くなります。と簡単に並べ替えることができます。

DC

于 2011-02-11T04:19:53.523 に答える
0

問題/データ構造は双方向グラフと呼ばれます。または、いくつかのリンクされたリストがあると言えます。

リンクされたリストと考えると、ソートと前/次のキーごとに項目テーブルにフィールドを追加するだけで済みます。しかし、DB の人はそのためにあなたを殺します。それは GOTO のようなものです。

それを（双方向）グラフと考えると、ジェシカの答えになります。ここでの主な問題は、注文の更新が高価な操作であることです。

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

1 つのアイテムの位置を新しい順序 A、C、B、D に変更すると、4 つの行を更新する必要があります。

于 2011-02-13T01:20:55.297 に答える
0

誤解していた場合は申し訳ありませんが、ユーザーがサーバーにアクセスする間、順序付けられたリストを保持したいと考えています。もしそうなら、あなたの答えは、データベースクエリ/スキーマの最適化ではなく、キャッシング戦略とテクノロジーにあるかもしれません.

私のアプローチは、最初に取得された配列を serialize() し、それを別のストレージ領域にキャッシュすることです。それがmemcached/APC/hard-drive/mongoDb/などであるかどうかにかかわらず、セッションデータを通じて各ユーザーのキャッシュの場所の詳細を個別に保持します。実際のストレージ バックエンドは当然、アレイのサイズに依存するため、詳細については説明しませんが、memcached は複数のサーバーにまたがって大きくスケーリングし、mongo はレイテンシ コストがわずかに大きくなります。

また、現実の世界に並べ替え順列がいくつあるかも示していません。たとえば、ユーザーごとに個別のリストをキャッシュする必要がありますか?それとも、並べ替え順列ごとにグローバルにキャッシュしてから、PHP を介して不要なものを除外できますか? あなたが与える例では、単純に両方の順列をキャッシュし、セッション データで unserialize() するために必要な 2 つを保存します。

ユーザーがサイトに戻ったら、キャッシュされたデータの Time To Live 値を確認し、有効であれば再利用します。また、別のテーブルにタイムスタンプ フィールドを設定するだけの特別オファーのために、INSERT/UPDATE/DELETE でトリガーを実行することもできます。これにより、キャッシュが古くなり、非常に低いクエリ コストでクエリを再実行する必要があるかどうかがすぐにわかります。トリガーを使用して 1 つのフィールドのみを設定することの優れた点は、そのテーブルから古い値や冗長な値を削除することを心配する必要がないことです。

これが適切かどうかは、返されるデータのサイズ、変更の頻度、およびサーバーで使用できるキャッシュ テクノロジによって異なります。

于 2011-02-13T14:47:43.493 に答える
-3

したがって、次の 2 つのタスクがあります。

  1. アイテムのソートされたリストを作成する (異なる ORDER BY を使用した SELECT)
  2. 各アイテムの詳細を表示します (キャッシュ可能なデータベースから詳細を選択します)。

何が問題ですか？

PS: 順序付きリストが大きすぎる場合は、PAGER 機能を実装する必要があります。たとえば、「LIMIT 5」をクエリに追加し、「次の 5 を表示」ボタンを提供するなど、さまざまな実装が考えられます。このボタンを押すと、「WHERE price < 0.89 LIMIT 5」のような条件が追加されます。

于 2010-02-22T14:04:30.650 に答える