mufassall

Konspekt · Ma'lumot va saqlash

Matn bo'yicha qidiruv (full-text search)

14 daq · O'rta · mufassall.dtwin.uz/uz/l/full-text-search/

← Darsni ochish

Muammo

Marketpleys katalogni `LIKE '%so'z%'` bilan qidiradi. 4 million mahsulotda har bir qidiruv jadvalning har bir qatorini o'qiydi, shunga qaramay boshqa apostrof bilan, kirillda yoki o'zbekcha qo'shimcha bilan yozilgan mahsulotlarni topa olmaydi. Haqiqiy matn qidiruvini bosqichma-bosqich quramiz: tahlil qilingan tokenlar ustidagi teskari indeks, BM25 reytingi, bazaning o'zgarishlar log'iga ergashadigan indeks, scatter-gather bilan shard'lar va xatoga chidamli qidiruv.

Nimani o'rganasiz

  • Nega LIKE '%x%' indeksdan foydalana olmaydi va butun jadvalni o'qiydi
  • Tahlil (analyzer): kichik harf, kirilldan lotinga, o'zbekcha apostroflar va qo'shimchalar, indekslashda ham, so'rovda ham bitta analyzer
  • Postings ro'yxatli teskari indeks va BM25 reytingi aniq raqamlarda
  • Indeksni o'zgarishlar log'i orqali yangi saqlash, hujjat bo'yicha sharding, scatter-gather va xatolarga chidamlilik
Yakuniy sahna
30%40%

Diagramma kod sifatida

Darsdagi yakuniy sxemani matn ko'rinishida oling va Jira, GitLab, GitHub, Notion yoki hujjatga qo'ying: Mermaid u yerlarda o'zi chiziladi. D2 va PlantUML (Confluence, IntelliJ) uchun alohida variantlar bor.

Mermaid: sxema

flowchart LR
  n_user(["Do'kon ilovasi"])
  n_api["Qidiruv API"]
  n_db[("Mahsulotlar bazasi")]
  n_catalog["Katalog servisi"]
  n_indexer("Indekser")
  n_log[["O'zgarishlar log'i"]]
  n_shard1[("Indeks shard 1")]
  n_shard2[("Indeks shard 2")]
  n_user -->|"chaqiruv"| n_api
  n_catalog --> n_db
  n_db -->|"asinxron"| n_log
  n_indexer --> n_log
  n_api --> n_shard1
  n_api --> n_shard2
  n_indexer --> n_shard1
  n_indexer --> n_shard2

Mermaid: so'rovlar ketma-ketligi

sequenceDiagram
  participant n_api as Qidiruv API
  participant n_db as Mahsulotlar bazasi
  participant n_index as Qidiruv indeksi
  participant n_user as Do'kon ilovasi
  participant n_indexer as Indekser
  participant n_log as O'zgarishlar log'i
  participant n_shard2 as Indeks shard 2
  Note over n_api,n_db: Katalog kichikligida LIKE bilan qidirish
  n_api->>n_db: SELECT id, title, price_minor FROM products
  Note over n_api,n_db: 4 million mahsulot: har qidiruv jadvalni o'qiydi
  n_api->>n_db: EXPLAIN ANALYZE SELECT ... WHERE lower(title #124;#124; ' ' #124;#124; description) LIKE '%choynak%'#59;
  n_db-->>n_api: Seq Scan on products (rows removed by filter: 3 998 160)
  Note over n_api,n_index: Teskarisiga o'gir: so'zdan mahsulotlarga
  n_api->>n_index: term df postings (doc id: positions)
  Note over n_user,n_api: Bitta so'z, to'rt xil yozilgan
  n_user->>n_api: sellers wrote #34;g'ilof#34; (phone case) in 4 ways, 2 170 products
  Note over n_indexer,n_index: So'z nima ekanini bir marta, ikkala tomon uchun hal qil
  n_indexer->>n_index: analyze(#34;Telefon GʻILOFLARI, qora#34;)
  Note over n_api,n_index: Sotuv bo'yicha emas, mosligi bo'yicha sarala
  n_api->>n_index: query #34;elektr choynak#34; N = 4 000 000 avgdl = 12
  Note over n_indexer,n_db: Yangi mahsulot ertagacha ko'rinmaydi
  n_indexer->>n_db: 10:12 seller adds #34;Elektr choynak 2 l#34; id 4120551 -#62; Products DB ok
  Note over n_indexer,n_log: Indeksni bazaning o'zgarishlar log'idan ozuqlantir
  n_indexer->>n_log: cdc products op=u id=4120551 lsn 0/7A3F10
  Note over n_api,n_shard2: Hujjat bo'yicha bo'l, har bir shard'dan so'ra
  n_api->>n_shard2: search q=#34;elektr choynak#34; size=10 -#62; both shards
  Note over n_user,n_api: Xaridor #34;choyank#34; yozsa ham #34;choynak#34; ni top
  n_user->>n_api: POST /v1/search HTTP/1.1
  n_api-->>n_user: HTTP/1.1 200 OK

D2

direction: right

n_user: "Do'kon ilovasi" {
  shape: rectangle
}
n_api: "Qidiruv API" {
  shape: rectangle
}
n_db: "Mahsulotlar bazasi" {
  shape: cylinder
}
n_catalog: "Katalog servisi" {
  shape: rectangle
}
n_indexer: "Indekser" {
  shape: rectangle
  style.multiple: true
}
n_log: "O'zgarishlar log'i" {
  shape: queue
}
n_shard1: "Indeks shard 1" {
  shape: cylinder
}
n_shard2: "Indeks shard 2" {
  shape: cylinder
}

n_user -> n_api: "chaqiruv"
n_catalog -> n_db
n_db -> n_log: "asinxron"
n_indexer -> n_log
n_api -> n_shard1
n_api -> n_shard2
n_indexer -> n_shard1
n_indexer -> n_shard2

PlantUML: so'rovlar ketma-ketligi

@startuml
participant "Qidiruv API" as n_api
database "Mahsulotlar bazasi" as n_db
database "Qidiruv indeksi" as n_index
participant "Do'kon ilovasi" as n_user
participant "Indekser" as n_indexer
queue "O'zgarishlar log'i" as n_log
database "Indeks shard 2" as n_shard2
note over n_api, n_db : Katalog kichikligida LIKE bilan qidirish
n_api -> n_db : SELECT id, title, price_minor FROM products
note over n_api, n_db : 4 million mahsulot: har qidiruv jadvalni o'qiydi
n_api -> n_db : EXPLAIN ANALYZE SELECT ... WHERE lower(title || ' ' || description) LIKE '%choynak%';
n_db --> n_api : Seq Scan on products (rows removed by filter: 3 998 160)
note over n_api, n_index : Teskarisiga o'gir: so'zdan mahsulotlarga
n_api -> n_index : term df postings (doc id: positions)
note over n_user, n_api : Bitta so'z, to'rt xil yozilgan
n_user -> n_api : sellers wrote "g'ilof" (phone case) in 4 ways, 2 170 products
note over n_indexer, n_index : So'z nima ekanini bir marta, ikkala tomon uchun hal qil
n_indexer -> n_index : analyze("Telefon GʻILOFLARI, qora")
note over n_api, n_index : Sotuv bo'yicha emas, mosligi bo'yicha sarala
n_api -> n_index : query "elektr choynak" N = 4 000 000 avgdl = 12
note over n_indexer, n_db : Yangi mahsulot ertagacha ko'rinmaydi
n_indexer -> n_db : 10:12 seller adds "Elektr choynak 2 l" id 4120551 -> Products DB ok
note over n_indexer, n_log : Indeksni bazaning o'zgarishlar log'idan ozuqlantir
n_indexer -> n_log : cdc products op=u id=4120551 lsn 0/7A3F10
note over n_api, n_shard2 : Hujjat bo'yicha bo'l, har bir shard'dan so'ra
n_api -> n_shard2 : search q="elektr choynak" size=10 -> both shards
note over n_user, n_api : Xaridor "choyank" yozsa ham "choynak" ni top
n_user -> n_api : POST /v1/search HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
@enduml

PlantUML: komponentlar

@startuml
left to right direction
agent "Do'kon ilovasi" as n_user
component "Qidiruv API" as n_api
database "Mahsulotlar bazasi" as n_db
component "Katalog servisi" as n_catalog
collections "Indekser" as n_indexer
queue "O'zgarishlar log'i" as n_log
database "Indeks shard 1" as n_shard1
database "Indeks shard 2" as n_shard2
n_user --> n_api : chaqiruv
n_catalog --> n_db
n_db --> n_log : asinxron
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2
@enduml

Xulosa

Matn qidiruvining oltita qoidasi.

1) LIKE '%x%' har bir qatorni o'qiydi; kichik jadvaldan kattasiga yaramaydi. 2) So'z nima ekanini mahsulot ham, so'rov ham uchun bitta analyzer bilan hal qil: kichik harf, bitta alifbo, apostrof variantlarisiz, ehtiyotkor stemmer. 3) Teskari indeks so'zlarni saralangan postings'ga bog'laydi; qidiruv faqat shu ro'yxatlarni o'qiydi. 4) BM25 bilan sarala: kamyoblik hisobga olinadi, takrorlar to'yinadi, uzun matnlar chegirma oladi. 5) Indeksni bazaning o'zgarishlar log'idan ozuqlantir va near-real-time'ni qabul qil; narx va qoldiq bazadan qayta o'qiladi. 6) Hujjat bo'yicha shard qil, scatter-gather ishlat va xatolarga qat'iy cheklovlar bilan chidamli bo'l.

Ko'rsatkichlar: boshida va oxirida

Ko'rsatkichBoshidaOxirida
Qidiruv p9545 ms24 ms
Har qidiruvda o'qilgan qatorlar50 00021 000
Topilmagan kerakli mahsulotlar37%6%
Natijasiz qidiruvlar3%2%
Yozuvdan qidiruvgacha0 s2 s

Qadamlar

  1. Holat Katalog kichikligida LIKE bilan qidirish

    Sotuvchilar mahsulotni katalog servisi orqali qo'shadi, xaridorlar qidiruv qatoriga so'z yozadi.

  2. Muammo 4 million mahsulot: har qidiruv jadvalni o'qiydi

    Uch yildan keyin katalogda 4 million mahsulot va 1.2 GB matn bor.

  3. Yechim Teskarisiga o'gir: so'zdan mahsulotlarga

    Teskari indeks (inverted index) har bir so'z uchun shu so'z uchraydigan mahsulotlar ro'yxatini saqlaydi: uning postings'ini.

  4. Muammo Bitta so'z, to'rt xil yozilgan

    Tez, lekin kerakli mahsulotlarning uchdan biri hali ham topilmaydi.

  5. Yechim So'z nima ekanini bir marta, ikkala tomon uchun hal qil

    So'z indeksga tushishidan oldin analyzer uni bir xil ko'rinishga keltiradi: kichik harf, kirilldan lotinga, apostrofning hamma variantlari olib tashlanadi, tokenlarga bo'linadi, qisqa ro'yxatdagi qo'shimchalar kesiladi.

  6. Yechim Sotuv bo'yicha emas, mosligi bo'yicha sarala

    Endi "elektr choynak" ga 1 840 ta mahsulot mos keladi va tartib muhim.

  7. Muammo Yangi mahsulot ertagacha ko'rinmaydi

    Indeks har kecha qaytadan quriladi.

  8. Yechim Indeksni bazaning o'zgarishlar log'idan ozuqlantir

    Mahsulotlar jadvalidagi har bir commit bo'lgan o'zgarish CDC yoki outbox orqali o'zgarishlar log'iga tushadi.

  9. Yechim Hujjat bo'yicha bo'l, har bir shard'dan so'ra

    Tavsiflar va pozitsiyalar bilan indeks 38 GB ga yetadi va bitta node xotirasiga sig'maydi: gavjum paytda p95 sekin-asta o'sadi.

  10. Yechim Xaridor "choyank" yozsa ham "choynak" ni top

    Qidiruvlarning 2% i hali ham hech narsa topmaydi, asosan yozuv xatolari tufayli.

  11. Xulosa Xulosa

    Matn qidiruvining oltita qoidasi.

Atamalar

Teskari indeks (inverted index)
Har bir so'z uchun shu so'z uchraydigan hujjatlarning saralangan ro'yxatini (postings) saqlaydigan indeks. Qidiruv hujjatlarni emas, faqat so'rovdagi so'zlarning ro'yxatlarini o'qiydi va kesishtiradi.
Analyzer (matn tahlilchisi)
Matnni indeks tokenlariga aylantiradigan qadamlar zanjiri: kichik harf, bitta alifbo, apostrof variantlarini olib tashlash, tokenlarga bo'lish, stemming. Aynan o'sha analyzer so'rovga ham qo'llanishi shart.
BM25
Matn qidiruvining standart reyting formulasi. Kam uchraydigan so'zlar og'irroq (idf), takrorlar foyda beradi, lekin to'yinadi (k1), uzun matnlar chegirma oladi (b).
Near-real-time indeks
Yangi yozuvlar darhol emas, keyingi refresh'da, odatda soniyada bir marta qidiruvga ochiladigan indeks. Refresh qanchalik tez-tez bo'lsa, birlashtirish kerak bo'lgan mayda segmentlar shunchalik ko'p.
Scatter-gather
So'rov hamma shard'larga yuboriladi, har biri o'zining top-k natijasini qaytaradi, koordinator esa ularni bitta ro'yxatga birlashtiradi. Javob eng sekin shard qancha ishlasa, shuncha vaqt oladi.