ICTSC2024 本戦問題解説: [OQC] IMOCON（いい感じにメモリを抑えろコンテスト）

2025.03.31

ICTSC2024 問題解説サーバー関連

問題文

ストーリー

じゃがいもを栽培する組織「OIMO（Organization of IMO）」は、採れたじゃがいものデータをデータベースに保存し、高品質なじゃがいもの研究を進めていた。
とくに、ゴツゴツとした形状が栄養価に影響を与えるという研究結果があり、そのデータは貴重だった。

OIMOの研究開発部門に所属するNさんは、ある日データベースを眺めていて、あることに気がついた。
shape テーブルがディスクを大量に消費していたのだ。
原因は slices というカラムに保存された形状データで、じゃがいもをスライスした各パーツの体積データが並んでいるが、そのまま保存してしまっている。
このままでは、5年も経たずにディスクがいっぱいになってしまう。

フライドポテトをくわえて見るしかできないNさんだったが、ふと、PostgreSQLにはユーザー拡張を作れることを思い出した。
独自の関数を作ってデータを圧縮すれば、ディスク使用量を削減できるかもしれない。
部門長に相談すると、「ぜひやってくれ。ただし、形状データは重要だ。情報を失わせるなよ。」と許可をもらえた。

早速を作っていこう。
まずは形状データの分析だ。

shape.slicesのサンプル値

なるほど、やっぱりじゃがいもの形だ。
よくみると隣り合う要素の差分が小さいな。
ならば、差分配列をつくればよいはず・・・。

よし！C言語でPostgreSQLの関数を作っていくぞ。

・・・できた！移行して・・・って、あれー？全然サイズが抑えられなかったよ・・・。
リフレッシュにRustのpgrxでもやってみるか・・・うわー全然だめだ〜。

概要

shape テーブルのデータを情報量を失わずにかつ、なるべくディスク使用量を抑えられるような圧縮データを保持するテーブル compressed_table を作成してください。
ただし、圧縮データの解凍時間が著しく長い、ということは避けてください。

遺産として圧縮・解凍関数を定義したC言語とRust言語のソースがありますが、うまくデータを圧縮できないトラブルを抱えています。
これらのソースの活用は任意です。

前提条件

shape テーブルと対応する圧縮データを持った compressed_table テーブルを作成すること
- データを複数のテーブルにまたがせることや、テーブル外の情報をデータを参照させることは禁止である
  - ただし、compressed_table_pkey や compressed_table_id_seq などの副次的なテーブルについては不問である
- compressed_table のカラムは変更可能であり、とくに複数のカラムを定義してもよい
- compressed_table.id は必ず含め、型や制約は SERIAL PRIMARY KEY とすること
実装した、もしくは存在する、圧縮・解凍関数を使用し、shape.slices を圧縮・解凍できるようにすること
- 複数の関数を定義してもよい
shape が初期状態であり、テストSQL文を実行して、(0 rows) が得られたら、正しい解答と判定される
報告書には、プロファイリングSQL文とその結果とテーブルのデータ使用量を含めること
プロファイリングや使用量の測定は「テスト」の項目を参照すること

操作

接続先ではC言語とRust言語の環境が提供され、それを用いてPostgreSQLの拡張（関数）を作成することができる。
拡張の作成は必須ではない。

C言語

/home/user/csrc/ ディレクトリにC言語のプロジェクトが存在する。
以下、ワーキングディレクトリはそこであるとする。

oqc.c を編集し、compress_function や decompress_function の修正・追加を行う。
関数を変更した場合は、PG_FUNCTION_INFO_V1() マクロや oqc--0.0.0.sql も適宜修正する必要がある。
編集後、$ sudo make install を実行して拡張をコンパイル・インストールを行う。

拡張のインストール後はpsqlの項を参照すること。

Rust言語(pgrx)

/home/user/rustsrc/oqc/ ディレクトリにRust言語のプロジェクトが存在する。
プロジェクトはpgrxクレートを使用している。

src/lib.rs を編集し、compress_function や decompress_function の修正・追加を行う。
変更後、$ cargo pgrx install --release -s を実行して拡張をコンパイル・インストールを行う。

$ cargo pgrx run などでサーバーが起動されるが、これは既存のPostgreSQLとは異なるインスタンスのため使用は推奨されない。

拡張のインストール後はpsqlの項を参照すること。

psql

$ psql コマンドによって操作するデータベース環境に入ることができる。

インストールしたPostgreSQL拡張は以下のコマンドで導入できる。
拡張のインストールの度に、このコマンドを実行する必要があることに注意する。

DROP EXTENSION oqc;
CREATE EXTENSION oqc;

導入した拡張によって導入される関数は以下のコマンドによって確認できる。

\dx+ oqc

以下のSQL文は圧縮データを保存するテーブルを作成する。idを除いたカラム情報は好きに設定できる。

CREATE TABLE compressed_table (
    id SERIAL PRIMARY KEY,
    slices integer[]
);

以下のSQL文は作成したテーブルに、圧縮関数で圧縮された slice のデータをすべて挿入し、目的のテーブルを作成する。
定義したテーブル情報や関数名にしたがって適切に書き換えてよい。

INSERT INTO compressed_table (id, slices)
SELECT
    id, compress_function(slices)
FROM
    shape;

やり直し等でテーブルの中身やテーブルを削除するときは以下のSQL文を用いるとよい。

-- テーブルのデータの全削除
TRUNCATE compressed_table;

-- テーブルの削除
DROP compressed_table;

誤って shape テーブルに変更を加えてしまった場合は、以下を実行すると初期状態に復旧できる。

DROP TABLE shape;
CREATE TABLE shape (
    id SERIAL PRIMARY KEY,
    slices integer[]
);
\COPY shape FROM '/home/user/shape.csv' WITH CSV

テスト

以下、解答のテストや評価の上で必要となるSQL文の雛形を提供する。

decompress_function は解凍関数であり、解答に応じて適宜書き換える必要がある。

テストSQL文は以下の通りである。

WITH
original AS (
    SELECT id, slices FROM shape
),
decompressed AS (
    SELECT id, decompress_function(slices) AS slices FROM compressed_table
)
SELECT
    COALESCE(o.id, d.id) AS id,
    CASE
        WHEN o.id IS NULL THEN '❌ 圧縮テーブルにのみ存在'
        WHEN d.id IS NULL THEN '❌ 元データテーブルにのみ存在'
        WHEN o.slices != d.slices THEN '❌ データ不一致'
    END AS status
FROM
    original o
FULL OUTER JOIN
    decompressed d
ON
    o.id = d.id
WHERE
    o.id IS NULL OR d.id IS NULL OR o.slices != d.slices
ORDER BY id;

プロファイリングSQL文は以下の通りである。

EXPLAIN (ANALYZE)
SELECT
    id, decompress_function(slices)
FROM
    compressed_table;

テーブル使用量を測定するコマンドは以下の通りである。

\dt+ compressed_table

プロファイリングSQL文の実行例とその出力を示す。
Execution Timeの値を参照して実行時間は評価される。この場合では0.785798秒と評価される。

                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Seq Scan on compressed_table  (cost=0.00..27690.40 rows=131072 width=36) (actual time=0.052..779.241 rows=131072 loops=1)
 Planning Time: 0.255 ms
 Execution Time: 785.798 ms
(3 rows)

テーブル使用量の測定の例を以下に示す。
Sizeの大きさにしたがってテーブル使用量は評価され、この場合では204MBと評価される。

                                   List of relations
 Schema |       Name       | Type  | Owner | Persistence | Access method |  Size  | Description
--------+------------------+-------+-------+-------------+---------------+--------+-------------
 public | compressed_table | table | user  | permanent   | heap          | 204 MB |
(1 row)

初期状態

compressed_table テーブルのサイズ使用量が200MB以上

終了状態

shape の圧縮されたデータが入った1つのテーブルcompressed_tableを作成する
テストSQL文の実行結果が (0 Rows) である
- テーブル設計にしたがって解凍部分に変更を加えてよい
プロファイリングSQLの実行時間が 5秒以下である
- テーブル設計にしたがって解凍部分に変更を加えてよい
ディスク使用量によって得られる得点は以下の通りである
- 150MB〜 0点
- 120〜149MB 20点
- 60〜119MB 50点
- 40〜59MB 150点
- 30〜39MB 200点（満点）
- 〜29MB 200点（満点）+ 名誉
報告書には、プロファイリングSQL文とその結果とテーブルのデータ使用量を記載すること
- 雛形から大きく逸脱したSQL文を提出した場合、0点と採点される場合がある
テーブルのテストや評価方法は「テスト」の項目を参照すること

解説

初期状態では、4000-5000程度の値を持つ配列がinteger型（32bit整数）で保存されており、非効率でした。

解法の要点は、隣接要素の差分を利用し、より小さい型や効率的なデータ形式で保存することです。

50点解法
- integer[]をsmallint[]（16bit整数）に変更
- 111MB
150点解法
- 差分を8bit整数で表現し、bytea型（バイト配列）で保存
- 最初の要素は別途保持（2byteで表現する、カラムを追加するなど）
- 56MB
満点解法
- 差分を4bit整数で表現し、byteaの1要素に2の差分を格納
- 配列長を別途保持（byteaの長さから要素数が単射でないため）
- 31MB

講評

圧縮・解凍の戦略を考え、実装することが主に求められる問題となり、今までのICTSCの中ではかなり趣旨が異なる問題でした。
それでも半数以上のチームが150点以上を獲得しており、参加者の守備範囲の広さを感じました。

想定解答の他にもzlibやlz4などの圧縮ライブラリを用いて、圧縮・解凍を行う解法がありました。
これらの使用は圧縮効率を求めると解凍時間が長くなるため、満点を取るための高圧縮が難しかったと考えられます。

なお、「OIMO」は架空の組織であり、実在の組織とは関係ありません。

名誉解法解説

29MBを達成する解法を紹介します。

キーワードは「グループ分け」と「連長圧縮」です。
差分配列を区間でグループ分けし、要素を3bitとグループ情報で表現することを考えます。

差分配列の値の遷移に着目すると、正負が連続しやすいことから「-8以上、-1以下」と「0以上、7以下」の2つのグループに分けます。
差分配列の要素はグループの所属に応じて3bit整数で表現し、要素がどのグループに属するかは連長圧縮のアイディアを利用します。
具体的には、1byte内にグループの情報（1bit）と長さ（7bit）を持たせることで表現します。

しかし、この方法では33MBにしか圧縮できませんでした。
原因は、ブレによる差分の値の -1と0の切り替わりが多く、グループ分けの連続率が低下してしまったことです。

そこで、ブレに強いグループ分けを編み出す必要があります。
一アイディアとして、新たに「-4以上、3以下」というグループを追加し、3つのグループに分けることにします。
この追加により、グループ情報のビット数は増えますが、ブレによる耐性が向上し、グループ分けの連続率が向上します。
グループ分けは動的計画法によって最適化できますが、想定解では貪欲法でグループ分けしました。
これによって、29MBを達成しました。

残念ながら29MB以下を叩き出し、OIMOの名誉を獲得した解答はコンテスト中にはありませんでした。

ICTSC2024 本戦 問題解説: [OQC] IMOCON（いい感じにメモリを抑えろコンテスト）

問題文