Czy to zapytanie SQLite może zostać wykonane znacznie szybciej?

Question

Mam bazę danych reprezentującą metadane NVR kamery bezpieczeństwa. Dla każdego jednominutowego fragmentu filmu jest 26-bajtowy wiersz recording. (Jeśli jesteś ciekawy, dokument projektowy jest w trakcie realizacji here.) Moje ograniczenia projektowe to 8 kamer, 1 rok (~ 4 miliony wierszy, pół miliona na kamerę). Udało mi się sfałszować niektóre dane, aby przetestować wydajność. To zapytanie jest wolniejszy niż się spodziewałem:

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; 

To tylko skanując wszystkie dane dotyczą aparatu, używając indeksu dla odfiltrowanie innych aparatów i kolejnością. Indeks wygląda następująco:

create index recording_camera_start on recording (camera_id, start_time_90k); 

explain query plan wygląda zgodnie z oczekiwaniami:

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

Wiersze są dość małe.

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

... 

Chciałbym coś takiego (może tylko miesiąc na raz, a nie na cały rok) należy uruchamiać za każdym razem dana strona jest trafiony, więc ma to być dość szybko. Ale na moim laptopie zajmuje to większość sekundy, a na Raspberry Pi 2, które chciałbym wspierać, jest zbyt powolny. Czasy (w sekundach) poniżej; to CPU-bound (użytkownik + sys czas ~ = w czasie rzeczywistym):

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

będę prawdopodobnie kończy się robi jakiś nieznormalizowana danych, ale najpierw chciałbym zobaczyć, czy mogę dostać tej prostej kwerendy wykonywać jak najlepiej, jak to możliwe. Mój benchmark jest całkiem prosty; przygotowuje sprawozdanie z góry, a następnie pętli nad tym:

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

zrobiłem profil procesora z gperftools. Obrazek:

$ 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 

To wygląda dość dziwnie, aby dać mi nadzieję, że może być ulepszona. Może robię coś głupiego. Jestem szczególnie sceptyczny operacji sqlite3_randomness i sqlite3_strnicmp:

• docs powiedzieć sqlite3_randomness służy do wstawiania rowids w pewnych okolicznościach, ale ja po prostu robi kwerendę wybierającą. Dlaczego miałby to teraz używać? Od skimmingu kodu źródłowego sqlite3, widzę, że jest on używany w select dla sqlite3ColumnsFromExprList, ale wydaje się, że to coś, co zdarzyłoby się podczas przygotowywania oświadczenia. Robię to raz, nie w części, która jest porównywana.
• strnicmp służy do porównywania wielkości liter niewrażliwych na wielkość liter. Ale każde pole w tej tabeli jest liczbą całkowitą. Dlaczego miałby korzystać z tej funkcji? Co to jest porównanie?
• i generalnie nie wiem, dlaczego sqlite3_reset byłby drogi lub dlaczego zostałby wywołany z 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) 
); 

Mam asfaltowa moje dane testowe + program testowy; możesz go pobrać here.

---

Edit 1:

Ahh, przeglądając kod SQLite, widzę pojęcia:

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

Wygląda sqlite3_stepsqlite3_reset rozmowy na temat zmian schematu. (FAQ entry) Nie wiem dlaczego nie byłoby zmiana schematu ponieważ moja wypowiedź została przygotowana chociaż ...

---

Edit 2:

Pobrałem SQLite 3.10.1 „amalgation "i skompilowane przeciwko niemu z symbolami debugowania. Dostaję teraz całkiem inny profil, który nie wygląda tak dziwnie, ale nie jest szybszy. Może dziwne wyniki, które widziałem wcześniej, wynikały z identycznego składania kodu lub czegoś podobnego.

---

Edit 3:

Próba rozwiązania indeksu klastrowego Bena poniżej, to jest o 3.6x szybciej. Myślę, że to najlepsze, co zrobię z tym zapytaniem. Wydajność procesora SQLite wynosi około 700 MB/s na moim laptopie. Nie licząc przepisywania go na kompilator JIT dla jego maszyny wirtualnej lub czegoś takiego, nie zamierzam robić nic lepszego. W szczególności wydaje mi się, że dziwne połączenia, które widziałem na moim pierwszym profilu, nie miały miejsca; gcc musi napisać wprowadzające w błąd informacje debugowania z powodu optymalizacji lub czegoś podobnego.

Nawet jeśli wydajność procesora zostałaby poprawiona, ta przepustowość jest większa niż moja pamięć masowa może zrobić przy odczycie zimna teraz i myślę, że to samo dotyczy Pi (które ma ograniczoną magistralę USB 2.0 dla karty 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 

Być może będę musiał zachować niektóre zdenormalizowane dane. Na szczęście myślę, że mogę po prostu zachować go w pamięci RAM aplikacji, ponieważ nie będzie zbyt duży, start nie musi być niesamowicie szybki i tylko jeden proces kiedykolwiek zapisuje do bazy danych.

Answer 1

Potrzebujesz indeksu klastrowego lub jeśli używasz wersji SQLite, która nie obsługuje jednego, indeksu pokrywającego.

Sqlite 3.8.2 i powyżej

wykorzystuje to w SQLite 3.8.2 i powyżej:

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; 

wcześniejszych wersjach

We wcześniejszych wersjach SQLite można użyć tego coś w rodzaju stworzenia indeksu pokrywającego.Powinno to pozwolić SQLite ciągnąć wartości danych z indeksu, unikając pobierania osobną stronę dla każdego wiersza:

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

Dyskusyjnego

Koszt jest prawdopodobnie IO (niezależnie od tego, że to powiedziałeś nie było), ponieważ przypominają, że IO wymaga procesora, ponieważ dane muszą być kopiowane do iz magistrali.

Bez indeksu klastrowego wiersze są wstawiane z rowidami i mogą nie być w rozsądnej kolejności. Oznacza to, że dla każdego 26-bajtowego rzędu, którego zażądasz, system może pobrać stronę 4KB z karty SD - co jest dużo narzutem.

Przy limicie 8 kamer, prosty indeks klastrowy na id, aby upewnić się, że pojawią się one na dysku we wprowadzonej kolejności, zapewniłby około 10-krotny wzrost prędkości, zapewniając, że pobrana strona zawiera kolejne 10-20 wierszy, które będą być wymaganym.

Indeks klastrowy w kamerze i czasie powinien zapewniać, że każda strona zawiera 100 lub więcej wierszy.