SQLによる数独の解法 #deim2010

2/28から3/2にかけて開催されたDEIM2010で発表してきました。

ワークショップの様子

  1. Togetter – まとめ「DEIM2010 初日」
  2. Togetter – まとめ「DEIM2010 2日目」
  3. Togetter – まとめ「DEIM2010 最終日」

「データベースの授業で使いたい」というコメントを多くの方からいただいたので、そのためのマテリアルを公開します。

論文の最終版は後で公開します。

論文:矢吹太朗, 佐久田博司. SQLによる数独の解法とクエリオプティマイザの有効性. 日本データベース学会論文誌. Vol.9, No.2, pp.13–18, 2010.

参考:数独の平凡な解法(C言語Mathematica

寛容なMySQLを非寛容にすること(その3)

結論:MySQLのsql_modeには、ONLY_FULL_GROUP_BYを入れておく

ユーザを管理するテーブルを考える。ユーザはa, bという2つの属性を持つ。テーブルはこんな感じ。

CREATE TABLE users (
id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
a INT,
b INT,
INDEX (a),
INDEX (b)
);
INSERT users (a,b) VALUES (1,1);
INSERT users (a,b) VALUES (1,2);
INSERT users (a,b) VALUES (1,3);
SELECT * FROM users;
+----+------+------+
| id | a    | b    |
+----+------+------+
|  1 |    1 |    1 |
|  2 |    1 |    2 |
|  3 |    1 |    3 |
+----+------+------+

属性aが1の人数は、次のように求められる。

SELECT count(*)
FROM users
WHERE a=1;
+----------+
| count(*) |
+----------+
|        3 |
+----------+

何かの事情でaの値も取得したいとき、安易に次のように書いてしまうかもしれない。

SELECT a,count(*)
FROM users
WHERE a=1;
+------+----------+
| a    | count(*) |
+------+----------+
|    1 |        3 |
+------+----------+

上のSELECT文は、手元のMySQL 5.0.84と5.1.37-1ubuntu5, 5.4.3-beta-communityでは動作する。しかし、MySQL 5.0.45-logでは次のようなエラーになる。

ERROR 1140 (42000): Mixing of GROUP columns (MIN(),MAX(),COUNT(),...) with no GROUP columns is illegal if there is no GROUP BY clause

リファレンスマニュアルの3.3.4.8. Counting Rowsには、上のようなSELECT文は可能だという記述があるのだが、うまくいかない環境もある(「SET sql_mode='';」としてもだめ)。

次のように書けば、どの環境でも動く。一般的に、集約関数があるときは、SELECTするものはGROUP BYの対象になっていなければならない(最初のSELECT文を実行できたのは、MySQLの独自の拡張のため)。

SELECT a,count(*)
FROM users
WHERE a=1
GROUP BY a;

SELECT a,count(*) FROM users GROUP BY a HAVING a=1;」と書いてもいいが、これを素朴実行したらさすがに遅いだろう(オプティマイザが上の形に変換してくれるとも思えない)。

このようなバージョンによる振る舞いのぶれを無くすためには、「SET sql_mode='ONLY_FULL_GROUP_BY';」として、SQLモードを変更し、MySQLの独自の拡張を無効にすればよい。こうすることによって、以下のSELECT文はすべてのバージョンでエラーになる。(ちなみに、現在のSQLモードは「SELECT @@sql_mode;」でわかる。)

SET sql_mode='ONLY_FULL_GROUP_BY';
SELECT a,count(*)
FROM users
WHERE a=1;
ERROR 1140 (42000): Mixing of GROUP columns (MIN(),MAX(),COUNT(),...) with no GROUP columns is illegal if there is no GROUP BY clause

そもそも、曖昧なSELECT文を実行させるような独自拡張に何の意義があるのだろうか。リファレンスマニュアルの12.16.3 MySQL Handling of GROUP BYには、You can use this feature to get better performance by avoiding unnecessary column sorting and groupingとあるから、パフォーマンスがよくなる可能性はある。本稿の例ではaの値は1しかないため、「GROUP BY a」をしなくて済むならそれに越したことはない。しかし、これはわざと作った例であり、実際にこういうことがうれしいという状況にあるときは、何かおかしなことをしているという自覚があるべきだろう(先に書いた「何かの事情」とはそういうことだ)。

それよりも、何か間違ったことをしているのに、MySQLの寛容さのためにその発見が遅れることがこわい。そういうことにならないための安全策として、普段から、曖昧なSELECT文を許容しないようにMySQLを設定しておくといいだろう。具体的には、my.cnfあるいはmy.iniの[mysqld]のセクションに、「sql-mode="ONLY_FULL_GROUP_BY"」と書いておけばよい。

もっと非寛容にしたい向きは、リファレンスマニュアルの5.1.7. Server SQL Modesから、それらしいものを見繕ってくればいい。TRADITIONAL(STRICT_TRANS_TABLES, STRICT_ALL_TABLES, NO_ZERO_IN_DATE, NO_ZERO_DATE, ERROR_FOR_DIVISION_BY_ZERO, NO_AUTO_CREATE_USERをまとめたもの)あたりから試すのがおすすめか。

お約束ですが、こういう話を基本から学びたいという方には、拙著『Webアプリケーション構築入門 実践!Webページ制作からマッシュアップまで 』(森北出版, 2011)がおすすめです。

SSD時代のデータベース管理システム

Solid Stateには近づくな

単純な読み書き性能のベンチマークはよく目にする一方で、(学術論文は別にして)あまり目にすることがなかったデータベース運用におけるHDDとSSDの違いについての解説記事が、2本立て続けに出ました。

SSDにはSingle-line Cell (SLC)とMulti-line Cell (MLC)の2種類があり、一般的にSLCは高速・小容量・長寿命、MLCは低速・大容量・短寿命です。定評のあるインテルの製品はどちらもAmazonにありますが、SLCであるX25-Mでは、価格がずいぶん違います。ノートPCに搭載されているものの大部分はMLCでしょう。

閑話休題

斉藤さんの記事では、データベースシステムの仕組みをまず解説し、それを踏まえてB+tree(挿入と大量SELECT)についてのベンチマーク、External Merge Sortについての学術論文紹介、トランザクション管理についての考察がなされています。アカデミックな雰囲気のある解説です。

松信さんの記事では、(HDDが苦手とする)インデックススキャン、(HDDが得意な)フルテーブルスキャン、(SSDが苦手だと予想される)更新系処理(DBT-2)の性能が調べられています。MySQLで利用する際に、SSDにデータを、HDDにREDOログとシステムテーブルスペースを置くと性能が50%以上向上するといった実践的な知識が得られます。

性能が上がれば単純にうれしいわけですが、HDDで使うことを(暗黙の)前提として作られていることが多いRDBMSのアーキテクチャが、SSDの普及とともに変わっていくのかどうかに私の興味はあります。

この点について、2本の記事の印象はずいぶん違います。

斉藤さんの記事を信じるなら、RDBMSのアーキテクチャは変わらないということになります。

従来使っていたHDDをSSDに取り替えるだけでDBMS自体はそのまま使える、という雰囲気になっています。(p.108)

既存のアーキテクチャのままで、HDDとSSDという性能特性のまったく違った記憶装置に対応できるなら、それはすばらしいことです。

松信さんの記事を信じるなら、RDBMSのアーキテクチャもアプリケーションもに大きく変わるということになります。

単なる著者の考察にすぎないので異論を持つ方もいるだろうが、活発な議論をして業界を盛り上げていけたらと思う。(p. 160)

データベースのアーキテクチャが劇的に変わる現場に遭遇できたら、それはすばらしいことです。

要注目です。

関連:HDD単体とRAID 0、SSDの比較

関連:容量の大きいSSD1台の性能、容量の小さいSSD2台によるRAIDの性能

SQL Server Express Editionで大量のデータを読み込む方法

拙著『Webアプリケーション構築入門』では、ウェブアプリの簡単な例として、郵便番号検索システムを、Javaを使って構築しています。(改訂版

ウェブアプリに関してはもう1冊著書があります。『Microsoft Visual Web Developer 2008 Express Edition入門』です。こちらはASP.NET(C#あるいはVisual Basic)なのですが、『Webアプリケーション構築入門』で作成した程度の簡単な郵便番号検索システムなら、こちらのほうが簡単に構築できます。

しかし、郵便番号データをSQL Server Express Editionで使えるようにするのが少し面倒なので、その方法を紹介します。(この点に関して言えば、SQL Server Express EditionよりもMySQLのほうがはるかに簡単です。)

まず、郵便番号データをダウンロードします。「読み仮名データの促音・拗音を小書きで表記するもの」の「全国一括」でいいでしょう。ダウンロードしたファイルを展開し、テキストファイル内の二重引用符を削除し、カンマをタブに置き換えておきます(後述のformat.fmtの「\t」を「,」にするなら、カンマの変換は実は不要です)。

Visual Web Developer(VWD, Visual Studioのウェブアプリ用無償版)上では、大量のデータを読み込むためのBULK INSERT文が(たぶん)使えないので、SQL Server Management Studioでデータベースとテーブルを作り、それをVWDで使うことにします。

データベースを作ります。

データベース名は「mydb」にしましょう。

GUIでテーブルを作るのは面倒なので、SQLを使います。

実行するSQLはこんな感じです。

USE [mydb]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[zips](
[jis] [char](10) NOT NULL,
[old_zip] [char](5) NOT NULL,
[zip] [char](7) NOT NULL,
[addr1_ruby] [ntext] NOT NULL,
[addr2_ruby] [ntext] NOT NULL,
[addr3_ruby] [ntext] NOT NULL,
[addr1] [ntext] NOT NULL,
[addr2] [ntext] NOT NULL,
[addr3] [ntext] NOT NULL,
[establishment_ruby] [ntext] NOT NULL,
[establishment] [ntext] NOT NULL
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO
SET ANSI_PADDING OFF
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_jis]  DEFAULT ('') FOR [jis]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_addr1_ruby]  DEFAULT ('') FOR [addr1_ruby]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_zips_addr1]  DEFAULT ('') FOR [addr1]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_establishment_ruby]  DEFAULT ('') FOR [establishment_ruby]
GO
ALTER TABLE [dbo].[zips] ADD  CONSTRAINT [DF_establishment]  DEFAULT ('') FOR [establishment]
GO

貼り付けて、右クリック→実行。

できたテーブルは「デザイン」で確認できます。

実は、先にあげたSQL文は、GULで作ったテーブルを「スクリプト化」したものです。(GUIは説明には不向きです。)

テーブルができたので、テキストファイルのデータをテーブルにロードします。

まず、テキストファイルとテーブルの対応関係を記述したファイルformat.fmtを用意します。(ファイルの書き方SQLCHAR等について

format.fmt
10.0
10
1 SQLCHAR 0 10 "\t" 1 jis ""
2 SQLCHAR 0 5 "\t" 2 old_zip ""
3 SQLCHAR 0 7 "\t" 3 zip ""
4 SQLCHAR 0 500 "\t" 4 addr1_ruby ""
5 SQLCHAR 0 500 "\t" 5 addr2_ruby ""
6 SQLCHAR 0 500 "\t" 6 addr3_ruby ""
7 SQLCHAR 0 500 "\t" 7 addr1 ""
8 SQLCHAR 0 500 "\t" 8 addr2 ""
9 SQLCHAR 0 500 "\t" 9 addr3 ""
10 SQLCHAR 0 500 "\r\n" 0 dummy ""

BULK INSERT文で郵便番号データを読み込みます。(参考:BULK INSERT文の詳細)。

BULK INSERT [dbo].[zips]
FROM 't:\KEN_ALL_CP932.TSV'
WITH(FORMATFILE='t:\format.fmt',CODEPAGE=932)

データを読み込み終わったら、データベースを「デタッチ」します。

このデータベースのファイルmydb.mdfをVWDのソリューション・エクスプローラでフォルダApp Dataにドラッグ&ドロップすれば、ウェブアプリから利用できます。

完成したデータベースのファイルmydb.mdf

「郵便番号検索システムの作成(ASP.NETチュートリアル)」に続く

米MS、特許主張しない約束をC#とCLI標準に適用、Monoはソースコードを2分割へ