大きなテーブルを操作するためのグリッド実装。 パート1

垂直スクロールバーを備えたテーブル（グリッド）は、リレーショナルデータベースデータを操作するための最も一般的なユーザーインターフェイス要素です。 ただし、テーブルに非常に多くのレコードが含まれている場合に直面しなければならない困難は、それらの完全な減算とRAMへの格納の戦術が不合理になることを知っています。



大きなテーブルの一部のアプリケーションは、表示/編集のために数百万のレコードを持つテーブルを開こうとすると、設計されず、「フリーズ」します。 他の人は、ページングを支持して垂直スクロールバーのあるグリッドを使用することを拒否したり、スクロールバーの助けを借りて目的の（少なくとも最新の）レコードにすばやく移動できるという幻想だけをユーザーに提供します。











Log（N）-fast 1）初期表示2）レコードの全範囲をスクロールする3）指定された一意のキーを持つレコードに移動するプロパティを使用して、テーブルコントロールを実装する方法の1つについて説明します。 このすべて-2つの制限の下で：1）レコードはフィールドのインデックス付きセットによってのみソートでき、2）データベース照合規則はアルゴリズムに知られている必要があります。



記事に記載されている原則は、Java言語に参加したプロジェクトの著者によって実装されました。

基本原則

テーブルコントロール（グリッド）の2つの重要な機能は次のとおりです。

1. スクロール - スクロールバースライダーの位置に対応するレコードを表示します。
2. キーフィールドの組み合わせで指定されたレコードに移動します。

まず、実装の最も簡単なアプローチを検討し、多数のレコードの場合にそれらが不適切な理由を示します。



最も簡単なアプローチは、すべてのレコード（または少なくともそのプライマリキー）をRAMに読み込み、その後、配列セグメントを選択してスクロールし、配列内のエントリを検索して配置することです。 しかし、多数のレコードがある場合、まず、配列の初期ロードに時間がかかりすぎ、その結果、グリッドが画面上で遅延し、次に、テーブルデータがRAMを占有し始めるため、全体的なパフォーマンスが低下します。



もう1つのアプローチは、計算をDBMSに「シフト」することです。フォーム... select ... limit ... offset ...の構造を使用してスクロールウィンドウに表示するレコードを選択します。 ただし、オフセットとカウント（*）の両方がサーバー内のレコードの列挙に関連付けられており、通常は実行速度がO（N）であるため、多数のレコードでは無効です。 頻繁に呼び出すと、データベースサーバーが過負荷になります。



したがって、メモリへのデータの完全なダウンロードを必要とせず、同時に非効率的に実行されたリクエストでサーバーに負荷をかけないシステムを実装する必要があります。 これを行うには、どのクエリが効果的で、どのクエリが効果的でないかを理解します。



インデックスがフィールドkに構築されている場合、次のクエリは高速です（インデックスルックアップを使用し、ログ（N）中に実行されます）。

1. クエリA.データセット内の最初と最後のレコードを検索します。
   
   

   select ... order by k [desc] limit 1
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

2. クエリB. Kの指定された値以上のキーを持つh個の最初のレコードを検索します。

    select ... order by k where k >= K limit h
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

クエリBの注目すべき特性は、データベース内の既存のレコードのキーをパラメーターとして置き換える必要がないことです。プライマリキーによるレコードと、指定されたキーに最も近いレコードの両方を同等にすばやく見つけます。 これを積極的に使用します。



次のクエリは高速ではありません。

1. クエリCデータセット内のレコードの総数を計算します。
   
   

    select count(*) ...
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

2. クエリD。これ以上のキーを持つレコードに先行するレコードの数を計算します。
   
   

    select count(*) ... where key < K
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

クエリBおよびDは、複合インデックスがこれらのフィールドに構築されている場合、k1、k2、k3 ...の順序でいくつかのフィールドのセットでソートする場合に一般化できます。 条件k> = Kは、 辞書式順序でいくつかの値を比較するための論理条件に一般化する必要があります。

 where k1 >= K1 and (k1 > K1 or (k2 >= K_2 and (k2 > K2 or ...)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

基本原則は、ユーザーに迅速な応答を必要とする手順では、データベースへの高速クエリのみを実行することです。

主キーのレコード番号への依存を「推測」する

しばらくの間、テーブルの主キーに整数フィールドが1つしかないことを想像してください（この制限を以下で削除します）。



スクロールバースライダーの各位置を、0〜 どこで -テーブル内のエントリの総数、 -グリッドの1ページに収まる行の数。 スクロールバーが 、これは、グリッドをレンダリングするときにスキップする必要があることを意味します テーブルの最初のエントリ、次に印刷 レコード。 これはまさにPostgreSQLのoffsetおよびlimitキーワードが担当するものであり、多数のレコードがある場合、それらを使用することはできません。 しかし、何らかの「魔法の」方法で、短時間で関数を計算できるなら およびその逆関数 主キーとこれよりも小さいキーを持つレコード数を接続し、クエリBを使用して、そこに値を代入します 、ユーザーに表示する一連のレコードをすばやく取得できました。 目的のレコードに移動するタスクは、この方法で解決されます。主キーは事前にわかっているため、クイッククエリパラメーターBとしてすぐに使用でき、スクロールバーは次のように設定する必要があります。 。 タスクは解決されます！



（パラメータkで呼び出されたクエリDは値を返すだけであることに注意してください 、しかし、1）それは遅いです、2）どのように計算できるようにする必要があります 彼女の反対。）



自然に機能する テーブル内のデータによって完全に決定されるため、キー値とレコード番号の相互依存性を正確に復元するには、データベースからすべてのキーを1つを介してRAMに読み込む必要があります： Bリクエストが中間点で正しく機能するには、 （クエリBの素晴らしい特性を思い出してください）。 これは、行のすべてのキーを記憶するよりも優れていますが、テーブルの初期表示にO（N）時間とRAMを必要とするため、まだ十分ではありません。 幸いなことに、関数の正確に既知のポイントのはるかに小さい値で取得できます 、そしてこれを理解するには、可能な値の小さな組み合わせ分析が必要です 。



リクエストを完了しましょう

 select min(k), max(k), count(*) from foo
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

0、60、7の結果が得られました。つまり、テーブルには7つのレコードしかないことがわかりました（つまり、最大値 6）に相当し、最初のエントリのキーは0で、最後のエントリのキーは60です。このようなクエリの1つで、実際に値を学習しました 3つのポイントで ： 、 そして 。 それだけではありません。まさに定義から それに続く：

1. 単調に成長する
2. 増加とともに 単位あたり 1増加するか増加しないため、関数グラフ ポイントを除く 完全に平行四辺形にあります 、 、 、 、
3. 可能な機能の総数 配布方法の数に等しい の記録 キー値（最初と最後のレコードの位置は固定）、つまり
   
   
   
   
   
   
   
   
   
   
   
   
4. 可能な機能の数 どの時点で 値を取る キーの少ないレコードの組み合わせの数の積によって決定されます 、および以上 ：
   
   
   
   
   
   
   
   
   
   
   
   

したがって、可能なオプションのそれぞれが同等に考えられる場合、特定の値に対して まさにあります キーが厳密に小さいレコード 関係によって定義されます 超幾何分布として知られています。 のために 、 写真は次のようになります。











超幾何分布の特性はよく知られています。 の場合 いつも 、セグメント上 平均値 kに線形依存：









値の分散 セグメントの端にゼロがある逆放物線の形をしています 中央に最大値があります

（おおよそ、平均誤差は ）



上記の式による値の計算 、 可能な最小値と最大値（赤線）、平均値（青線）のそのような画像を示しています 、および標準偏差の境界線（灰色の領域）：











そのため、 ポイント間に構築された破線 、 、そして 関数を計算するための統計的に有効な近似です そして逆 、この近似により、1つのクエリで取得された3点の値しかわからない場合でも、関数の値を非常に正確に「推測」することができます。 実際、「推測」では、境界値を慎重に決定することによってのみ、 補間検索アルゴリズムの最初の反復を実行します。



今の場合 、 新しい正確な値が既知になる カップルを追加できます 補間テーブルにアクセスし、区分補間を使用して値の更新された計算を取得します スクロール問題を解決し、区分的逆補間を使用して、洗練された値を計算します ポジショニングの問題を解決するとき。 累積された各ポイントで、可能な不一致の範囲が狭くなり、関数の精度が向上します 。

複数のキーフィールドがあり、データタイプがINTでない場合

実際には、ビジネスはデータセットをソートするための単一の整数フィールドに限定されません。 まず、データ型が異なる場合があります：文字列、日付など。 第二に、いくつかのソート可能なフィールドがあります。 計算できれば、この困難は取り除かれます

1. ナンバリング機能 任意のタイプのフィールドの値のセットを自然数に変換し、
2. それの逆関数 自然数を一連のフィールド値に変換し直し、 。

ナンバリング関数には、次のプロパティが必要です。 少ないダイヤル 辞書順の意味では、 。



数学の言語では、全単射 フィールドのセットの可能な値のセットと自然数のセットの間で順序の同型を確立する必要があります。 注：適切なタスクを見つけるために 数学的に解くことができるため、可能なフィールド値のセットが重要です 有限でした。 たとえば、自然数（実数のペア）の辞書式に順序付けられたすべてのペアのセットと自然（実数）のセットの間で、順序の同型を構築することは不可能です。 もちろん、あらゆるマシンデータタイプのすべての可能な値のセットは、非常に大きいものの、有限です。



値を表すには 標準の32ビットおよび64ビット整数型は適切ではありません。したがって、すべての種類の10バイト文字列だけに番号を付け直すには、64ビット（8バイト）整数ではもはや不十分です。 実装では、 java.math.BigIntegerクラスを使用しました。これは、任意のサイズの整数を表すことができます。 この場合、値が占めるRAMの量 値のセットが占める体積にほぼ等しい 。



可逆的なナンバリング機能がある場合 および可逆補間関数 、

• グリッドスクロールは、キーフィールドの値の計算に限定されます どこで -垂直スクロールバーの位置。その後、データベースへのクイッククエリが検出されます 最初のエントリ以上 、
• ポジショニングは読書になります 以前に既知の値に従ってデータベースから最初のレコード 、およびスクロールバースライダーの位置を計算します 。

プロシージャ相互作用スキーム

この段階では、数学から脱出し、アルゴリズム部分自体を処理できます。 システム手順の相互作用の一般的なスキームを次の図に示します。 「近似UMLアクティビティ」表記が使用され、実線の矢印は手順のシーケンスを示し、点線の矢印は別の実行スレッドでの非同期呼び出しを示します。







ユーザーが垂直スクロールバーのスライダーの位置を変更したと仮定します（図の左下隅を参照）。 補間器は、キーフィールド値の組み合わせ番号の値を計算します（ ）BigIntegerタイプ。 この値に基づいて、列挙子はキーフィールドの組み合わせを復元します 。



フィールドのこの段階でそれを理解することが重要です データベースに実際に存在する値は必ずしも見つかるとは限りません。近似値のみが存在します。 たとえば、文字列フィールドには、意味のない文字セットがあります。 ただし、クエリBの顕著な特性のため、データベースからの出力 セット以上のキーを持つ行 指定されたスクロールバーの位置に対してほぼ正しい結果になります。



ユーザーがスクロールバーを離し、しばらく触れない場合、非同期で（実行の別のスレッドで）クエリDが実行され、レコードのシリアル番号、したがってユーザーに表示されるものに対応するスクロールバーの正確な位置が決定されます。 要求が完了すると、受信したデータに基づいて、補間テーブルが更新されます。 この時点でユーザーが再びテーブルのスクロールを開始していない場合、垂直スライダーは新しい洗練された位置に「バウンス」します。



記録に移行すると、プロシージャコールのシーケンスは反対方向に発生します。 キーフィールドの値は既にわかっているため、ユーザーリクエストBはデータベースからデータをすぐに取得します。 番号付けは計算します 、そして補間器はスクロールバーのおおよその位置を次のように決定します 。 並行して、非同期の実行スレッドで、洗練クエリが実行され、その結果によって新しいポイントが補間テーブルに追加されます。 1〜2秒後、スクロールバースライダーが新しいバウンド位置に「バウンス」します。



ユーザーが指定された垂直スライダーを「さまよう」するほど、補間テーブルに収集されるポイントが多くなり、「バウンス」が少なくなります。 実践では、補間テーブルで4〜5個の成功したポイントだけが「バウンス」を非常に小さくするのに十分であることを示しています。



補間クラスのインスタンスは、32ビット整数のセット（テーブル内のレコード番号）とBigIntegerオブジェクトのセット（キーフィールド値の組み合わせのシーケンス番号）の間の単調増加関数の中間点を格納する必要があります。



グリッドを初期化した直後に、正しい値を取得するために、別の実行スレッドでテーブル内のレコードの総数を要求する必要があります 。 並列スレッドで実行されているクエリを使用してこの値が取得されるまで、デフォルト値（1000など）を使用できます-これは正しい操作には影響しません。



補間器は、補間点の数という点で高速であるために、一方の方向と他方の方向の両方で値を計算できる必要があります。 ただし、組み合わせのシーケンス番号の値をレコード番号で計算する必要がある場合が多いことに注意してください。このような計算は、ユーザーグリッドをスクロールするプロセスで毎秒何回も実行されます。 したがって、インターポレーターモジュールの実装の基礎として、キーがレコード数であり、値が組み合わせ（JavaのTreeMap <Integer、BigInteger>クラス）のシーケンス番号であるバイナリツリーに基づいた辞書を使用すると便利です。



与えられた数に対して そのような辞書は、対数時間で2つのポイントを見つけます（ ）その間で関数の直接補間を構築します 。 しかし、という事実 単調に成長し、素早い時間と逆計算を可能にします。 確かに：組み合わせ番号が与えられている場合 、 あるピースセグメントの検索 、二分法により辞書に作成できます。 目的のセグメントが見つかったら、逆補間を実行します そして番号を見つける 対応する 。



ディクショナリを補間ポイントで満たす場合、補間された関数が単調なままであることを確認する必要があります。 他のユーザーは表示されているテーブルのエントリを削除および追加できるため、辞書が認識している補間点の関連性が失われ、新しく追加された点が単調性を損なう可能性があります。 したがって、新しい補間ポイントを追加する方法では、追加したばかりの「左側のポイント」が小さい値に対応し、「右側のポイント」が大きい値に対応することを確認する必要があります。 そうではないことが判明した場合、最後に追加されたポイントが現在の物事の状態に対応し、古いポイントの一部が関連性を失ったという仮定から進む必要があります。 新しく追加されたポイントに関連して、大きな値を含む左側のすべてのポイントと、低い値を含む右側のすべてのポイントを削除する必要があります。 「ノックアウトポイントをカットする」プロセスを図に示します。











また、インターポレーターには、冗長なポイントでオーバーフローすることから辞書を保護し、それらの最下位を破棄するメモリを保存するためのメカニズムが含まれている必要があります（思い出すように、すべてのポイントを連続して保存することは意味がありません-1つだけで十分です）。

前半の結論

そのため、システムの一般的な配置を理解しました。その主要部分は補間器と番号付けデバイスであり、 補間 器の実装についても十分に議論しました。 問題の解決を完了するには、 番号付け -バイジェクションを実装する必要があります 、キーフィールド値のセットをリンクします。これは、Unicode照合規則などを使用してソートされた日付、文字列で構成され、同じ順序で数字が増加します。



記事の第2部はこれに専念します 。



また、科学出版物も準備しています。また、arxiv.orgのこの記事の科学版の前刷りに慣れることもできます。