PostgreSQLの列名指定をミスした時のエラーメッセージ

本エントリーは[PostgreSQL Advent Calendar 2022](https://qiita.com/advent-calendar/2022/postgresql)の3日目です。
[前日の記事はこちら](https://zenn.dev/donsan/articles/f2c2054c113d2e)です。

# はじめに
本記事はPostgreSQLのエラーメッセージについての小ネタです。新機能ではなく、また派手な内容でもありませんが、何気なくお世話になっていることも多いと思うのでトピックとして挙げてみました。

# 列名の指定をミスした場合のエラーメッセージ
PostgreSQLでの操作時に、列名をうっかり間違って指定した場合に以下のようなエラーメッセージが出力されます。
その際に、「もしかしてこの列を指定したかったのでは？」というHINTが出ます。

```
postgres=# CREATE TABLE t1 (col1 int);
CREATE TABLE

-- 存在しない列名を指定する
postgres=# SELECT col2 FROM t1;
ERROR:  column "col2" does not exist
LINE 1: SELECT col2 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.col1". <-- これ
```
このメッセージが出力されるようになったのはPostgreSQLのバージョン9.5からです。7年以上前に実装されたので、最近PostgreSQLを使い始めた方にとっては違和感はないかもしれません。9.5より前のバージョンではこのHINTは出ていませんでした。

この機能は[Peter Geoghegan氏によって提案](
https://www.postgresql.org/message-id/flat/CAM3SWZS9-Xr2Ud_j9yrKDctT6xxy16h1EugtSWmLU6Or4CtGAA%40mail.gmail.com)され、様々な議論を経て[2015年3月に本体へCommit](https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=e529cd4ffa605c6f14f1391af5559b3a44da0336)されました。現在のバージョンでは別の機能追加やリファクタリングの影響で若干の変更がされています。


# どのように候補の列名を判別しているのか？
エラーメッセージのHINTとして出力される列名は誤って指定した列名に「近い」名称が使われます。この「近い」ものは内部的に[レーベンシュタイン距離](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)を利用して算出しています。
PostgreSQLのレーベンシュタイン距離の実装は「src/backend/utils/adt/levenshtein.c」にあります。
なお、実装として参考にしたアルゴリズムへのリファレンスリンクがコード上にありますが、すでにデッドリンクとなっています。おそらくこの[リンク先の説明が元々参照されているものかと思います。](https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm)
アルゴリズムに関してはこのリンク先を見ていただくのが一番分かりやすいですが、端的にはソースとなる文字列(ユーザが指定した列名）とターゲットとなる文字列(実際にテーブルが持つ列名)を順次照わせていき、ソースがターゲットと同じ文字列になるまでに必要となる文字の挿入・削除・置換の回数を距離として算出します。この距離が短いものを候補としています。

PostgreSQLでのこのエラーメッセージ出力においては、挿入・削除・置換はそれぞれ同一のコストで評価しており、例えば「col1」という文字列に対しては「col (要1文字追加)」「col12 (要1文字削除)」「col2 (要1文字置換)」はそれぞれ同じ距離となります。

# エラーメッセージ出力の流れ
PostgreSQLで前述のHINTを含めたエラーメッセージの出力までの流れはおおよそ以下となります。

1. パース時にSELECTなどで指定された列名が実際に存在するかをシステムカタログへ探しに行く。(`transformColumnRef()`)
1. 存在しない場合、`errorMissingColumn()`を呼び出しエラーメッセージを出力の準備に入る。
    - この関数内で`searchRangeTableForCol()`を呼び出し、指定された列名を含むであろうテーブル群に対して`scanRTEForColumn()`を順次実行する。
        - この関数内で各列名に対して`updateFuzzyAttrMatchState()`が順次実行される。
            - この関数内でユーザが指定した列名と実際の各列名とのレーベンシュタイン距離を測る`varstr_levenshtein_less_equal()`が呼ばれる。
        - 得られた距離と対象の情報について`fuzzystate`という構造体に記録される
            - この構造体には現在の最小距離、および最小距離と同距離となる最大2つの列名をもつテーブルと列の位置が記録される
            - 基本的には各列をサーチ&評価し、最小の距離となるものが見つかり、かついくつかの条件を満たすものであれば`fuzzystate`の情報を更新していく。
1. 全てのテーブルと列名のサーチが終わったら、得られた候補の列名(とテーブル名)を添えてエラーメッセージのHINTに出力する 。

`searchRangeTableForCol()`や`scanRTEForColumn()`は通常の処理でも使うもので、エラー処理特有のロジックは`updateFuzzyAttrMatchState()`から、になります。
上記の「いくつかの条件」ですが、以下のようなものはHINTで出力しません。

#### ４以上の距離を持つもの
レーベンシュタイン距離の結果で4以上の距離を持つものはHINTで出しても有用性に欠ける可能性が高いので除去しています。

```
postgres=# CREATE TABLE t1 (col123 int);
CREATE TABLE

-- 3文字の置換で正解になるのでHINTあり
postgres=# SELECT abc123 FROM t1;
ERROR:  column "abc123" does not exist
LINE 1: SELECT abc123 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.col123". <-- HINTあり

-- 以下は4文字の置換が必要になるのでHINTなし
postgres=# SELECT abc023 FROM t1;
ERROR:  column "abc023" does not exist
LINE 1: SELECT abc023 FROM t1;
               ^
-- 以下も4文字の追加が必要になるのでHINTなし
postgres=# SELECT col1234567 FROM t1;
ERROR:  column "col1234567" does not exist
LINE 1: SELECT col1234567 FROM t1;
               ^
```
#### 指定の列名文字列の過半数の距離を持つもの
レーベンシュタイン距離の結果で指定列名の文字列数の過半数以上の距離を持つものはHINTで出しても有用性に欠ける可能性が高いので除去しています。
```
postgres=# CREATE TABLE t1 (col1 int);
CREATE TABLE

--- "colabc1"は7文字、うち"abc"の３文字の除去となるためHINTあり
postgres=# SELECT colabc1 FROM t1;
ERROR:  column "colabc1" does not exist
LINE 1: SELECT colabc1 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.col1".

--- "coabc1"は6文字、うち"abc"の2文字の除去と1文字の追加となるためHINTあり
postgres=# SELECT coabc1 FROM t1;
ERROR:  column "coabc1" does not exist
LINE 1: SELECT coabc1 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.col1".

--- "cabc1"は5文字、うち"abc"の2文字の除去と1文字の置換となる5の過半数となるためHINTなし
postgres=# SELECT cabc1 FROM t1;
ERROR:  column "cabc1" does not exist
LINE 1: SELECT cabc1 FROM t1;
               ^
```
#### 最小の距離を持つものが3つ以上ある場合
レーベンシュタイン距離の最も小さいものをHINTで出力しますが、最も小さい距離に該当する列が3つ以上となった場合、多数の列がHINTに出てしまい有用性に欠ける可能性が高いので除去しています。(内部的には`fuzzystate`に蓄積した現在の最小距離の情報以外をクリアしています)

```
postgres=# CREATE TABLE t1 (col1 int, col2 int);
CREATE TABLE

-- col0に対して、col1とcol2は共に距離1となるためHINTに2つ出力される
postgres=# SELECT col0 FROM t1;
ERROR:  column "col0" does not exist
LINE 1: SELECT col0 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.col1" or the column "t1.col2".

-- col3を足して距離1となるものが3つになるとHINTは出ない
postgres=# ALTER TABLE t1 ADD COLUMN col3 int;
ALTER TABLE
postgres=# SELECT col0 FROM t1;
ERROR:  column "col0" does not exist
LINE 1: SELECT col0 FROM t1;
               ^
```
#### 日本語とかどうなの？
リーベンシュタイン距離の実装内ではマルチバイトを意識しているようで、日本語列名にも対応しています。そのため、列名が日本語であってもHINTは同じように出力されます。

```
postgres=# CREATE TABLE t1 (列名A int, 列名B int);
CREATE TABLE

postgres=# SELECT 列番号 FROM t1;
ERROR:  column "列番号" does not exist
LINE 1: SELECT 列番号 FROM t1;
               ^
HINT:  Perhaps you meant to reference the column "t1.列名a" or the column "t1.列名b".
```

# おまけ
PostgreSQLにはcontribモジュールが同梱されていますが、その中にある曖昧検索を行うための`fuzzystrmatch`という拡張機能は上記と同じリーベンシュタイン距離の処理ロジックを利用しています。
この拡張機能を使うと、同じように文字列同士の距離を測ることができます。
```
postgres=# CREATE EXTENSION fuzzystrmatch ;
CREATE EXTENSION
postgres=# select proname from pg_proc where proname like '%lev%';
        proname         
------------------------
 levenshtein
 levenshtein
 levenshtein_less_equal
 levenshtein_less_equal
(4 rows)

-- 引数で挿入、削除、置換のコストを制御できる。これは全て1(デフォルトと同じ）にした場合
postgres=# SELECT levenshtein('abc', 'def', 1, 1, 1);
 levenshtein 
-------------
           3
(1 row)

-- 置換のコストを2にした場合は距離が大きくなる
postgres=# SELECT levenshtein('abc', 'def', 1, 1, 2);
 levenshtein 
-------------
           6
(1 row)

-- ちなみに置換のコストを３にした場合は上記と変わらない
-- これは内部的に置換コストが挿入+削除を上回らないようにしているため (なので置換コストは2になっている)
postgres=# SELECT levenshtein('abc', 'def', 1, 1, 3);
 levenshtein 
-------------
           6
(1 row)
```
fuzzystrmatchで利用可能になる関数については[オンラインマニュアル](https://www.postgresql.org/docs/current/fuzzystrmatch.html#id-1.11.7.26.7)に記述があります。


# おわりに
エラーメッセージのやや地味な仕様を解説しました。目立たない機能ですが、こういうユーザビリティの向上を粛々と面白い機能を用いて実施しているのもDBMSのようなミドルウェアの魅力だと思います。日頃見ているメッセージなども「あれ、これどうやって出力してるんだろう？」と疑問を持って仕組みを掘り下げてみると、新しい発見があるかもしれません。

[明日はそーだいさんのネタ](https://soudai.hatenablog.com/entry/2022/12/04/115037)です。楽しみですね！