Optymalizacja zapytań MySQL dla koniunkcji wielu danych

Nie raz, nie dwa mieliśmy sytuację, która wymagała od nas koniunkcji warunków większej ilości danych lub dane te były tekstowe, ale niedługie. Niby nic, klucze załatwiają sprawę, ale sięgając do kodu gry bukmacherskiej, musiałem ją nieco zoptymalizować pod względem częstego wyciągania danych. Baza rozrosła się dość szybko, dlatego niezbędna była lekka modyfikacja jej struktury.

Moim zadaniem było bardzo częste wyciągnięcie ID meczu, który musiał na raz (AND) być zgodny z żądaną datą, nazwą drużyny pierwszej oraz drugiej. Informacji do warunków dostarczał system. Oprócz daty, są to dane tekstowe, więc połączyłem je ze sobą CONCAT i stworzyłem z nich sumę md5. Indeks, po którym baza szukała, był już krótszy od warunków, bo zawierał zawsze 32 znaki. Pierwszym warunkiem koniunkcji zawsze była suma md5 wymienionych wcześniej pól rekordu, nazwałem to suma kontrolna rekordu, potem faktyczna wartość pól, aby w razie zdublowania sumy kontrolnej (czego się nie spodziewamy, bo zakres wariacji jest ogromny, ale dla idei) wybrać prawidłowy rekord. Do tej pory wystarczało…

Gdy baza rozrasta się, problemem staje się wyszukiwanie. O ile suma kontrolna to już krok w stronę optymalizacji, dla >100k rekordów, baza danych potrzebowała co najmniej 0.05 sekundy na zwrócenie wyniku. Postanowiłem dodać odcisk palca sumy kontrolnej. Najlepszym rozwiązaniem okazało się dodanie jednego bajtu, który zrobił magię w bazie danych. Jedno pole TINYINT – 8 bitów, zakres 0-255 bez znaku. Założenia odcisku palca:

  • jest wartością liczbową oraz zajmuje tylko jeden bajt, aby oszczędzić miejsca w rekordach oraz indeksach bazy danych,
  • nie musi być uniwersalny (unikalny), a jedynie grupować odciski palców w mniejsze, a liczniejsze zbiory.

Rozwiązanie, które zastosowałem przy generowanu odcisku palca sumy kontrolnej, również nie jest skomplikowane:

  1. Odcisk palca to suma kolejnych znaków sumy kontrolnej rekordu, gdzie 0 – 9 zachowują swoje wartości, a litery [a-f] przyjmują kolejno [10-15], dokładnie jak w przeliczaniu pojedynczych wyrazów systemu liczbowego o podstawie 16 (HEX) na dziesiętny.
  2. Skoro jest to suma, to wartość minimalna jest dla samych zer, zatem MIN = 0.
  3. Wartość maksymalną można stworzyć podając same maksymalne wartości F, zatem MAX = 480.
  4. 480 mieści się na 9 bitach (min. 2 bajty, zakres 0-65535 bez znaku, tracimy 65055 wartości), dzieląc liczbę przez 2 tracimy unikalność odcisku dwukrotnie, ale zmieścimy się na ośmiu bitach, czyli jednym bajcie – możemy użyć typu TINYINT (zakres 0-255 bez znaku, nasza to 0-240), zatem tracimy tylko 15 niewykorzystanych wartości.

Przeprowadzamy testy naszego rozwiązania.

Stwórzmy przykładową tabelę danych test_md5_index, która będzie przechowywała wartości tekstowe w polach data_content, data_content2, data_content3. Tabela może zawierać pole dodatkowe, ale te trzy będziemy wykorzystywać w naszym wyszukiwaniu. Ważnym jest to, że warunkiem jest koniunkcja (AND), dlatego możemy stworzyć sumę (analogicznie do sumy logicznej) md5 jako odcisk palca tych pól, który zapiszemy w data_sum varchar(32). Dodatkowo stworzymy odcisk palca odcisku palca – jednobajtowe pole data_sum_index TINYINT.

Od razu zakładamy klucz podstawowy na data_id oraz klucz dla zapytania, który będzie go wykorzystywał, czyli szukanie wspólnie po data_sum_index oraz data_sum.

CREATE TABLE test_md5_index (
  data_id int(11) unsigned NOT NULL AUTO_INCREMENT,
  data_sum_index tinyint(1) unsigned NOT NULL,
  data_sum varchar(32) NOT NULL,
  data_contents text NOT NULL,
  data_contents2 text NOT NULL,
  data_contents3 text NOT NULL,
  PRIMARY KEY (data_id),
  KEY data_index (data_sum_index, data_sum)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=1;

Pora stworzyć funkcję, która przeliczy nam nowy, krótszy odcisk palca na podstawie poprzedniego:

CREATE FUNCTION TestIndexChecksum(sSum VARCHAR(32)) RETURNS TINYINT
BEGIN

  DECLARE sSumPart VARCHAR(1);
  DECLARE iSumPart TINYINT;
  DECLARE iSum SMALLINT DEFAULT 0;
  DECLARE i INT;

  IF (SELECT sSum NOT REGEXP '^([a-z0-9]){32}$') THEN RETURN 0; END IF;

  SET i = 1;

  WHILE i <= LENGTH(sSum) DO
    SET sSumPart = SUBSTR(sSum, i, 1);
    SET iSumPart = (SELECT (CASE WHEN sSumPart = 'a' THEN 10 WHEN sSumPart = 'b' THEN 11 WHEN sSumPart = 'c' THEN 12 WHEN sSumPart = 'd' THEN 13 WHEN sSumPart = 'e' THEN 14 WHEN sSumPart = 'f' THEN 15 ELSE 0 END));

    IF iSumPart = 0 THEN
      SET iSumPart = sSumPart;
    END IF;

    SET iSum = iSum + iSumPart;
    SET i = i + 1;
  END WHILE;

  RETURN iSum / 2;
END;

Aby przeprowadzać testy, stwórzmy sobie procedurę, która wstawi nam N losowo, jakkolwiek wypełnionych rekordów do bazy danych:

CREATE PROCEDURE TestIndexesPrepareTest(IN i INT)
BEGIN
  TRUNCATE TABLE test_md5_index;

  WHILE i > 0 DO

    INSERT INTO test_md5_index SET
      data_contents  = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
      data_contents2 = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
      data_contents3 = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
      data_sum = CONCAT(data_contents, data_contents2, data_contents3),
      data_sum_index = TestIndexChecksum(data_sum);

    SET i = i - 1;
  END WHILE;
END;

Po wykonaniu CALL TestIndexesPrepareTest(100000) mamy przygotowane małe środowisko testowe.

Przygotujmy kilka zapytań do bazy danych, wybieramy losowy rekord, na którym będziemy testowali wyniki. Wykonujemy zapytanie z ręcznie wpisaną wartością warunku wybranego rekordu, sprawdźmy, jak szybko zostanie odnaleziony:

SELECT * FROM test_md5_index WHERE data_sum = "24045771412594250684228176888212";

Average: ~0.0506 sec

SELECT * FROM test_md5_index WHERE data_sum_index = 68 AND data_sum = "24045771412594250684228176888212";

Average: ~0.0004 sec (UWAGA! Specjalnie w warunku nie użyłem zwróconej warości funkcji, tylko dałem ją na sztywno, ręcznie wpisaną – funkcja by była wykonywana dla każdego porównania rekordu z osobna!).

Nasze zapytanie działa znacznie szybciej (~120 razy dla 100k rekordów) kosztem niewielkiej pamięci – po 1 bajcie do rekordu oraz po 1 bajcie do jego indeksu.

Zapewne istnieją szybkie silniki indeksowania danych, natomiast, gdy jesteśmy skazani np. na InnoDB z założeń technicznych – nie oznacza, że się nie da.

Mam nadzieję, że komuś się przyda.

 

10 thoughts on “Optymalizacja zapytań MySQL dla koniunkcji wielu danych

  1. Ciekawe zagadnienie ten „odcisk palca sumy kontrolnej”.

    Temat optymalizacji zapytań SQL jest niestety rzadko poruszany.

  2. Widzę że ostro ostaniego czasu męczysz te MySQL 🙂

    Bardzo fajny tekst i przyjemnie się czyta, czekam na kolejne 🙂

    Ps. w kolorowaniu kodu wstawia encje zamiast

  3. Nie ma czegoś takiego jest warunkowa koniunkcja. To po pierwsze. Po drugie, w liście numerowanej, punkt 1, napisałeś, że litery [a-f] przyjmują wartości [10-15] jak w systemie liczbowym o podstawie 16 – czy w systemie liczbowym o podstawie 16 znajdziesz cyfrę „12”? Przeredaguj ten punkt, bo zupełnie nie wiadomo na pierwszy rzut oka o co chodzi.

    // dzięki bardzo, poprawiłem, uchybienia.

    No ale chwila, to chyba po to mamy indeksy na b-drzewach i innych różnorakich strukturach, by wyszukiwanie po wybranych polach było zdecydowanie szybsze niż na tych nieindeksowanych.

    A jeśli potrzebujesz generować dane statystyczne bądź zbiorcze (jak i przypadku zadań analitycznych na danych), zaleca się wykorzystania mechanizmów chociażby hurtowni danych bądź kostek OLAP.

  4. Jak tak Ci zależy na zajmowanym miejscu to dlaczego data_sum jest varchar(32)? Powinien być zapisywany na 16 bajtach.
    Po drugie to wydaje mi się, że zamiast wbrew pozorom skomplikowanej sumy wystarczy wziąć pierwszy bajt sumy kontrolnej. Rozkład powinien nie być gorszy od sumy w postaci szesnastkowej.
    Idąc dalej w oszczędzanie miejsca można by zrezygnować z pola data_sum_index i nałożyć indeks na pierwszy bajt data_sum. Pewnie MySql nie wspiera takiej operacji, więc można podzielić sumę na dwa pola: 1 bajt i pozostałe 15.
    Tak w ogóle to nie rozumiem tego artykułu. Tworzysz index (data_sum_index, data_sum), który zajmuje więcej niż sam indeks na data_sum. Ponadto zapytanie z data_sum_index i data_sum wykonuje się dłużej z samym data_sum.

  5. „… funkcja by była wykonywana dla każdego porównania rekordu z osobna!” co prawda ja przychodzę z podwórka PostgreSQL, ale wydaje mi się, że „DETERMINISTIC” powinno załatwić sprawę (http://awurl.com/TtAkQQdIy). Po drugie zrobiłeś pierwszy krok do partycjonowania danych, ale według mnie całkowicie niepotrzebny (i niekompletny, ale to nie temat tego posta). Otóż podstawową zasadą tworzenia warunków w SQL jest podanie najpierw warunków najbardziej selektywnych.
    Ile Ci się te mecze razy powtarzają? Bo tutaj każdy odcisk masz 100k / 240, czyli ponad 400 razy (oczywiście podałeś, że danych masz więcej niż 100k, chcę tylko pokazać skalę). Niby to nie dużo, ale i tak pewnie ze 400 razy więcej niż masz tych samych sum MD5 😉
    Zamiast czarować z jakimiś concatami, md5 i odciskami wziąłbyś zrobił porządny profiling kodu i zapytań – jestem przekonany, że jeden porządny indeks załatwiłby sprawę, zwłaszcza że 100k rekordów to naprawdę nie są jakieś ogromne wielkości, nawet dla InnoDB.

    Pozdrawiam

  6. @djstrong, na 16 bajtach się niestety nie zmieści. Jeden char – jeden bajt.

    Jeżeli weźmiesz pierwszy bajt sumy kontrolnej, zachowasz jedną wartość (literę), a jakbyś chciał kiedyś przeliczyć wartości na liczbę: 0-15, zatem niewykorzystanych będzie 240 wartości, jakie może faktycznie przechować ten jeden bajt. Jak widać – można pogrupować czulej.

    Klucz, owszem, zajmuje jeden bajt więcej dla każdego rekordu, ale zapytanie z data_sum_index i data_sum wykonuje się ~120 razy szybciej, niż z samym data_sum.

    @Michał Bachowski, nie wiem, jak jest w PostgreSQL, u mnie testy wykazały, że lepiej wykonać zapytanie z podaną wartością, aniżeliby z obliczaną przez funkcję. Zapytanie z funkcją wykonuje się znacznie dłużej, przez co wnioskuję, że sumy są obliczane na bieżąco.

    Profiling aplikacji, o którym wspominałeś, w xDebug nic nie wykazał. Aplikacja czekała na bazę danych, czyli zabieg był konieczny. Jakikolwiek, notabene nie mówię, że ten jest najlepszy, bo Tiraeth wspomniał o składowaniu poindeksowanych danych, ale znacznie optymalniejszy, jak zastosowany wcześniej. Na przeróbkę miałem dość mało czasu, żeby drastycznie przebudowywać struktury.

    Tak, dobrze mówisz: warunki układa się w taki sposób, aby kolejne miały mniej rekordów do przeszukiwania – to jest prawda naga. Dlatego data_sum_index jest jako pierwsza – grupuje wyniki w mniejsze znacznie zbiory eliminując od razu niepotrzebne.

    Odcisk palca rekordu został stworzony tylko po to, aby skrócić stringi z czterech pól – łatwiej porównać 32 znaki, niż średnio 100.

    BTW: OT: fajnie, że blogosfera nadal żyje. Myślałem, że Facebook doszczętnie wszystko zabił swoimi przeklejkami.

  7. WHILE i > 0 DO

    Parser wlejanego kodu jest czulszy niż myślisz 😉

    EDIT: Chodziło o nawias kwadratowy < – zamienia go na encję &.gt;

  8. @Athlan

    Nie wiem czemu md5 traktujesz jako 32 znaki… Po pierwsze jest to 16B, możesz sobie sprawdzić gdziekolwiek, np. na wiki.

    >@djstrong, na 16 bajtach się niestety nie zmieści. Jeden char – jeden bajt.

    Dwa znaki szesnatkowe odpowidają jednemu bajtu.

    >Jeżeli weźmiesz pierwszy bajt sumy kontrolnej, zachowasz jedną wartość (literę), a jakbyś chciał kiedyś przeliczyć wartości na liczbę: 0-15, zatem niewykorzystanych będzie 240 wartości, jakie może faktycznie przechować ten jeden bajt. Jak widać – można pogrupować czulej.

    Chodziło mi o bajt, a nie literę, więc nic nie tracę.

    >Klucz, owszem, zajmuje jeden bajt więcej dla każdego rekordu, ale zapytanie z data_sum_index i data_sum wykonuje się ~120 razy szybciej, niż z samym data_sum.

    WG mnie to nie prawda, usuń ten indeks i załóż na sam data_sum – będzie przynajmniej tak samo szybko.

  9. @Athlan: MD5 to 32 hexy (znaki 0..9 a..f) czyli 16 bajtów (2 hexy to jeden bajt). Robiąc więc prostą konwersję uzyskujesz liczbę 16 bajtową – rozbij na dwie.

    To tak:
    1) generujesz md5 – dzielisz go na pół (16 znaków i znaków – nazwijmy je high i low)
    2) high i low zamieniasz na unsigned bigint (ma on 8 bajtów).
    3) zakładasz index B-Tree na high i na low

  10. Rozwiązanie ciekawe, ale…

    Zabawne, piszesz o optymalizacji a dla md5 masz:
    data_sum varchar(32)

    Dlaczego varchar, jeśli zawsze spodziewasz się 32?

    Jak już ktoś wspomniał szybciej przejrzałbym bazę i aplikację pod kątem refaktoryzacji niż dorzucał do wyszukiwania 32 znakowe pole znakowe.

    Tu pewnie nie miałeś możliwości, ale warto też przy zabawach na txt skorzystać ze Sphinxa lub innego cuda do pełnotekstowego szukania, jak już musisz mieć pełno porównań tekstowych w warunkach.

Comments are closed.