このSQLiteクエリをもっと高速化できますか？

Question

私は、セキュリティカメラNVRのメタデータを表すデータベースを持っています。ビデオの1分のセグメントごとに26バイトのrecording行があります。 （あなたが好奇心が強いなら、設計書は進行中ですhere）私の設計限界は8台のカメラで、1年（400万行、カメラごとに50万）です。パフォーマンスをテストするためにいくつかのデータを偽造しました。ただ、カメラのすべてのデータをスキャンし、他のカメラと順序をフィルタリングするためのインデックスを使用しています

select 
    recording.start_time_90k, 
    recording.duration_90k, 
    recording.video_samples, 
    recording.sample_file_bytes, 
    recording.video_sample_entry_id 
from 
    recording 
where 
    camera_id = ? 
order by 
    recording.start_time_90k; 

を：このクエリは、私が予想よりも遅くなります。インデックスは次のようになります。

create index recording_camera_start on recording (camera_id, start_time_90k); 

explain query planは予想通りになります。

0|0|0|SEARCH TABLE recording USING INDEX recording_camera_start (camera_id=?) 

行が非常に小さいです。

$ sqlite3_analyzer duplicated.db 
... 

*** Table RECORDING w/o any indices ******************************************* 

Percentage of total database...................... 66.3% 
Number of entries................................. 4225560 
Bytes of storage consumed......................... 143418368 
Bytes of payload.................................. 109333605 76.2% 
B-tree depth...................................... 4 
Average payload per entry......................... 25.87 
Average unused bytes per entry.................... 0.99 
Average fanout.................................... 94.00 
Non-sequential pages.............................. 1   0.0% 
Maximum payload per entry......................... 26 
Entries that use overflow......................... 0   0.0% 
Index pages used.................................. 1488 
Primary pages used................................ 138569 
Overflow pages used............................... 0 
Total pages used.................................. 140057 
Unused bytes on index pages....................... 188317  12.4% 
Unused bytes on primary pages..................... 3987216  2.8% 
Unused bytes on overflow pages.................... 0 
Unused bytes on all pages......................... 4175533  2.9% 

*** Index RECORDING_CAMERA_START of table RECORDING *************************** 

Percentage of total database...................... 33.7% 
Number of entries................................. 4155718 
Bytes of storage consumed......................... 73003008 
Bytes of payload.................................. 58596767 80.3% 
B-tree depth...................................... 4 
Average payload per entry......................... 14.10 
Average unused bytes per entry.................... 0.21 
Average fanout.................................... 49.00 
Non-sequential pages.............................. 1   0.001% 
Maximum payload per entry......................... 14 
Entries that use overflow......................... 0   0.0% 
Index pages used.................................. 1449 
Primary pages used................................ 69843 
Overflow pages used............................... 0 
Total pages used.................................. 71292 
Unused bytes on index pages....................... 8463   0.57% 
Unused bytes on primary pages..................... 865598  1.2% 
Unused bytes on overflow pages.................... 0 
Unused bytes on all pages......................... 874061  1.2% 

... 

は、私はこのような何か（時多分月だけではなく、通期）は、特定のWebページがヒットするたびに実行されることを希望ので、私はそれが非常に高速になりたいです。しかし、私のラップトップでは、それはほとんどの時間がかかります。そして、ラズベリーパイ2で私はサポートしたい、それは遅すぎます。以下の時間（秒）。それはCPUバウンドです（ユーザー+ SYS時〜=リアルタイム）：

laptop$ time ./bench-profiled 
trial 0: time 0.633 sec 
trial 1: time 0.636 sec 
trial 2: time 0.639 sec 
trial 3: time 0.679 sec 
trial 4: time 0.649 sec 
trial 5: time 0.642 sec 
trial 6: time 0.609 sec 
trial 7: time 0.640 sec 
trial 8: time 0.666 sec 
trial 9: time 0.715 sec 
... 
PROFILE: interrupts/evictions/bytes = 1974/489/72648 

real 0m20.546s 
user 0m16.564s 
sys  0m3.976s 
(This is Ubuntu 15.10, SQLITE_VERSION says "3.8.11.1") 

raspberrypi2$ time ./bench-profiled 
trial 0: time 6.334 sec 
trial 1: time 6.216 sec 
trial 2: time 6.364 sec 
trial 3: time 6.412 sec 
trial 4: time 6.398 sec 
trial 5: time 6.389 sec 
trial 6: time 6.395 sec 
trial 7: time 6.424 sec 
trial 8: time 6.391 sec 
trial 9: time 6.396 sec 
... 
PROFILE: interrupts/evictions/bytes = 19066/2585/43124 

real 3m20.083s 
user 2m47.120s 
sys 0m30.620s 
(This is Raspbian Jessie; SQLITE_VERSION says "3.8.7.1") 

は、私はおそらく非正規化データのいくつかの並べ替えを行って終わるだろうが、最初私はこの単純なクエリを取得することができるかどうかを確認したいのですができるだけ早く実行することができます。私のベンチマークはとてもシンプルです。それは、事前に文を準備し、この上でループする：私はgperftoolsとCPUのプロファイルを作っ

void Trial(sqlite3_stmt *stmt) { 
    int ret; 
    while ((ret = sqlite3_step(stmt)) == SQLITE_ROW) ; 
    if (ret != SQLITE_DONE) { 
    errx(1, "sqlite3_step: %d (%s)", ret, sqlite3_errstr(ret)); 
    } 
    ret = sqlite3_reset(stmt); 
    if (ret != SQLITE_OK) { 
    errx(1, "sqlite3_reset: %d (%s)", ret, sqlite3_errstr(ret)); 
    } 
} 

。画像：

$ google-pprof bench-profiled timing.pprof 
Using local file bench-profiled. 
Using local file timing.pprof. 
Welcome to pprof! For help, type 'help'. 
(pprof) top 10 
Total: 593 samples 
    154 26.0% 26.0%  377 63.6% sqlite3_randomness 
    134 22.6% 48.6%  557 93.9% sqlite3_reset 
     83 14.0% 62.6%  83 14.0% __read_nocancel 
     61 10.3% 72.8%  61 10.3% sqlite3_strnicmp 
     41 6.9% 79.8%  46 7.8% sqlite3_free_table 
     26 4.4% 84.1%  26 4.4% sqlite3_uri_parameter 
     25 4.2% 88.4%  25 4.2% llseek 
     13 2.2% 90.6%  121 20.4% sqlite3_db_config 
     12 2.0% 92.6%  12 2.0% __pthread_mutex_unlock_usercnt (inline) 
     10 1.7% 94.3%  10 1.7% __GI___pthread_mutex_lock 

これは私はそれが改善されることを願って与えるのに十分奇妙に見えます。たぶん私は何かばかげたことをしている。

• ドキュメントはsqlite3_randomnessは、いくつかの状況でROWIDを挿入するために使用されていると言うが、私は選択クエリをやってる：私はsqlite3_randomnessとsqlite3_strnicmp操作の特に懐疑的です。なぜそれを今使っているのですか？スキミングsqlite3のソースコードから、私はそれがsqlite3ColumnsFromExprListのために選択で使用されているが、それは文を準備するときに起こるだろうと思われる。私は一度それをやっています、ベンチマークされている部分ではありません。
• strnicmpは、大文字と小文字を区別しない文字列比較です。しかし、この表の各フィールドは整数です。なぜこの機能を使用していますか？それは何を比較していますか？
• 一般に、なぜsqlite3_resetが高価であるのか、それがsqlite3_stepから呼び出される理由がわかりません。

スキーマ：私は私のテストデータ+テストプログラムをアップしましたタール

-- Each row represents a single recorded segment of video. 
-- Segments are typically ~60 seconds; never more than 5 minutes. 
-- Each row should have a matching recording_detail row. 
create table recording (
    id integer primary key, 
    camera_id integer references camera (id) not null, 

    sample_file_bytes integer not null check (sample_file_bytes > 0), 

    -- The starting time of the recording, in 90 kHz units since 
    -- 1970-01-01 00:00:00 UTC. 
    start_time_90k integer not null check (start_time_90k >= 0), 

    -- The duration of the recording, in 90 kHz units. 
    duration_90k integer not null 
     check (duration_90k >= 0 and duration_90k < 5*60*90000), 

    video_samples integer not null check (video_samples > 0), 
    video_sync_samples integer not null check (video_samples > 0), 
    video_sample_entry_id integer references video_sample_entry (id) 
); 

。 hereをダウンロードできます。

---

編集1：

ああ、SQLiteのコードを見、私は手がかりを参照してください。

int sqlite3_step(sqlite3_stmt *pStmt){ 
    int rc = SQLITE_OK;  /* Result from sqlite3Step() */ 
    int rc2 = SQLITE_OK;  /* Result from sqlite3Reprepare() */ 
    Vdbe *v = (Vdbe*)pStmt; /* the prepared statement */ 
    int cnt = 0;    /* Counter to prevent infinite loop of reprepares */ 
    sqlite3 *db;    /* The database connection */ 

    if(vdbeSafetyNotNull(v)){ 
    return SQLITE_MISUSE_BKPT; 
    } 
    db = v->db; 
    sqlite3_mutex_enter(db->mutex); 
    v->doingRerun = 0; 
    while((rc = sqlite3Step(v))==SQLITE_SCHEMA 
     && cnt++ < SQLITE_MAX_SCHEMA_RETRY){ 
    int savedPc = v->pc; 
    rc2 = rc = sqlite3Reprepare(v); 
    if(rc!=SQLITE_OK) break; 
    sqlite3_reset(pStmt); 
    if(savedPc>=0) v->doingRerun = 1; 
    assert(v->expired==0); 
    } 

これは、スキーマの変更にsqlite3_step通話sqlite3_resetのように見えます。私の文がしかし用意したので、スキーマの変更があるだろう、なぜ私にはわからない（FAQ entry）...

---

編集2：私はSQLiteの3.10.1をダウンロード

「amalgationデバッグシンボルでコンパイルします。私は変わったように見えない、今はかなり異なるプロフィールを取得しますが、それはそれほど速くはありません。前に見た奇妙な結果は、同一コード折りたたみなどによるものかもしれません。

---

編集3：

は以下のベンのクラスタ化インデックスのソリューションをしようと、それはより速く3.6Xについてです。私はこれが私がこのクエリでやっている最善の策だと思う。 SQLiteのCPU性能は、ノートパソコンの約700 MB/sです。 JITコンパイラをバーチャルマシンなどで使用するように書き直すのではなく、もっとうまくいくつもりはありません。特に、私の最初のプロフィールで見た奇妙な呼び出しは実際には起こっていないと思います。 gccは、最適化などの理由で誤ったデバッグ情報を書いているに違いありません。

CPUのパフォーマンスが改善されても、その処理能力は私のストレージが現在のコールドリードでできる以上のものであり、Pi（SDカードのUSB 2.0バスが限られています） 。

$ time ./bench 
sqlite3 version: 3.10.1 
trial 0: realtime 0.172 sec cputime 0.172 sec 
trial 1: realtime 0.172 sec cputime 0.172 sec 
trial 2: realtime 0.175 sec cputime 0.175 sec 
trial 3: realtime 0.173 sec cputime 0.173 sec 
trial 4: realtime 0.182 sec cputime 0.182 sec 
trial 5: realtime 0.187 sec cputime 0.187 sec 
trial 6: realtime 0.173 sec cputime 0.173 sec 
trial 7: realtime 0.185 sec cputime 0.185 sec 
trial 8: realtime 0.190 sec cputime 0.190 sec 
trial 9: realtime 0.192 sec cputime 0.192 sec 
trial 10: realtime 0.191 sec cputime 0.191 sec 
trial 11: realtime 0.188 sec cputime 0.188 sec 
trial 12: realtime 0.186 sec cputime 0.186 sec 
trial 13: realtime 0.179 sec cputime 0.179 sec 
trial 14: realtime 0.179 sec cputime 0.179 sec 
trial 15: realtime 0.188 sec cputime 0.188 sec 
trial 16: realtime 0.178 sec cputime 0.178 sec 
trial 17: realtime 0.175 sec cputime 0.175 sec 
trial 18: realtime 0.182 sec cputime 0.182 sec 
trial 19: realtime 0.178 sec cputime 0.178 sec 
trial 20: realtime 0.189 sec cputime 0.189 sec 
trial 21: realtime 0.191 sec cputime 0.191 sec 
trial 22: realtime 0.179 sec cputime 0.179 sec 
trial 23: realtime 0.185 sec cputime 0.185 sec 
trial 24: realtime 0.190 sec cputime 0.190 sec 
trial 25: realtime 0.189 sec cputime 0.189 sec 
trial 26: realtime 0.182 sec cputime 0.182 sec 
trial 27: realtime 0.176 sec cputime 0.176 sec 
trial 28: realtime 0.173 sec cputime 0.173 sec 
trial 29: realtime 0.181 sec cputime 0.181 sec 
PROFILE: interrupts/evictions/bytes = 547/178/24592 

real 0m5.651s 
user 0m5.292s 
sys  0m0.356s 

一部の非正規化されたデータを保存する必要があります。幸いにも、私はアプリケーションのRAMにそれを保持することができると思っています。それはあまりにも大きくならず、スタートアップは驚くほど高速である必要はなく、1つのプロセスだけがデータベースに書き込みます。

Answer 1

クラスタ化されたインデックスが必要です。または、サポートしていないSQLiteのバージョンを使用している場合は、インデックスをカバーしてください。

sqliteは3.8.2と3.8.2のSQLiteで

使用この上記以上：

create table recording (
    camera_id integer references camera (id) not null, 

    sample_file_bytes integer not null check (sample_file_bytes > 0), 

    -- The starting time of the recording, in 90 kHz units since 
    -- 1970-01-01 00:00:00 UTC. 
    start_time_90k integer not null check (start_time_90k >= 0), 

    -- The duration of the recording, in 90 kHz units. 
    duration_90k integer not null 
     check (duration_90k >= 0 and duration_90k < 5*60*90000), 

    video_samples integer not null check (video_samples > 0), 
    video_sync_samples integer not null check (video_samples > 0), 
    video_sample_entry_id integer references video_sample_entry (id), 

    --- here is the magic 
    primary key (camera_id, start_time_90k) 
) WITHOUT ROWID; 

以前のバージョンあなたがこれを使用することができたSQLiteの以前のバージョンでは

カバーインデックスを作成することのようなもの。これは、SQLiteのは、行ごとに別のページをフェッチ避け、インデックスからデータ値を引きできるようにする必要があります：

create index recording_camera_start on recording (
    camera_id, start_time_90k, 
    sample_file_bytes, duration_90k, video_samples, video_sync_samples, video_sample_entry_id 
); 

ディスカッション

コストがIOである可能性が高い（関係なく、そのあなたはそれを言いましたそうではありませんでした）IOがCPUを必要とすることを想起させるために、データはバスとの間でコピーされなければなりません。

クラスタ化された索引を使用しない場合、行はROWIDとともに挿入され、合理的な順序ではありません。これは、要求する26バイトの行ごとに、システムがSDカードから4KBのページをフェッチする必要があることを意味します。これはオーバーヘッドが大きくなります。

カメラの数が8個の場合、idにクラスタ化された単純なインデックスが挿入された順番でディスクに表示されるようにするには、取得したページに次の10-20行必要とされる。

カメラと時間の両方でクラスタード・インデックスを使用すると、取り出した各ページに100以上の行が含まれるようにする必要があります。