» »

Kako pohitrit build-anje index za autocomplete?

Kako pohitrit build-anje index za autocomplete?

HotBurek ::

Dobro jutro.


Evo, nov večer, nov izziv. Kako pohitrit build-anje indexa za autocomplete.

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

PRIMER

Tabela produktov:
id|name                 |
--+---------------------+
 0|bio brokoli 500g novo|
 1|banane bio           |
 2|brokoli              |
 3|bio košuta noro      |

Na client strani (web vmesnik) se za vsak keyup naredi xhr request, potem pa čaka na response iz baze.

Npr. da client vnese "b".

Za zgornji primer naj autocomplete vrne (LIMIT 11):
bio
banane
brokoli
bio 500g
bio noro
bio novo
bio banane
bio košuta
bio brokoli
bio 500g novo
bio 500g noro

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

TRENUTNI SETUP

KORAK 1:

Za "bio brokoli 500g novo" se naredi split po presledku in vsak word vnese v tabelo word-ov, nazaj pa vrača id, pod katerim je shranjen word.
Če bi bila tabela prazna, bi bil "bio"=0, "brokoli"=1, "500g"=2, itn.

KORAK 2:

Iz inputa "bio brokoli 500g novo" se naredi group-e vseh kombinacije word-ow ("bio", "brokoli", "bio novo", "500g brokoli", "500g brokoli novo", "novo bio brokoli"), s tem da je trenutno group-a lahko sestavljena z največ 3 word-i. Brez te omejitve lahko pride do nekaj tisoč različnih group-ov na posamičen produkt. Trenutno je nek max, ki se prikaže ~250 group na produkt. (Pravkar naletel na enega z 1500 kombinacij kljub omejitvi na max 3.)
Se pravi "vse" kombinacije v kontekstu, da niso zgolj od leve proti desni, tudi v obratno smer, ter z skakanjem naprej-nazaj ("1 3 2", "4 1 2").

Tule je tema na to temo: [Python] Kako iz seznama narediti možne kombinacije le-teh?

KORAK 3:

Vsako od teh kombinacij se vnese v tabelo autocomplete group. Zraven se vnese podatek, v katero grupo spada kombinacija (npr. "bio 500g" in "500g bio" spadata v isto grupo "0_2"). Pri iskanju se vrača samo eno kombinacijo iz posamične grupe.
Ter, če gre za ponovni vnos iste kombinacije (iz zgornjega primera se "bio" vnese 3x, "brokoli" 2x), se poveča counter za +1.

AUTOCOMPLETE:

Ko pride request, se naredi search v autocomplete group tabeli. LIMIT je 11, ORDER BY pa:

ORDER BY `no_of_items` ASC, `count_inserts` DESC, `text` ASC, CHAR_LENGTH(`text`) ASC

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

PROBLEM

In ta zadeva, gledano skozi oči uporabnika na web vmesniku, dela tip-top.

Problem pa je, da build-anje teh index-ov traja celo večnost.

Trenutni podatek kaže, da v eni uri z-build-a groupe za vsega 700 produktov, kar je 0,15% (vseh produktov je 440.000).


Kar se tiče insert time-a, le tega ne vidim kot glavni problem, ampak veliko število kombinacij.


Sedaj pa vprašanje. Kakšne bi bile kaj opcije, da bi se tole pohitrilo? :(
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window
  • spremenilo: HotBurek ()

smacker ::

440.000 produktov * 250 kombinacij => cca. 100 mio recordov. Index bo v gigabajtih, dober database strežnik bi prebavil, za običajne mašine pa najbrž sfali RAMa in je počasno ko drek.
Raje uporabi primernejšo podatkovno strukturo, recimo: https://www.geeksforgeeks.org/auto-comp...

MH0 ::

Kako daleč pa te pripelje čisto navadni LIKE?

kuall ::

to ne dela ok?

če vtipka
bio brokoli

poženeš ta query:

where name like '%bio%brokoli' or name like '%brokoli%bio%'

če pa hočeš, da najde ime, kjer je katerakoli od besed poženeš query 2x:
where name like '%bio%'
union all
where name like '%brokoli%'


ravnokar pognal tale query na tabeli, ki ima 10 milijonov vrstic. vrne precej hitro, najde 100 vrstic v parih sekundah. če pa namesto % spredaj damo samo zadaj vrne takoj, ker lahko (bolje) uporabi index.
tak da če parsal stavek v besede in besede shranil v svojo kolono bi bila opcija za pohitritev, da ti namesto v 7 sekundah vrne instantno.

HotBurek ::

smacker, hvala za link. Trenutno sem za nekaj razredov prekratek za tak nivo.

--------

MH0, misliš za autocomplete? To bi bil (i guess) kr fail, ker bi za input "b" dobil izpisan celoten string "bio brokoli 500g novo". Se pravi brez "bio" in drugih besed. Razen, če je v tabeli kak produkt, ki ima v imenu zgolj "bio".

UPDATE:

Evo, potestiral query LIKE "b%" in ORDER BY LENGTH(`name`) ASC. Ni slabo. Bom dal v web vmesnik in tam potestiral, da vidim, kako zgleda tam.

--------

kuall, podobno tvojem primeru (%niz%) sem uporabil pri search funkciji, in takoj videl kje je problem.

Namreč, tak query najde tudi rezultate, ki imajo sredi (ali na koncu) stringa iskani niz.

In je problem sortirat, da so najbolj kvalitetni na vrhu.

Npr. LIKE %alla% potem poleg alla vrne še: balla, dallas, allan, caballa, vallauris, gallardo, farfalla, vallado itn.

--------

Bom pa vseeno moral pripravit nek seznam kombinacij, ker rezultate search-a predhodno z-build-am. S tem lahko rangiram po lastnem algoritmu. Kar sem tudi potestiral in dela gut, tako hitrost build-anja, kot samo rangiranje.

No, in glede teh kombinacij sem naštudiral, da preveč kompliciram. Zato bom naredil enostavneje.

Za input "a b c d" bom generiral samo:
a
a b
a b c
a b c d
b
b c
b c d
c
c d
d

To je to. In na tak način bi moralo leteti na polno. Bom poročal.
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

HotBurek ::

Evo, tisto z iskanjem za autocomplete z LIKE ni (sprejemljivo) gut.

Search:
WHERE `name` LIKE "cisco%" ORDER BY LENGTH(`name`) ASC

Rezultati:
cisco c9300l 24p 4g a network switch
cisco business 350 12xs managed switch
cisco business 350 16xts managed switch
cisco business 350 24xts managed switch
cisco cab stk e 1m networking cable black
cisco cab stk e 3m networking cable black
cisco sf350 08 8 port 10 100 managed switch
cisco sf352 08 8 port 10 100 managed switch
cisco gigabit power injector sb pwr inj2 eu
cisco sf350 24 24 port 10 100 managed switch
cisco catalyst c9300l 24p 4g e network switch

Za autocomplete bo treba zbuildat nekaj opcij. A bolj na enostaven način, kot sem zgoraj omenil.
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

mr_chai ::

V kateri bazi že delaš sploh ? Za Postgres vem, da imaš prov za tex search dodatno podporo, ko imaš recimo lahko slovenski parser ki ti vse besede tokenizira in klasificira. In tud dela ko šus. Mogoče bolš če migriraš na postgres, tam je kar dober support za te stvari.

https://www.postgresql.org/docs/current...

Pomebno je tudi to, da ti stop worde (besede, ki so preveč pogoste, da bi jih blo smiselno indeksirat) ven pomeče

Zgodovina sprememb…

  • spremenilo: mr_chai ()

kuall ::

rešitev je parsanje tekstov v besede preden jih vstaviš v bazo s c# itd (ali sql jobom) in shranjevanje besed v svojo kolono in uporaba like 'beseda%'
zdaj če hočeš zelo pameten iskalnik, da sortira zadetke po relavantnosti, kot jih google bo treba iznajti/poiskat kak bolj pameten algoritem. ampak jaz ne bi kompliciral, time is money, razen če imaš preveč časa. tu smo potem že počas v AI vodah bi rekel in moraš algoritem raztuhtat na kakem sprehodku.

HotBurek ::

Evo, sprememba da se build-a bistveno manj in bolj enostavne kombinacije... v eni uri je naredilo 1,15%.

Se pravi 4 dni. Kar je sprejemljivo.
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

MH0 ::

Pač daš
1, name where like 'bio %'
Union
2, name where like '% bio %'
...
Order by 1,2

Že moraš vedeti kaj bi rad. Autocomplete pa sem vedno omejeval na vsaj 3 znake inputa in v selectu omejil število recordov na smiselno vrednost ta ui.

HotBurek ::

Dobro jutro.


Evo, fantje in dekline, da pošeram, kako se je zadeva odvijala.

Po tistem, ko sem pognal buildanje indexa in izračunal, da naredi 1.15% na uro, sem šel spat. In potem čez nekaj ur, ko pogledam, kako daleč je buildanje prišlo, sem hitro ugotovil, da se je vnos podatkov bistveno upočasnil. Se pravi, več je bilo podatkov v tabeli, počasnejši je bil vnos.

In tu pride ideja, ki sem jo ravnokar speljal do konca.

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

KORAK 1

Najprej sem nareditl tabelo autocomplete_template in jo uporabil za generiranje DDL-ja.

KORAK 2

Spisal sem Python skripto, ki ima tri counterje: row_id = 0, table_id = 0 in insert_counter = 0.

- Skozi celoten vnos se row_id povečuje po 1. Neke vrste autoincrement, na client strani. Preverjena tehnologija. 8-)
- Za vsak vnos se insert_counter poveča za eno. A ko ta pride do 1000, se ga resetira na 0, table_id se poveča za 1, ter skripta požene SQL ukaz, ki naredi novo tabelo. Pri id-jih za imena tabel sem uporabil zfill(9)

Rezultat je bil 20.000 tabel, v vsaki po 1000 vrstic.

autocomplete_000000000
autocomplete_000000001
autocomplete_000000002
itn.

KORAK 3

Pripravi se tabelo autocomplete_merge, ki ima isto strukturo, kot ostale tabele, brez vseh index-ov.

KORAK 4

Ko je Pytohn skripta po dveh, treh dneh končala, je zgenerirala dva fajla: build_autocomplete.sqlmerge in build_autocomplete.sqldrop

V prvem fajlu so ukazi za združitev podatvok v skupno tabelo autocomplete_merge.

INSERT INTO `autocomplete_merge` (`id`, `text`, `no_of_items`)
    SELECT `id`, `text`, `no_of_items` FROM `autocomplete_000000000`;
INSERT INTO `autocomplete_merge` (`id`, `text`, `no_of_items`)
    SELECT `id`, `text`, `no_of_items` FROM `autocomplete_000000001`;
INSERT INTO `autocomplete_merge` (`id`, `text`, `no_of_items`)
    SELECT `id`, `text`, `no_of_items` FROM `autocomplete_000000002`;
itn.

V drugem fajlu so ukazi za izbris tabel.

DROP TABLE `autocomplete_000000000`;
DROP TABLE `autocomplete_000000001`;
DROP TABLE `autocomplete_000000002`;

KORAK 5

Ko so vsi podatki bili v tabeli autocomplete_merge, sem z spodnjim ukazom prišel do željenih podatkov za tabelo autocomplete_group.
INSERT INTO `autocomplete_group` SELECT ... FROM `autocomplete_merge` ... GROUP BY ...

Vsega skupaj nekje 10.000.000 vrstic.

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

SEDAJ PA NASLEDNJI PROBLEM

Tabela autocomplete_group ima štiri stolpce:

`id` INT, `text` TEXT, `no_of_items` INT, `count_inserts` INT

Postavljene imam 4 index-e, za vsak stolpec po enega, vsi BTREE, ter še enga, ki pokriva 3 stolpce hkrati:

CREATE INDEX `autocomplete_group_tnoici_IDX`
USING BTREE ON `autocomplete_group` (`text`(50), `no_of_items`, `count_inserts`);

Stored procedra `sp_autocomplete_group_search` za search je sledeča (p_search_query se vedno konča z %, se pravi "ana%", "kruh%" itn.):

SELECT `text`
FROM `autocomplete_group`
WHERE `text` LIKE p_search_query
ORDER BY `no_of_items` ASC, `count_inserts` DESC, CHAR_LENGTH(`text`) ASC, `text` ASC
LIMIT 11;

In sedaj zagonetka:

CALL `sp_autocomplete_group_search`('a%'); # response traj 2.44 s
CALL `sp_autocomplete_group_search`('an%'); # response traj 828 ms 
CALL `sp_autocomplete_group_search`('ana%'); # response traj ~200 ms 
CALL `sp_autocomplete_group_search`('x%'); # response traj 494 ms
CALL `sp_autocomplete_group_search`('b%'); # response traj 3.73 s
CALL `sp_autocomplete_group_search`('y%'); # response traj 380 ms
CALL `sp_autocomplete_group_search`('q%'); # response traj 464 ms


Iskanje po "x%", "y%", "q%" dela normalno hitro, po "a%", "b%" pa traja 8~10x dlje. Krneki.

Kak index bi (še) lahko postavit na to tabelo, da bi pohitril query-je z kratke vnose?


OZ. ZAKAJ DELA QUERY PO "a%" POČASNEJE KOT QUERY PO "ANA%"?


Ena način pohitritve je, da se naredi prebuild cache za query-je dolžina 2 ali manj. Teh je, če sem prav preštel, vsega 1528. In za te bi naredil tabelo key-value pair, ki za string dolžine 1 ali 2 vrne nek id, ta id pa potem predstavlja file name na disku, ki že ima rezultate in se jih samo prebere in vrne web klientu.

Za ostale, ki so dolžine 3 ali več, pa direkt query v tabelo autocomplete_group, saj to pa dela ko šus (response na web klientu je v rangu 200 in nekaj ms).
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

DamijanD ::

Če imaš na tabeli indexe, potem vsak insert zahteva tudi posodabljanje teh indexov - večja kot je tabela, več časa ta operacija zahteva. Če pa imaš samo tabelo brez vseh indexov, bi pa vsi inserti morali trajati enako dolgo (razen občasno vmes, ko se dela nov page)


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Kako napisat SQL query?

Oddelek: Programiranje
131295 (501) HotBurek
»

Iskalnik po spletnih trgovinah: kje začeti pri podatkih?

Oddelek: Izdelava spletišč
191842 (1231) RedDrake
»

[SQL] Ali je možno postavit UNIQUE index po grupah?

Oddelek: Programiranje
211599 (1000) Spura
»

SQL vprasanje (strani: 1 2 )

Oddelek: Programiranje
688357 (5036) BivšiUser2
»

MS Access (strani: 1 2 )

Oddelek: Programiranje
647403 (5461) travica

Več podobnih tem