Jak bychom to řešili v ...?

• Relačních databázích
• Key-Value databázích
• Dokumentových databázích

Relační databáze - LIKE

        SELECT *
        FROM movies
            WHERE title LIKE '%sta wrs%';
            

• ❌ nefunguje (překlep)
• ❌ žádná relevance
• ❌ pomalé na velkých datech

Relační databáze - FULLTEXT

        SELECT *
        FROM movies
            WHERE MATCH(title) AGAINST ('sta wrs');
                    

• ✔️ lepší než LIKE
• ⚠️ základní relevance
• ⚠️ omezené možnosti ladění
• ⚠️ slabší práce s překlepy
• ⚠️ není optimalizovaný pro velký search load
• ❌️ není standardizovaný
• 🔥 různá implementace & dotazování
• ⚠️ potřeba extensions / pluginů
• ⚠️ většinou hard-core konfigurace
• ❌ některé RDBMS ho vůbec nepodporují

Key-Value databáze - Redis (8+)

        FT.CREATE movies_idx ON HASH PREFIX 1 "movie:"
        SCHEMA
            title TEXT
            description TEXT
	

• ✔️ fulltext search dostupný přímo v Redis
• ⚠️ nutnost explicitního indexu
• ⚠️ jiný přístup než běžný key-value model

Key-Value databáze - Redis

        FT.SEARCH movies_idx "sta wrs"
	

• ✔️ základní fulltext funguje
• ⚠️ omezené možnosti relevance
• ⚠️ méně flexibilní než specializovaný nástroj
• ⚠️ není primárně určený pro komplexní search

Dokumentová databáze - MongoDB

        db.movies.createIndex({
          title: "text",
          description: "text"
        });

        db.movies.find({
          $text: { $search: "sta wrs" }
        });
    

• ✔️ základní fulltext existuje
• ✔️ přirozená práce s dokumenty / JSON
• ⚠️ nutnost text indexu
• ⚠️ omezenější ladění relevance
• ⚠️ méně specializované než search engine

Dok. db - MongoDB Atlas Search

        db.movies.aggregate([
          {
            $search: {
              text: {
                query: "sta wrs",
                path: ["title", "description"]
              }
            }
          }
        ]);
    

• ✔️ pokročilejší fulltext než klasický $text
• ✔️ search index mimo běžný DB index
• ⚠️ blízké specializovanému search řešení
• ⚠️ vyšší komplexita než obyčejný find()

Distribuovaný systém

• systém běžící na více uzlech (nodes)
• uzly spolu komunikují a sdílí práci
• navenek se chová jako jeden celek
• cílem je škálování a odolnost

Elasticsearch - distribuovaný systém

• běží jako skupina spolupracujících node
• navenek se tváří jako jeden celek = cluster
• data i dotazy se mezi nody rozdělují
• díky tomu umí škálovat výkon i odolnost

Co je Elasticsearch cluster?

• cluster = skupina (např. Elasticsearch) node
• sdílí data, stav a zodpovědnost za vyhledávání
• uživatel obvykle komunikuje s clusterem jako s jednou službou
• uvnitř se ale práce rozděluje mezi více strojů

Jaké role mají node?

• master-eligible node – může se stát masterem (účastní se voleb)
• elected master node – aktuálně zvolený master, řídí cluster (metadata, shard allocation)
• data node – drží data a obsluhuje dotazy
• ingest node – zpracovává data při zápisu (pipelines, transformace)
• v demo prostředích může jeden node dělat více rolí najednou
• ve větším nasazení role často oddělujeme (master / data / ingest)

Jak se ukládají data?

• index se dělí na primární shardy
• každý shard může mít svou replicu
• shardy rozkládají data i zátěž
• repliky pomáhají s dostupností a často i čtením
• primární shard a jeho replica nikdy neběží na stejném node

Minimální konfigurace indexu

        PUT /program
        {
          "settings": {
            "number_of_shards": 3,
            "number_of_replicas": 1
          }
        }
    

• number_of_shards: 3 → index se rozdělí na 3 primární shardy
• number_of_replicas: 1 → každý primární shard bude mít 1 repliku
• celkem tedy vznikne 6 shardů
• celkem shardů = primární shardy × (1 + počet replik)

Ukázková demo architektura

• 6× Elasticsearch node
• 3× master + 3× data node
• Nginx jako SSL reverse proxy a load balancer
• Kibana pro vizualizaci a práci s clusterem
• Filebeat pro sběr a posílání dat
• Logstash pro zpracování a transformaci dat

Jak to do sebe zapadá?

• Filebeat sbírá data a posílá je do Logstash
• Logstash data zpracuje a předá do Elasticsearch
• Elasticsearch je ukládá do indexů a shardů
• Kibana nad clusterem dělá správu, dotazy a vizualizaci
• Nginx sjednocuje přístup zvenku a rozděluje požadavky mezi node

Role Nginx v našem demu

• ukončuje TLS/SSL
• funguje jako load balancer pro všechny ES node
• při chybě umí zkusit další upstream
• do hlavičky přidává, který node požadavek obsloužil
• má vlastní health endpoint pro kontrolu dostupnosti
• !! v našem demu se jedná o SPOF !!

Jak to Elasticsearch dělá?

• nevyhledává přímo v datech
• nejdřív si je připraví do indexu
• používá tzv. invertovaný index
• hledání pak probíhá nad tokeny, ne nad celým textem

Invertovaný index

    Star Wars        → star, wars
    War of Worlds    → war, worlds
    Star Trek        → star, trek

    ----------------------------

    star   → doc1, doc3
    wars   → doc1
    war    → doc2
    worlds → doc2
    trek   → doc3
    

Inverted Index (příklad)

Vstupní dokumenty

1. Kočka sedí na střeše domu.
2. Malá kočka seděla na střeše.
3. Kočky sedí na střechách domů.
4. Na střeše domu sedí černá kočka.
5. Kočka právě sedí na střeše starého domu.

Tokenizace

        1 → [kočka, sedí, na, střeše, domu]
        2 → [malá, kočka, seděla, na, střeše]
        3 → [kočky, sedí, na, střechách, domů]
        4 → [na, střeše, domu, sedí, černá, kočka]
        5 → [kočka, právě, sedí, na, střeše, starého, domu]
    

Normalizace (zjednodušeně)

        kočka / kočky → kočk
        sedí / seděla → sed
        střeše / střechách → střech
        domu / domů → dom
    

Inverted Index

        kočk   → [1, 2, 3, 4, 5]
        sed    → [1, 2, 3, 4, 5]
        střech → [1, 2, 3, 4, 5]
        dom    → [1, 3, 4, 5]
        malá   → [2]
        černá  → [4]
        starý  → [5]
        právě  → [5]
    

Pomohou analyzery?

• analyzery upravují text → tokeny
• řeší jazyk (tvary slov, stemming…)
• pomáhají sjednotit data a dotaz

Typy analyzérů

• standard – základní tokenizace + lowercase
• simple – ponechává znaky + lowercase
• language analyzers – např. czech, english
• whitespace – dělí jen podle mezer
• custom analyzers – vlastní tokenizer + filtry

Jazykové analyzéry - Stop words

• slova, která ignorujeme při vyhledávání
• např. a, the, je, to
• pomáhají snížit „šum“ v datech

Pomůže Hunspell?

• slovníková kontrola nad tvary slov
• užitečné hlavně pro morfologii jazyka
• typicky pro skloňování, časování, odvozování tvarů
• ale str wrs stále není validní slovo

Pomohlo to?

• Hunspell zlepšuje práci se slovními tvary
• neřeší ale zkrácené nebo rozbité tokeny
• str wrs → stále nic

Pomůže n-gram / autocomplete?

• text se rozdělí na menší části
• neindexujeme jen celé slovo, ale i jeho fragmenty
• to pomáhá při našeptávání a neúplném vstupu
• star → st, sta, star…

Pomohlo to?

• str wrs už se může částečně potkat s indexem
• funguje dobře pro prefixy a části slov
• je skvělé pro autocomplete
• ale není to univerzální řešení relevance
• str wrs → s velkou pravděpodobností nic

Pomůže analyzer pipeline?

• pipeline kombinuje více kroků zpracování textu
• např. tokenizer + lowercase + stop words + stemming
• umožní si analyzaci textu přesně přizpůsobit
• ale pořád pracujeme jen s tím, co z textu dokážeme odvodit

Pomohlo to?

• pipeline zlepší konzistenci analyzace
• pomůže zkombinovat více technik najednou
• ale str wrs stále nemusí stačit na star wars
• samotná pipeline také problém nevyřešila

Signifikantní termy

• hledají statisticky neobvyklá slova
• porovnávají subset vs celý dataset
• počítají se při dotazu (query-time)
• využívají frekvenci výskytu (TF / DF)
• neukládají se jako data → jsou odvozené

Signifikantní termy – příklad I.

    Celý index: 1000 filmů
    Subset: 100 akčních filmů

    'exploze':
        → v celém indexu: 50×
        → v subsetu: 40×

        => nečekaně vysoký výskyt (80% dokumentů) → significant
    

Signifikantní termy – příklad II.

    Celý index: 1000 filmů

    'film':
        → v celém indexu: 900×
        → v subsetu: 10×

        => normální výskyt (~1% dokumentů) → non-significant
    

Collapse

Collapse - Příklad použití

    Dotaz: Chci znát pro každý rok film,
           který nejlépe odpovídá výrazu: 'terminator'
                

            Výsledky:

            * 1984 - Terminátor - 87 %
            * 1991 - Terminátor 2: Den zúčtování - 91 %
            * 2003 - Terminátor 3: Vzpoura strojů - 74 %
            * 2007 - Hra s časem - 20 %
            * 2009 - Terminator Salvation - 67 %
            * 2015 - Terminator Genesys - 66 %
            * 2019 - Terminátor: Temný osud - 67 %
                

Agregace

• seskupují data do bucketů
• nevrací primárně dokumenty, ale statistiku
• typicky: kolik filmů je v žánrech, letech, zemích…
• fungují jako analytická vrstva nad indexem

Agregace - Sub-buckets

• buckety můžeme zanořovat
• např. žánr → rok → země
• dostaneme strukturovaný pohled na data
• něco jako hierarchická analytika

Agregace - Příklad

        Dotaz: Chci znát počet filmů
               dle žánru a následně dle let v kterých vyšly.
                

        1000 filmů
            ├─ Akční: 500
            │  ├─ 1980s: 120
            │  ├─ 1990s: 180
            │  └─ 2000s: 200
            │
            ├─ Sci-fi: 300
            │  └─ ...
            └─ Komedie: 200
               └─ ...
    

More like this (MLT)

MLT - Jak to funguje?

MLT - Příklad použití