1 of 28

Keď už relačná databáza nestačí...

Peter Krátky

2 of 28

1463736028948;640;542;mouseover;486;447;div;

1463736028997;641;541;mousemove;487;446;div;

1463736029010;642;541;mousemove;487;446;div;

1463736029015;642;540;mousemove;487;445;div;

1463736029064;643;539;mousemove;488;444;div;

1463736029115;644;539;mousemove;489;444;div;

1463736029123;645;538;mousemove;490;443;div;

1463736029137;645;537;mousemove;490;442;div;

1463736029139;646;537;mousemove;490;442;div;

1463736029147;647;537;mousemove;491;442;div;

1463736029153;647;536;mousemove;491;441;div;

1463736029159;647;535;mousemove;491;440;div;

1463736029167;648;535;mousemove;492;440;div;

1463736029191;649;534;mousemove;493;439;div;

1463736029196;649;533;mousemove;493;438;div;

1463736029225;650;532;mousemove;493;437;div;

1463736029239;650;531;mouseout;493;436;div;

1463736029239;650;531;mouseover;493;436;p;

1463736029239;650;531;mousemove;493;436;p;

1463736029241;650;530;mousemove;493;435;p;

1463736029242;651;530;mousemove;494;435;p;

1463736029247;651;529;mousemove;494;434;p;

1463736029252;652;528;mousemove;495;433;p;

1463736029255;653;528;mousemove;496;433;p;

1463736029259;653;527;mousemove;496;432;p;

1463736029262;653;526;mousemove;496;431;p;

1463736029268;654;525;mousemove;496;430;p;

1463736029274;654;524;mousemove;496;429;p;

1463736029276;655;524;mousemove;497;429;p;

1463736029281;655;523;mousemove;497;428;p;

1463736029283;655;522;mousemove;497;427;p;

1463736029293;655;521;mousemove;497;426;p;

1463736029297;656;521;mousemove;498;426;p;

1463736029303;656;520;mousemove;498;425;p;

1463736029307;657;519;mousemove;499;424;p;

1463736029313;657;518;mousemove;499;423;p;

1463736029319;657;517;mousemove;499;422;p;

1463736029325;658;516;mouseout;499;421;p;

1463736029325;658;516;mouseover;499;421;div;

1463736029325;658;516;mousemove;499;421;div;

1463736029328;658;515;mousemove;499;420;div;

1463736029330;658;514;mousemove;499;419;div;

1463736029335;658;513;mousemove;499;418;div;

1463736029341;659;511;mousemove;500;416;div;

1463736029345;659;510;mousemove;500;415;div;

1463736029349;659;509;mousemove;500;414;div;

1463736029350;659;508;mousemove;500;413;div;

1463736029353;659;507;mousemove;500;412;div;

1463736029355;660;506;mousemove;501;411;div;

1463736029356;660;505;mousemove;501;410;div;

1463736029358;661;504;mouseout;502;409;div;

1463736029359;661;504;mouseover;502;409;p;

1463736029359;661;504;mousemove;502;409;p;

1463736029363;661;502;mousemove;502;407;p;

1463736029366;661;501;mousemove;502;406;p;

1463736029369;662;499;mousemove;503;404;p;

1463736029373;662;497;mousemove;503;402;p;

1463736029375;662;496;mousemove;503;401;p;

1463736029379;663;495;mousemove;503;400;p;

1463736029381;663;494;mousemove;503;399;p;

1463736029382;663;493;mousemove;503;398;p;

1463736029386;663;492;mousemove;503;397;p;

1463736029388;663;491;mousemove;503;396;p;

1463736029391;663;490;mousemove;503;395;p;

1463736029395;663;489;mousemove;503;394;p;

1463736029397;663;488;mousemove;503;393;p;

1463736029403;663;487;mousemove;503;392;p;

1463736029407;663;486;mousemove;503;391;p;

1463736029409;664;486;mousemove;504;391;p;

1463736029410;664;485;mousemove;504;390;p;

1463736029413;664;484;mousemove;504;389;p;

1463736029419;664;483;mousemove;504;388;p;

1463736029424;664;482;mousemove;504;387;p;

1463736029431;664;481;mousemove;504;386;p;

1463736029437;664;480;mousemove;504;385;p;

1463736029509;663;480;mousemove;503;385;p;

1463736029515;662;480;mousemove;503;385;p;

1463736029523;661;480;mousemove;502;385;p;

Jednotlivec vygeneruje ~100kB za minútu

​

3 of 28

Relačná databáza (RDBMS)

  • Dáta: štrukturované, normalizované

​

  • Vlastnosti ACID �(atomicity, consistency, isolation, durability)

​

  • Use case: Vytváranie objednávok, prevody prostriedkov...

​

4 of 28

NoSQL databázy

  • Vlastnosti BASE �(basicly available, soft state, eventually consistent)

​

    • Menší dôraz na konzistenciu
    • Väčší dôraz na dostupnosť

​

​

​

​

​

Stĺpcové

Dokumentové

Grafové

Key-value

  • Iný spôsob ukladania dát

5 of 28

Dokumentové databázy

  • Dáta: Dokumenty so stromovou štruktúrou (napr. JSON), denormalizované

​

  • Use case: Potreba voľnej štruktúry dát (napr. produkty s variabilnými atribútmi)

​

  • Príklad: Elasticsearch, MongoDB

​

{

"Id":1002,

"Product": {

"Name": "Samsung S8"

"Price": 500.0,

"Category": "Smartphones"

"Camera": {

"Resolution": "12 Mpix",

"Autofocus": true,

}

}}

{

"Id":26572,

"Product": {

"Name": "Whirlpool AWE 50510"

"Price": 300.0,

"Category": "Washing machines"

"Energy data": {

"Class": "A++",

"Input": 2.3 W,

}

}}

6 of 28

Kľúč-hodnota databázy (key-value)

  • Dáta: Kľúč – hodnota (skalárna, štrukturovaná, blob)

​

  • Use case: Potreba rýchleho prístupu podľa kľúča, rýchleho uloženia (cachovanie dát, uloženie dočasných dát)

​

  • Príklad : Redis, Memcached

​

7 of 28

Grafové databázy

  • Dáta: Uzly (nodes), vzťahy (relationships), vlastnosti (properties)

​

  • Use case: Potreba modelovania vzťahov medzi entitami (reprezentácia sociálnej siete, odporúčanie súvisiacich článkov)

​

  • Príklad: neo4j

​

Name: John

Age: 32

Name: Peter

Age: 29

Name: Martin

Age: 40

knows

knows

8 of 28

Sĺpcové databázy

  • Dáta: Štruktúrované, uložené po stĺpcoch (nie riadkoch u RDBMS)

​

  • Use case: Potreba rýchleho dopytovania podľa atribútov – OLAP dopyty (analytické nástroje, ktoré počítajú štatistiky podľa filtrov)

​

  • Príklad: �MonetDB, Clickhouse�Cassandra (wide-column store)

​

Peter

Jane

Martin

Mark

Daniela

...

male

female

male

male

female

...

29

29

32

28

35

...

name

gender

age

9 of 28

Ako sme vytvorili vlastnú špecializovanú databázku

„ReachEngine“

10 of 28

Úloha: počet unikátnych ľudí podľa atribútov+geo

11 of 28

gender=male

AND age=18-25

AND age=26-35

AND home_locationXA > =149000

AND home_locationXB <= 149500

AND home_locationYA > =115000

AND home_locationYB <= 115200

hardware=Android

AND work_locationXB <= 149500

AND work_locationXA > =149000

AND work_locationYA > =115000

AND work_locationYB <= 115200

...

∩

∩

12 of 28

userId x18A y18A gender age

14241 144218 90754 Male 35 - 45

27813 144984 90384 Male 26 - 35

7276 143496 90832 Female 55 - 65

25577 143564 90956 Female 35 - 45

61 143560 90984 Male 35 - 45

9881 146464 90240 Female 35 - 45

8612 144640 89792 Female 35 - 45

25897 144944 90324 Male 26 - 35

9954 143616 90960 Female 45 - 55

26029 144672 89848 Female 65 -

26317 146652 90408 Male 35 - 45

10704 146492 90320 Male 26 - 35

19848 143516 90956 Male 26 - 35

19029 144226 90780 Female 45 - 55

14087 146484 90412 Male 35 - 45

478 143544 90928 Male 18 - 26

24514 143568 91056 Female 35 - 45

23208 143548 91048 Male 26 - 35

14172 143564 91008 Female 55 - 65

5583 143548 90922 Female 45 - 55

24565 146560 90336 Male 26 - 35

18026 143472 90940 Male 26 - 35

9443 146596 90016 Female 65 -

21025 144720 89776 Female 45 - 55

14051 146592 90328 Female 35 - 45

2095 143500 90900 Male 26 - 35

11652 143448 90816 Male 35 - 45

3244 146544 90368 Male 26 - 35

179 143444 90912 Male 35 - 45

2521 146524 90308 Male 26 - 35

Vhodná stĺpcová databáza

  • rýchle filtrovanie
  • kompresia
  • Vektorizácia (SIMD)

3 podproblémy:

  • výber podľa artibútov
  • geografický výber
  • počet unikátnych userov

13 of 28

[„ReachEngine“]

Výber podľa atribútov

14 of 28

INDEX

DATA

muž

žena

<30

>30

<30

>30

5

4

8

7

2

1

6

3

6

1

2

8

5

6

4

3

pohlavie

vek

VRSTVA 1

15 of 28

muž

žena

<30

>30

<30

>30

5

4

8

7

2

1

6

3

6

1

2

8

5

6

4

3

INDEX

DATA

pohlavie

vek

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

VRSTVA 1

muži, >30

16 of 28

áno

nie

Android

iPhone

Android

iPhone

5

4

8

7

2

1

6

3

6

1

2

8

5

6

4

3

INDEX

USERI

dáta

hardware

VRSTVA 2

Android aj iPhone, NEpoužívajú dáta

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

17 of 28

áno

nie

5

4

8

7

2

1

6

3

6

1

2

8

5

6

4

3

INDEX

USERI

dáta

národnosť

VRSTVA 2

Android aj iPhone, NEpoužívajú dáta

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

Android

iPhone

Android

iPhone

18 of 28

vlákno 1

vlákno 2

vlákno 3

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

Paralelizácia

19 of 28

[„ReachEngine“]

Geografický výber

20 of 28

Priestorový index

1000

3

2

1

6

7

3

4

8

7

1

2

8

4

3

9

INDEX

USERI

X

1001

1002

1003

1004

1005

1006

1007

1000

3

2

1

6

7

3

4

8

7

1

2

8

4

3

9

INDEX

USERI

Y

1001

1002

1003

1004

1005

1006

1007

21 of 28

Priestorový index

1000

3

2

1

6

7

3

4

8

7

1

2

8

4

3

9

INDEX

USERI

f(X,Y)

1001

1002

1003

1004

1005

1006

1007

22 of 28

Quadkey

zdroj: msdn.microsoft.com

23 of 28

Quadkey

(

qk >= 26525438207

AND qk <= 26525466623

) --approximate filtering

AND �(

x18b > 143455

AND y18b > 90911

AND x18a < 143615

AND y18a < 91007

) --finer filtering�

24 of 28

1000

3

2

1

6

7

3

4

8

7

1

2

8

4

3

9

2

INDEX

USERI

Quadkey (x,y)

VRSTVA 1

GEO výber

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

1001

1002

1003

1004

1005

1006

1007

25 of 28

1

2

3

4

5

6

7

8

9

10

ZOZNAM USEROV

Vektorizácia

26 of 28

Porovnanie

100 dopytov

​

  • MS SQL: 23 min
  • ReachEngine: 50 s

27 of 28

Zhrnutie

  • Niektoré use casy môže byť výhodné nahradiť špecializovanou NoSQL databázou
  • Lepšie uchopenie problému môže priniesť rýchlejšie a efektívnejšie riešenie

28 of 28

Stay in touch

Instarea s.r.o. �29. Augusta 36/A

811 09 Bratislava

www.instarea.com

​

Peter Krátky

Data Scientist & Software Developer

Instarea

peter.kratky@instarea.com

https://www.linkedin.com/in/peterkratky/

Thank you