kenju's blog

About Programming and Mathematics

PostgreSQLのSort実装アルゴリズムのコードを読んでみた

tl;dr

  • PostgreSQLORDER BY句などでSortをする時、Disk I/Oの発生するMerge SortかインメモリでのQuick Sortが選択される

背景

https://www.slideshare.net/MikiShimogai/postgre-sql-explain を読んでいて下記スライドを発見したので、現在の実装を確認してみた。

f:id:itiskj:20170922173341p:plain

実装

現在のmasterブランチの実装は↓

github.com

void cost_sort()の実装を見ていく。

まずはヘッダーコメント。

/*
 * cost_sort
 *   Determines and returns the cost of sorting a relation, including
 *   the cost of reading the input data.
 * ...

void cost_sort()は、データをソートするコストを計算することに責任を負う。また、データ読み込みのオーバーヘッドも考慮してコストを算出する、と。

次に、選択されうる3つのアルゴリズムについての説明。

  • Disk I/Oの発生しないインメモリでのクイックソート
  • tape-style merge(マージソート、先頭からの順次アクセスを行う2本のテープ型の記憶媒体を用いてマージするロジックを擬似的に再現したアルゴリズム
  • bounded heap-sort(ちょうどデータ数が上限値か下限値に有界の時)
    • このロジックは理解が不十分である
/*
 * ...
 * If the total volume of data to sort is less than sort_mem, we will do
 * an in-memory sort, which requires no I/O and about t*log2(t) tuple
 * comparisons for t tuples.
 *
 * If the total volume exceeds sort_mem, we switch to a tape-style merge
 * algorithm.  There will still be about t*log2(t) tuple comparisons in
 * total, but we will also need to write and read each tuple once per
 * merge pass.  We expect about ceil(logM(r)) merge passes where r is the
 * number of initial runs formed and M is the merge order used by tuplesort.c.
 * Since the average initial run should be about sort_mem, we have
 *     disk traffic = 2 * relsize * ceil(logM(p / sort_mem))
 *     cpu = comparison_cost * t * log2(t)
 *
 * If the sort is bounded (i.e., only the first k result tuples are needed)
 * and k tuples can fit into sort_mem, we use a heap method that keeps only
 * k tuples in the heap; this will require about t*log2(k) tuple comparisons.
 * ...
 */

アルゴリズムを選択しているのが、以下の箇所。 先にあげた通り、三つの条件で分岐が行われている

 if (output_bytes > sort_mem_bytes) // 
    {
        /*
        * We'll have to use a disk-based sort of all the tuples
        */  
        ...
      }
    else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
    {
        /*
        * We'll use a bounded heap-sort keeping just K tuples in memory, for
        * a total number of tuple comparisons of N log2 K; but the constant
        * factor is a bit higher than for quicksort.  Tweak it so that the
        * cost curve is continuous at the crossover point.
        */
        ...
    }
    else
    {
        /* We'll use plain quicksort on all the input tuples */
        ...
    }

それぞれの分岐内で初期実行コストstartup_costと実行時コストrun_costから、トータルでかかる実行コストtotal_costを算出し、path構造体に格納し、処理を終える。

 path->startup_cost = startup_cost;
    path->total_cost = startup_cost + run_cost;

total_coststartup_costについては、costsize.cのヘッダーコメントを参照されたい:

  * We compute two separate costs for each path:
  *     total_cost: total estimated cost to fetch all tuples
  *     startup_cost: cost that is expended before first tuple is fetched

ぼやき

PostgreSQLで複雑で重めのクエリを投げる時に度々Disk I/Oが発生していて、どんな処理が多いのだろうといつも気になっていたのだが、そのうちの一要因としてメモリに乗らない量のSortを実行しているからかもしれない。