Sort by Table Partition?

idea

v9.6向け開発ネタとして思い付いたアイデア。
でも、個人的には他に優先すべき機能*1もあるので、たぶん自分ではできない。誰かヨロシク的な。

タイムスタンプをキーとして複数の子テーブルにパーティション化されたテーブルがあるとする。
これは結構一般的な伝票データの作り方なのでそれほど変な仮定でもない。

各子テーブルに設定されたCHECK()制約から、特定のキーによる並べ替えを行う場合に各々の子テーブルに大小関係が定義できる場合。
例えば、以下のようなテーブル構成で、キー "YMD" によるソートを行うケースを考えると、tbl_2013テーブルに格納されている全てのレコードは、他のテーブルから読み出したレコードよりも最近の日付を持っていると言える。中を読むまでもなく。

f:id:kaigai:20150610000543p:plain

そうすると、キー "YMD" による並べ替えを行うケースであっても、ソートを行う問題領域を小さくする事ができるので、その分、処理時間を短くできる。

要は、こういった条件が満たされる場合には

GroupAggregate
 -> Sort (key: YMD)
   -> Append
     -> SeqScan on tbl_2013
     -> SeqScan on tbl_2012
     -> SeqScan on tbl_2011
     -> SeqScan on tbl_2010

これが

GroupAggregate
 -> Append
   -> Sort (key: YMD)
     -> SeqScan on tbl_2013
   -> Sort (key: YMD)
     -> SeqScan on tbl_2012
   -> Sort (key: YMD)
     -> SeqScan on tbl_2011
   -> Sort (key: YMD)
     -> SeqScan on tbl_2010

これが等価になると思う。

QuickSortの計算量は平均で O(NLogN) なので、仮に個々の子テーブルが同じ数のレコードを持っていた場合、たった４分割のケースであっても、ソートの計算量は後者の方が半分くらいで済む事になる。

もちろんプランナがもっと賢くならないとダメなんだが、Appendのパスを作る時点で『ここには後でキー"YMD"によるソートが要求される可能性がある』という事が判っていれば、pathkeys付きでAppendパスを追加してやれば良いのではなかろうか。

*1:Aggregate Before Joinとかね