誰にも見えないブログ

雑なメモ。まとまってない文章等

Database Concurrency Control Papadimitriou 直近3回分くらい参加メモ

勉強メモ 勉強会 transaction

整理やtexの変換が終わってないが、ここはそういう雑なものを置いておく場所なのでとりあえず投稿。

  • 読んだ範囲p103 "Exclusive and Shared Locks"~

排他ロックと共有ロック

  • 2つのトランザクションが同時にロック(片方が排他)を獲得していないスケジュールはlegal
    • writeにがあったentityには排他ロックを獲得している
    • readがあったentityには排他・共有どちらかのロックを獲得している

ロックの粒度

  • 議論:楽観ロックと悲観ロック

    • 悲観ロック
      • スタベーション(abortし続ける)

  • 個別にロックを取るか、まとめてロックを取るか

    • まとめてロックを取る:まとめて=粒度
      • 個別に複数ロックを取るのと同じ

  • class $\Gamma \subset E$

  • $e \in E$

  • ${e} \in \Gamma$

  • 任意のG1,G2∈Γに対して共通部分が存在する場合、片方が新部分集合になっている

    • $G_1 \cap G_2 =\emptyset $ or
    • $G1 \subset G2$ or
    • $G2 \subset G1$

  • chain of $\Gamma$

    • chain $$

  • この構造は木構造そのもの

  • access lock,intention lockのrule

    • 1:action対象のentityを含むgranulesのどれか一つにaccess lock獲得する
    • 2:access lockしたものが所属するgranule chainのすべてのgranuleに対してintention lockを獲得する
    • 3:各トランザクションはロックの解除ステップにlock stepを持たない()

  • 議論:javaのsynchornizedの仕様が微妙

    • safe,unsafe的な用語では無いのか

2020/10/07

  • p107~The path Protocolから
  • p108 1行目「travery nsactions」はタイポ(多分transactions)

Path Protocol

  • entityに順番にアクセスすることを前提とできるとき、two-phase lockよりも柔軟なlockプロトコルを考えることができる

    • entityに対してlinear orderを定義するx1,x2,...,xn
    • 例えば以下のtransactionsがそれに該当する
      • T1=A(x2)A(x3)
      • T2=A(x3)A(x4)A(x5)A(x6)

  • ルール

    • 最初に操作対象のentityをlockする
    • 操作対象のentityにaccessする
    • 次の操作対象のentity xiをlockする際、前回操作対象だったxi-1のentityをunlockする

  • L(x3)A(x3)L(x4)U(x3)L(x4)A(x4)L(x5)U(x4)...

    • 上記のtransactionはpath protocolに従っている
      • two phase lockingではない
        • unlockの後にlockしている箇所があるため

  • path protocol は safe

  • 証明略
  • 用語の定義
    • triangulated/chordal:任意の3より長いcycleが含むより短いcycleのこと(長さ3のcycle)
    • path:in-degree

TIMESTAMP SCHEDULERS

  • 2020/11/04~の範囲

  • p111~

  • output,arrirvedなどの概念がややこしいと思った。
  • 以下をテストするとConflict Serializableなスケジュールが得られる

implementation

  • timestampを使う
    • のでtimestamp schedulerと呼ばれる
  • 各activeなトランザクションには数字(timestampを割り当てる)
    • 最初のステップが到着したtimestampを各トランザクションに割り当てる
      • papa本では最初のstepはbegin transaction stepとしている
        • 実際のシステムでbegin transactionの時間をccに使っているものはないのではないか？という議論があった。

  • entityのタイムスタンプという概念を考える

    • entityに対する最後のwrite,read操作をreadのタイムスタンプ、writeのタイムスタンプと定義する
      • xのwriteのentityタイムスタンプよりr(x)のtransactionタイムスタンプが大きい時、r(x)は続行できる
      • xのread,writeのentityタイムスタンプよりw(x)のtransaction timestampが大きい時、w(x)は続行できる

  • dynamic modeで動作可能だが、デッドロックにあるパターンがある。p112のExample 4.3~

  • p113 5行目:”Notice that A2: W(x) ended up joining the queue~"とあるが、A2ではなくA1の間違い(typo?)

Conflict Graph Schedulers

  • p113~
  • conflict graphを使ったcc
  • conflict graphに新しいstepが追加した際、acycleな場合にstepをすすめることができる。
  • csrなスケジュールが得られる
    • theorem 4.11: the set of schedules output by the conflict graph scheduler is precisely the set of conflict serializable schedules.

Theory of Database Concurrency Control

Theory of Database Concurrency Control

次回はp116 Theorem 4.12から

*1:A step can proceed if all conflicting steps of older active transactions have already been output

Database Concurrency Control Papadimitriou 読会33回ノート:Schedulerのmode,Two-Phase Lockingなど

勉強会 transaction
  • p96 4.2 Lockingからp103 Exclusive and Shared Lockの手前まで。
  • 次回はp103 Exclusive~から

connpass.com

Schedulerの3つのモード(個人的な復習)

Dynamic mode

  • 初期状態で何の情報も持たない。
    • Transacionのstepが順次到着するが、そのstepの情報のみ(操作内容read,writeや操作対象のentity)
    • 最終ステップに関しては最終ステップである趣旨の通知がスケジューラになされる。

Declaration Mode

Static Mode

開始時にすべてのTransactionの情報がすべて把握できている。

Static Two-Phase Locking

  • 以下をテストする
    • "A step can always proceed, unless it is the first step of a transaction, and this transaction conflicts with an active transaction."
      • あるTransactionの最初のstepはActiveなtransactionとconflictしていない場合のみ進行可能である
        • →conflictしている場合はactiveなもう一方のtransactionの終了を待つ(FIFO queuing)
  • declaration modeでのみ可能

Dynamic Two-Phase Locking

  • 以下をテストする
    • "A step can always proceed, unless it conflicts with a previous step of an active transaction(other than its own)"
    • つまり、activeなtransactionで実行済みなstepでconflictがあるものは実行されない
      • 実行中のtransactionで操作対象としているentityに対するstepはqueuingされる。
        • つまりconflictしている実行中のtransactionが終了した時にqueueからoutされる
  • dynamic modeで実行可能。

Two-Phase Locking

  • 1.entityに対するactionの前に必ずロックをとる

  • 2.各トランザクションのlock stepの前にunlock stepが来ることはない(entity関係なく)

  • 関係ないけどTwo-Phase Lockの証明はかなり綺麗らしい(serializable?weikum本にある？)

Theory of Database Concurrency Control

Theory of Database Concurrency Control

Database Concurrency Control Papadimitriou 読会(31回)に参加

勉強メモ transaction

Database Concurrency Control Papadimitriou 読会(32回)に参加

  • p86からp90まで読んだ。
  • 次回はp90「Definition 3.4~」から

The Complexity of Reliability(続き)

  • (s(F),V'_{s(F)})is reliable if and only if F is true
    • のonly if direction
      • reliable → F is true
    • 対偶(F is false → universal player が QSAT gameに勝つ)を示す
  • PSPACE-compeleteとNP-completeはどちらが難しいかわかっていない
  • が、view serializability(NPC)よりreliability(PC)の方が難しいと(papaさん達は)思っている
  • Chapter 7でdistributed concurrency controlのPSPACE-completenessの例を説明する
    • 本にはchapter 6と書かれているが7の間違い

Conflicts and Reliability(p87)

  • unsafe read,writesがないfulll schedulesをconservativeという(Example 3.7(p70)の議論も参照)
    • 形式的な定義
      • readはread commitedであること
      • concurrentなW(x) は存在しない
        • transactionの最終ステップではないW(x)に関して
          • s中にはあるw'の後にくるw''stepgaが存在するとき、 V(w)=w' を対応させているversion functionに置いて、w時点でsがcommitされているならVはwをw''に対応づける
          • つまり最新commmitのwriteは上書きされない？
    • standard version functionを採用する1つ以上のversion functionを含んでいる場合、reliableではない(がquasi-standardard versionn functionであればreliable)
    • Example 3.8(p71)はconservativeであるがreliableではない例
    • conflict serializable scheduleの場合、 conservativeであればreliableである。
  • confllict seriazableであるとき、atomic write model,(s,V_s)はrelliable

Rollback Reliability

  • A-continuation(p71)などの復讐が必要

Theory of Database Concurrency Control

Theory of Database Concurrency Control

SQLパフォーマンス詳解読書会(7)ノート

インデックスを使ったgroup by

  • group by のアルゴリズム
    • hash
    • sort group
      • 中間結果をマテリアライズしてソートしないのでパイプライン化できる
        • マテリアライズ&ソート:一旦メモリ上で全データをソートする必要があるということ？

部分結果

  • パイプライン化したorder byの使い方

  • 最初のN行のみの選択

  • memo

    • DB2には各種OSS DBをエミュレートする機能がある

  • ページング

    • 複数間結果を10件ずつ区切って一つ一つ選択していく方式
    • ”(1) 順序付けはクエリが呼び出 される度にやり直されるので、新しい売上が挿入されるとページがずれ てしまいます。”(p149)
      • repeatable read だとずれない
    • オフセット法
      • order byした結果をoffset句で飛ばす範囲を指定する
      • limitで必要な行数を指定する
    • シーク法
      • 前ページの最終値”?”を指定し、sort対象の列 < ? をwhere句で与える(Order by DESCの場合)
      • sort 対象の列がユニークである場合にのみ可能
    • window関数
      • ... row_number() over() rn ... where rn between 11 and 20
        • STOP KEYが実行計画に出ていない場合はパイプライン化できない可能性がある
          • OVER句が含まれる内側のクエリがマテリアライズされることがある

  • 行値式:標準SQLだが実装の足並みが揃っていない。DB2とPostgreSQLがサポート

    • Oracle範囲条件検索は非サポート(ORA-01796)
    • SQL Server 2017 非サポート
    • MySQL インデックスのアクセス述語として使用不可

SQL Performance Explained

SQL Performance Explained

  • メディア: ペーパーバック

Database Concurrency Control Papadimitriou 読会29回ノート:reliabilityとQSATの帰着

勉強メモ transaction

主にreliability保証がPSPACE完全であることを示すためにQSATをreliability gameに帰着させる手順の解説を読んだ。QSATの用語とreliability gameの用語とgadgetの用語が混ざっている上に図がほとんどないのでかなり分かりにくい。加えて私はgadgetの理解がいまいちなので読んでて非常に混乱した。

  • p80 The Reductionからp83　Finally let us spcecify(4)~の段落最後まで読んだ。次回はp83 We will describe~から

connpass.com

The Reduction

  • F=true ↔︎ (s(F),V's(F)) is reliable

    • 上記を満たす変換(reduction)を考える

  • 各EXISTENSIAL(偶数変数)、UNIVERSAL(奇数変数)のx_iごとにトランザクションD_i,D'_iを作成する

    • UNIVERSAL(EVIL player)は奇数iのD_i,D'_iどちらかを一つのみをabortできるようにDを作る
    • EXISTENSIAL(Good palyer)は偶数iのD_i,D'_iは他のトランザクションがwriteしないentityをread-writeしている
      • このwriteは(もちろん他のtransactionがwriteしないので)最終値を決定している。
    • EVILが奇数iのトランザクションをabortした時、GoodはDi,D'_iのread writeの順序を変更することができる
      • xi=trueのときDi,D'_iの順序に対応し、xi=falseの場合逆順になる。

Reductionの手順

  • Reductionはscheduleを構成するパートとpolygraphを構成するパートに分かれる。手順は以下になる

    • (1).(EVIL側に)奇数iのDi,D'iどちらか一方をabortするように強制する
    • (2).QSATの各clause中のすべてのlilteralがfalseのとき、cycleが発生するように構成する
    • (3).clause中に出現した各xiに対して、Di,D'iに”Fan-out” gadgetsを使って真理値を配る
    • (4)."Precedence" gadgetを使って正しい順序を強制する

  • 上記のパートについて詳しく説明する

  • 前提としてarc=directed edgeであることに注意

(1)

  • 奇数番目iに対応したトランザクションT1,T3,...Tn-1を用意する

  • 追加でTn+1のトランザクションを用意する

  • T1からTn+1への潜在的なpathを用意する
    • T1がy1,y'1をwriteする。
    • T3がy1,y'1,y3,y'3をwriteする　
      • 同様に後続のtransactionでyi-1, y'i-1, yi, y'iのentityにwriteし、隣り合った順序のトランザクションをwrite-write conflictで接続する
        • この接続で作ったarcはpolygraphに出現しない。
          • yi,y'iの最終値はDi,D'iで決定されるため
            • Di,D'iどちらかをabortしないとT1 to Tn+1のpathが構成されない(EVIL側が必ず負ける)*1
              • 故にEVIL playerはDi,D'iどちらかをabortする必要がある

(2)

  • 各clauseはTn+1からT1への潜在的なback pathを持つ
    • 潜在的なback pathは4つのarcと3つのundirected edgeから構成される
      • 3つのundirected edgeはclause中のliteralに対応する

一応(4)まで読んだが仕事が忙しいのでとりあえずここまででで一旦投稿。

英語

  • occurrence:出来事
  • Precedence:優先

Theory of Database Concurrency Control

Theory of Database Concurrency Control

*1:ここからよくわからない？

SQLパフォーマンス詳解オンライン読書会(6)参加ノート:インデックスのみスキャン、ソートなど

勉強会 sql

クラスタ化インデックスよくわかってないので復習したいところ。

meguro-binary-study.connpass.com

インデックスのみスキャン

  • インデックスに含まれる列のみの問い合わせはターブルアクセスが発生しない
    • カバリングインデックスとも呼ばれる
    • 少数の列へのアクセスの場合は優位性はとくにない
      • アクセスする行数とクラスタ化係数によって優位性が決まる
    • postgreSQLはサポートが 遅かったらしい
      • 最新版では対応
    • WHERE句の条件にインデックスにない行が増えたりするとテーブルアクセスが発生し、行数が少なくなるのに遅くなる、という事象が発生するので注意。
    • リーフノード非キー列を格納するINCLUDE句が存在する(postgreSQL/SQL Server)
      • WHERE句には指定しないがSELECT句に指定したい列を指定する？
  • 部分インデックス：長さがわからないテキスト列などに使えるインデックス
    • CREATE INDEX .. ON employees (last_name(10))
  • インデックスのみスキャンを考えるときは各RDBのindexに含めることのできる列数制限やインデックスサイズ制限に注意する(必要に応じてベンダのドキュメントを参照すること)
    • 大まかな目安(多くのRDBでこの値)
      • 32列
      • 1700Byte~6398Byte

索引構成表

ソートとグルーピング

  • ソート処理は一般にパイプライン化出来ない

    • パイプライン化の部分の全体の中での順序が決定する必要があるため

  • インデックスをうまく使えばOrder byをパイプライン化できる

  • Order Byで指定する列順でindeを作ればOrder By処理は不要にできるケースがある(実行計画から消える)

  • (ソート不要のつもりが)ソートが行われてしまう原因を知りたければ、order by 句を完全に含むインデックス定義を使って調べる

オプティマイザは、結果の最後 のレコードを最も早く得られる実行計画を選ぶのです(p133)

  • 一般的にリーフノードチェーンの作成は双方向連結リストを使っているのでOrcer byのASC/DESCのコスト差はない
    • ただし複合インデックスの場合はインデックスに含めた各列の順序を合わせる必要がある。
      • ASC,ASCで指定したindexにDESC,DESC問い合わせはOKだがASC,DESCなどを混ぜた問い合わせ使うとソート処理が必要になる。
        • 混在させた問い合わせを使いたい場合は混在させたindexを定義しておく
          • ASC/DESC付インデックスを使う
            • MySQL以外のDBはほぼほぼASC/DESC インデックスに対応
            • MySQLは最新では対応してる(8のどこかから対応)
              • p138の表は少し古い

f:id:yuyubu:20200622215108p:plain

SQLパフォーマンス詳解

SQLパフォーマンス詳解

  • 作者:Markus Winand
  • 発売日: 2015/09/14
  • メディア: ペーパーバック

Database Concurrency Control Papadimitriou 読会(27回)参加メモ

transaction 勉強会

papa本27

  • p76 「Our proof~」から読んだ

  • 次回はp80「The Reduction」から

  • 久々に全然わからなかった。

connpass.com

gadget続き

  • Reliabilityの計算量がPSPACEになることを示そうとしている。

    • 何を問題意識に議論しているのか全くわからなかった。
    • 時系列でstep-by-stepにpolygraphが作成されていく際、
      • abortするとpolygraphにcycleを発生させてしまうトランザクションがある
        • このようなabortをEVILと言われている
          • 詳細はよくわかってません。
  • 何か書き足すかも？
  • p77のs1を反転させたs1‘を作り、C=E'、E=C'として接続し、s2を作る。このS2でD(D'?)がe'をwrite setに持っているという話から全くついていけなくなった。

Theory of Database Concurrency Control

Theory of Database Concurrency Control