Questa query SQLite può essere eseguita molto più velocemente?

Question

Ho un database che rappresenta i metadati di un NVR della videocamera di sicurezza. C'è una riga da 26 byte recording per ogni segmento di video di 1 minuto. (Se sei curioso, è in corso un documento di progettazione here.) I miei limiti di progettazione sono 8 telecamere, 1 anno (~ 4 milioni di righe, mezzo milione per telecamera). Ho falsificato alcuni dati per testare le prestazioni. Questa query è più lento del previsto:

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; 

questo è solo la scansione di tutti i dati di una telecamera, utilizzando un indice per filtrare le altre telecamere e l'ordinamento. Indice assomiglia a questo:

create index recording_camera_start on recording (camera_id, start_time_90k); 

explain query plan appare come previsto:

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

Le righe sono piuttosto piccole.

$ 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% 

... 

mi piacerebbe qualcosa di simile (forse solo un mese alla volta, piuttosto che un intero anno) per essere eseguito ogni volta che una particolare pagina web è colpito, quindi voglio che sia abbastanza veloce. Ma sul mio portatile, ci vuole quasi un secondo, e sul Raspberry Pi 2 mi piacerebbe supportare, è troppo lento. Times (in secondi) sotto; è CPU-bound (utente + sys tempo ~ = tempo reale):

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") 

io probabilmente finire per fare una sorta di dati denormalizzati, ma prima mi piacerebbe vedere se riesco a ottenere questo semplice query per eseguire al meglio. Il mio punto di riferimento è piuttosto semplice; prepara la dichiarazione in anticipo e poi loop su questo:

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)); 
    } 
} 

ho fatto un profilo CPU con gperftools. Immagine:

$ 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 

Questo sembra abbastanza strano per darmi spero che possa essere migliorato. Forse sto facendo qualcosa di stupido. Sono particolarmente scettici delle operazioni sqlite3_randomness e sqlite3_strnicmp:

• documenti dicono sqlite3_randomness viene utilizzato per l'inserimento di ROWIDs in alcune circostanze, ma sto solo facendo una query di selezione. Perché dovrebbe usarlo ora? Dal codice sorgente di sklite sqlite3, vedo che viene utilizzato in select per sqlite3ColumnsFromExprList ma sembra essere qualcosa che potrebbe accadere quando si prepara la dichiarazione. Lo sto facendo una volta, non nella parte di riferimento.
• strnicmp è per confronto stringhe senza distinzione tra maiuscole e minuscole. Ma ogni campo in questa tabella è un numero intero. Perché dovrebbe usare questa funzione? Che cosa sta comparando?
• e in generale, non so perché sqlite3_reset sarebbe costoso o perché sarebbe chiamato da sqlite3_step.

schema:

-- 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) 
); 

ho asfaltata fino miei dati + programma di test di prova; lo puoi scaricare here.

---

Edit 1:

Ahh, guardando attraverso il codice SQLite, vedo un indizio:

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); 
    } 

Sembra sqlite3_step chiamate sqlite3_reset sulla modifica dello schema. (FAQ entry) Non so il motivo per cui ci sarebbe una modifica dello schema poiché la mia dichiarazione è stata preparata anche se ...

---

Edit 2:

Ho scaricato lo SQLite 3.10.1 "Amalgation "e compilato contro di esso con i simboli di debugging. Ho un profilo abbastanza diverso ora che non sembra strano, ma non è più veloce. Forse i risultati bizzarri che ho visto prima erano dovuti a Identical Code Folding o qualcosa del genere.

---

Edit 3:

Cercando soluzione indice cluster di Ben al di sotto, si tratta di 3.6X più veloce. Penso che questo sia il meglio che ho intenzione di fare con questa query. Le prestazioni della CPU di SQLite sono circa ~ 700 MB/s sul mio portatile. A parte riscriverlo per usare un compilatore JIT per la sua macchina virtuale o qualcosa del genere, non ho intenzione di fare di meglio. In particolare, penso che le bizzarre chiamate che ho visto sul mio primo profilo non stessero realmente accadendo; gcc deve aver scritto informazioni di debug ingannevoli a causa di ottimizzazioni o qualcosa del genere.

Anche se le prestazioni della CPU risultassero migliorate, il throughput è maggiore di quanto possa fare la mia memoria su cold read ora, e penso che lo stesso sia vero sul Pi (che ha un bus USB 2.0 limitato per la scheda SD) .

$ 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 

Potrei dover conservare alcuni dati denormalizzati. Fortunatamente, sto pensando di poterlo tenere nella RAM della mia applicazione dato che non sarà troppo grande, l'avvio non deve essere incredibilmente veloce e solo l'unico processo scrive nel database.

Answer 1

È necessario un indice cluster o se si utilizza una versione di SQLite che non ne supporta uno, un indice di copertura.

Sqlite 3.8.2 e al di sopra

Utilizzare questo in SQLite 3.8.2 e superiori:

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; 

versioni precedenti

Nelle versioni precedenti di SQLite è possibile utilizzare questo sorta di cosa per creare un indice di copertura.Questo dovrebbe permettere SQLite per tirare i valori dei dati dall'indice, evitando scarica una pagina separata per ogni riga:

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 
); 

Discussione

Il costo è probabile che sia IO (indipendentemente che hai detto non lo era) perché ricorda che l'I/O richiede CPU in quanto i dati devono essere copiati sul e dal bus.

Senza un indice cluster, le righe vengono inserite con un rowid e potrebbero non essere in alcun ordine ragionevole. Ciò significa che per ogni riga di 26 byte richiesta, il sistema potrebbe dover recuperare una pagina 4KB dalla scheda SD, il che è un sovraccarico.

Con un limite di 8 telecamere, un semplice indice cluster id per assicurare appaiono sul disco in modo inserita probabilmente dare circa 10x aumento della velocità garantendo che la pagina recuperata contiene prossimi 10-20 righe che stanno essere richiesto

Un indice cluster su telecamera e ora dovrebbe garantire che ogni pagina recuperata contenga 100 o più righe.