毎回量と平均を再計算しない方法

電子決済システムがあり、その中にデータベース内にオペレーションのテーブルがあると想像してください。 また、たとえば、平均的な操作のサイズを計算します。 簡単です、ここにリクエストがあります。完了するのに長い時間しかかかりません：



> SELECT avg(amount) FROM transfer;

65.125965782378

generated in 3850 seconds







ここで、インディケータが最も新しく、テーブルのエントリが毎秒作成され、1か月に何百万ものデータが蓄積されると想像してみましょう。 または他の要件ですが、本質は同じです-毎回同じデータを集約することは非常に高価です。 通常のデータベースでは、このような最適化は提供されていません。 になる方法



自転車に乗る人は、このサイクリングコンピュータがどのようにして平均速度を無限に毎秒計算できるのか疑問に思うかもしれませんが、すべての速度値を保存するわけではありません。 今、もちろん、microSDカードは自転車のコンピューターに入りますが、そのようなメモリーがなかった数年前と同じように働きました。



簡単です。移動距離と時間を保存します。 毎秒、タイムカウンターを増やし、走行距離を走行距離に追加するだけです。 4または8バイトの2つの値のみ、合計2つの加算操作。 平均値を導き出すには、1つを別の値に分割する必要があります。

その他の変換

支払いシステムの場合、定期的に金額または平均の値を追加するだけでなく削除する必要があります。 削除する値がわかっている場合、これは同じ式で反対方向にのみ行われます。







d _1がわからない場合、何も実行されません。



すでに考慮されている値を変更する場合、同じことを2回行います。平均から古い値を削除し、新しい値を追加します。







数学を知っている人は、分散、積、さらには各数量の積（または共分散）などの統計に簡単に分解できます。 そのような知識を実際に適用する場所は一例です。

プロフィール

ユーザーはさまざまな質問からアンケートに記入し、1〜100のスケールで同意を示します（強い同意から完全な不一致まで）。 2人のユーザー間の差、つまり対応する質問に対する回答間の標準偏差を計算する必要がありました。







iとjは異なるユーザーです。 また、ユーザーXとグループ、およびユーザーXと他のすべてのユーザーとの差を計算する必要があります。 （統計の用語から意図的に逸脱し、分散のnによる除算を省略しました。計算の本質と複雑さは、これから定性的に変わりませんでした。）



最適化なしのデータベースへのクエリは次のとおりです。

 選択
        平均（パワー（my_answer.value-his_answer.value、2））

    から
         my_answer ASとして回答
             my_answer.question_id = his_answer.question_idでhis_answer ONとしてINNER JOIN回答

    どこ
         my_answer.user_id = X AND
         his_answer.user_id = Y 

複数のユーザーの場合、条件を変更するだけです。

  ...
    どこ
         his_answer.user_id IN（Z）AND
         ... 

回答を全員と比較する場合は、削除することもできます。 明らかに、このためには、テーブル全体を選択する必要があります。 もちろん、50個の質問と10,000個のアンケート、つまり500,000行、わずか数メガバイトのメモリでキャッシュできます。 ただし、ユーザーはアンケートに記入し、結果を見ることが多いため、計算操作をもう一度繰り返したくないため、最適化する必要があります。



最初の行のこの式には、分散式、より正確には最適化が必要な部分があります。 X _qは質問_qに対するこのユーザー（インジケーターが考慮される）の回答であり、V _quは同じ質問qに対するユーザーuの回答です。 ユーザーと質問ごとに集計します。 質問が少ない場合（m≅50）、多数のアンケートがあります（n≅10,000）。 2行目には、ユーザーの合計（n、10,000）が分離される同じ式が含まれています。 q-sumはこの式全体に張り出します。つまり、データは質問ごとに分類される必要があり、毎回それらを集計する必要がありますが、これはわずか50行です。 そして、10,000人のユーザーの量、u、私たちは分離し、計算して保存することができます。 質問qに対する回答の合計をS _qとして、二乗の合計をR _qとして表すと、非常にコンパクトな式が得られます。







S _qとR _qは事前に計算して、別のテーブルに保存できます。

測定

システムがどれほど速く動作するかを感じるために、抽象的なユーザーから抽象的な質問へのランダムな回答を生成するスクリプトを作成しました。 このスクリプトは、回答という1つのテーブルのみを埋めます。 他のテーブルは必要ありません。

 インポートsys、sqlite3、ランダム、itertools

 USERS = xrange（100000）
質問= xrange（50）

 conn = sqlite3.connect（ 'aggregation.sqlite3'）
 cur = conn.cursor（）

 cur.execute（「存在する場合はテーブルをドロップする」回答）;
 cur.execute（「テーブルの回答を作成（user_id整数、question_id整数、value整数）」）

 itertools.productのu、q（ユーザー、質問）：
	 cur.execute（「回答値に挿入（？、？、？）」、（u、q、random.randint（1、100）））

 ＃データ入力後にインデックスを構築し、
 ＃挿入中に二分木を再構築しないように
 cur.execute（ 'answer（user_id）にインデックスanswer_userを作成'）
 cur.execute（「回答（question_id）にインデックスanswer_questionを作成」）
 conn.commit（）

 cur.execute（ "" "
	テーブルanswer_summaryを作成します
	 question_id、sum（value）value、sum（value * value）value_square、count（*）numを選択します
	答えから
	 question_idでグループ化
	 "" "）

 cur.execute（「answer_summary（question_id）に一意のインデックスanswer_questionを作成」） 

100,000ユーザーへの50応答-500万レコード。 私の弱いラップトップ（1.5 GHz x2および2 GBのメモリ）では、テーブルは約30分で構築され、レコード数に応じたファイルは数十から数百メガバイトでした。



合計と二乗の合計でいくつかのクエリを作成しましたが、その主観的な感覚を以下に示します。 重要なことは、Linuxがデータベースファイルをメモリに完全にキャッシュしたことです。 つまり、計算のみが遅くなる唯一のこと、つまりインデックス検索と追加です。



そして、答えの違いの統計を考慮した場合の結果は次のとおりです。

	最適化なし	最適化あり
すべてに	秒	すぐに
それぞれに	数分	すぐに

副作用

プログラムがデータベースと通信し、大量の行（数千行）が必要な場合は、すべてのデータをプログラムに転送して集計するのではなく、データベースにこれを実行させるのが妥当です-これによりオーバーヘッドが増加します。



ただし、例のアンケートの場合のように、データが事前に要約されている場合は、50 + 50行しかありません。 そのようなデータは、元の形式ですでに選択され、コードがより簡潔になるプログラムで計算されます。



量の更新も同じ方法で実行できます。テーブル結合で複雑なUPDATEクエリを記述する必要はありません。データを選択して追加し、INSERT OR REPLACEを使用して更新できます。

アプローチが機能しない場合

速度計の例に戻りましょう。 平均速度はキロメートル/時です。 これをメートル/秒に直線的に変換できます。 km / hからm / sまで数えて、それから集計した場合、同じことが起こりました。



平均値を保存し、平均空気抵抗（速度の2乗に比例する）を計算したい場合、値の2乗の合計は値の合計では機能しないため、成功しません。 最初の観察が必要です。

それほど複雑ではない

実際、OLAPではなくORMのみを使用している場合は、SQLクエリシートを記述する必要はありません。SQLクエリシートは後で保守する必要があり、最悪の場合、他の人を理解する必要があります。 このような最適化は、関連モデルの形で行うことができます。 Djangoでモデルを整理する方法は次のとおりです。

 クラス質問（モデル）：
    テキスト= CharField（）


クラスの回答（モデル）：
     user = ForeignKey（ユーザー）
     question = ForeignKey（質問）
    値= IntegerField（）


クラスAnswerAggregate（モデル）：
     question = ForeignKey（質問、related_name =「集計」）
     summ = IntegerField（）
     summ_of_squares = IntegerField（）
     answer_count = IntegerField（）


 def add_to_aggregates（* kwargs）：
     answer = kwargs ['instance']
     answer.question.aggregates.update（
         summ = F（ 'summ'）+ answer.value、
         summ_of_squares = F（ 'summ_of_squares'）+ answer.value ** 2、
         answer_count = F（ 'answers_count'）+ 1
     ）


 def remove_from_aggregates（* kwargs）：
     answer = kwargs ['instance']
     answer.question.aggregates.update（
         summ = F（ 'summ'）-answer.value、
         summ_of_squares = F（ 'summ_of_squares'）-answer.value ** 2、
         answer_count = F（ 'answers_count'）-1
     ）


 Signals.post_add.connect（add_to_aggregates、model = Answer）
 Signals.pre_update.connect（remove_from_aggregates、model = Answer）
 Signals.post_update.connect（add_to_aggregates、model = Answer）
 Signals.pre_delete.connect（remove_from_aggregates、model = Answer）

回答を作成するとき、さまざまな量に追加します。 削除するには、値を減算するだけです。 変更するには、古い値を減算し、新しい値を追加します。



魅力的な宿題として、ORMまたはSQLでクエリを作成し、上記の式から標準偏差を計算できます。

価格改善

そのような計算を最適化することがいかに適切かは、別の問題です。 アンケートを使用した例では、数千のユーザーでもレポートの処理速度が低下し始め、1万人のユーザーがそれぞれ数秒間で完了しました。 このような量のデータは、小規模なプロジェクトでも、さらには営利企業でもかなり達成可能です。 今日の通常のデータベースは、このような最適化を自動的に行いません。 最適化はOLAPデータベースに組み込まれていますが、小規模企業にとっては高価でかさばります。 したがって、このような小さな最適化は良い解決策になります。



このような最適化の価格は次のとおりです。



1.数式を導き出し、理解します。これには、数学的統計の十分な知識が必要です。

2. ORMでトリガーまたはプロシージャを作成し、デバッグします。

3.新しい従業員が通常の集計関数の使用を開始しないように、システムを詳細に文書化します。

まとめ

まず、測定結果からわかるように、ユニットのメインブレーキ（SUM、AVG）はディスクをまったく読み取っておらず、むしろ合計しています。



第二に、複雑な集約関数でさえも分解でき、それらの中で集約を区別できます。 差の2乗がどのように成分に分解され、量の合計とそれらの2乗の合計が区別されるかを示しました。 金額は事前に計算して保存することができます。



レポートのリソース消費は、観測数O（n）に比例して減少します。 ギガバイトのデータを保存するシステムでは、これにより作業が大幅に加速される可能性があり、レポートは最大1秒で加速されます。



第三に、集計を完全に再カウントすることなく、新しいデータを追加し、古いデータを編集および削除できます。 再計算のリソース消費もO（n）回減少します。



第4に、少数の行、つまり集計のみで作業すると、データの量が減少し、データベースから取得してプログラムコードで直接計算できるため、面倒なSELECTまたはUPDATEクエリを回避できます。



最後まで読んだ人のために：記事の一番最初のリストは架空のものです。