木構造のデータ・サンプルとして、次のような階層の深さが3の組織図を例に取りましょう。一つのノードは、複数の親を持つことはない（＝複数の上司を持たない）、かつ必ず一つの親を持つ（＝命令系統から外れる社員がいない）と仮定します。この条件を破ると、木構造ではなくなってしまいます。 図1-1. 木構造の組織図 一般的な隣接リストモデルでこのデータを表現...
データベースを操作するための言語であるSQLを別の用途に使おうとする理由は、SQLが宣言的な記述が可能な言語の中で最も普及していると思われるからです（宣言的言語と言えばPrologを思い浮かべる方も多いかもしれませんが、残念なことにPrologは、SQLほどには普及していません）。 まず、宣言的な記述について説明しましょう。タクシーに乗ることを想像してください。「...
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）...
はuserpwdプログラムのソースリストである。Perlで書かれたプログラムで，DBIインタフェース（注１）を使用してMySQL（注２）データベースへアクセスする。 5〜7行目では，コマンドライン引数からユーザ名，現在のパスワード，新しいパスワードをそれぞれ変数$user，$curpwd，$newpwdに受け取る。10行目はDBIインタフェースを使用してデータベースへ接続する（注３）。13〜14行目で受け...
「データへの最短ルート」とは、最も効率的なアクセスパス（実行計画）のこと。SQLチューニングはDBエンジニアの晴れ舞台といえる
データベースというよりは、トランザクション処理ネタなのですが、皆さんは、データベースのトランザクション処理を実行される場合、対象となる行をどのように排他制御されていますか。排他制御というのは、同時実行処理において必要不可欠なものなのですが、使い方を誤ると簡単なはずの処理が難しくなってしまう可能性があります。一般的にリソース（資源）をロック...
フレンド・タイムライン処理の原理と実践 の続きです。 先のエントリでは、プルモデルの速度が当初予測していたよりも遅かった (というより SQL レイヤでのオーバーヘッドが大きそうだった) ので、MySQL Internals メーリングリストで質問したりしながら、C++ で直接 InnoDB にアクセスするようなコードを書いてみました。 タイムライン構築速度 タイムライン/秒 SQL56.7 ストアド...
Wikipediaめくりでは、MySQLに格納したWikipedia記事をランダムに表示している。速度を気にしないなら、 SELECT * FROM docs ORDER BY RAND() LIMIT 10; で良いのだけど、レコード数が多いと遅くて使いものにならない。そこで、記事IDを1から始まる連番になるようにDBに格納している。このようにすると、アプリケーション側でDBに格納されている文書IDが全て分かるので、ランダムに文書IDを10個選...
SELECT item, tag, log2(tf.times + 1) / log2(total) * (log2(n / df.times) + 1) AS tfidf FROM tf LEFT JOIN df USING(tag) LEFT JOIN (SELECT item, count(tag) total FROM tf GROUP BY item) AS a USING(item) CROSS JOIN (SELECT count(id) AS n FROM items) AS b WHERE item="j"; 実際はユーザ変数を使った方がSQLが短くなっていいと思う。 SELECT @total := count(tag) FROM tf WHERE item = "j"; SELECT @n := count(id) FROM items; SELECT item, tag, log2(tf.times + 1) / log2(@total) * (log2(@n / df.times)...
先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても...
