EVAL R(0,1,8) CONFIRM S(y,x) R(3,4,10) CONFIRM S(x,y) R(0,2,9) CONFIRM T(x,w) R(0,1,8) CONFIRM T(x,w) R(0,1,8) CONFIRM S(y,x) CONFIRM T(x,w) Fill in Boolean Formula (False AND True) OR True Project R(x,y,z) on (x,y) (0,1) Output (0,1) S E M I - J O I N S P A R A L L E L I S M G R O U P I N G Parallel Evaluation of Multi-Semi-Joins Jonny Daenen Frank Neven Tony Tan Stijn Vansummeren Poster presentation VLDB 2016, New Delhi, India Semi-Joins R ⋉S = πR.∗(R ⋊⋉S) Semi-Join Reducers GYM (Afrati et al. 2014) Yannakakis 1981 Reduce Communication Overhead Bernstein et al. 1981 R1 R2 R4 R3 R5 R6 R ⋊⋉S = (R ⋉S) ⋊⋉(S ⋉R) 0 1 1 1 1 1 4 3 8 2 2 8 SGF Queries GF ~ Semi-Join Algebra Stricly = no top-level Boolean combinations Nesting Strictly Guarded Fragment Z1 = SELECT aut FROM Amazon(title,aut,’bad’) WHERE BN(title,aut,’bad’) AND BD(title,aut,’bad’) Z2 = SELECT newttl FROM Upcoming(newttl,aut) WHERE NOT Z1(aut) MSJ 0,1 REQUEST R(0,1,8) S(x,y) 1,0 REQUEST R(0,1,8) S(y,x) 0 REQUEST R(0,1,8) T(x,w) 1,0 ASSERT S(x,y) 1,0 ASSERT S(y,x) 0 ASSERT T(x,w) REQUEST R(0,1,8) S(x,y) REQUEST R(0,1,8) S(y,x) REQUEST R(0,1,8) T(x,w) ASSERT S(x,y) ASSERT S(y,x) ASSERT T(x,w) 0,1 0 1,0 0 1 8 0 3 2 9 10 4 R 4 3 1 3 0 2 S 1 0 0 7 4 9 T 1 Guard Atom Conditional Atoms EVAL(R, ϕ) MSJ(X1, X2) MSJ(X3) SELECT x,y FROM R(x,y,z) WHERE S(x,y) AND S(y,x) OR NOT T(x,w) BSGF Queries Boolean Combination X1 = SELECT x,y,z FROM R(x,y,z) WHERE S(x,y) X2 = SELECT x,y,z FROM R(x,y,z) WHERE S(y,x) X3 = SELECT x,y,z FROM R(x,y,z) WHERE T(x,w) 2 Rounds 100% 200% 300% 400% 500% 600% Net Time SEQ 100% 100% 100% 100% 100% PAR 59% 54% 68% 63% 63% GREEDY 60% 98% 56% 60% 74% HIVE1 241% 243% 129% 208% 465% HIVE2 139% 134% 138% 115% 476% PIG 217% 245% 201% 189% 237% 1-ROUND 43% 200% 400% 600% 800% Total Time 100% 100% 100% 100% 100% 253% 242% 245% 191% 265% 238% 170% 149% 168% 186% 225% 218% 142% 78% 211% 324% 317% 319% 117% 640% 540% 614% 490% 373% 576% 120% 200% 400% 600% Input 100% 100% 100% 100% 100% 240% 240% 240% 240% 291% 171% 110% 120% 132% 139% 246% 246% 124% 140% 298% 361% 361% 361% 181% 437% 344% 433% 344% 344% 535% 70% 100% 200% 300% 400% 500% A1 A2 A3 A4 A5 Communication 100% 100% 100% 100% 100% 133% 133% 133% 133% 161% 133% 108% 90% 120% 124% 202% 202% 122% 101% 244% 322% 322% 322% 161% 389% 304% 304% 304% 304% 367% 70% 50% 100% 150% 100% 100% 22% 44% 17% 36% 83% 69% 59% 92% 44% 131% 18% 100% 400% 700% 1000% 100% 100% 361% 43% 106% 27% 844% 61% 479% 58% 560% 87% 18% 100% 300% 500% 700% 900% 100% 100% 411% 51% 80% 25% 749% 80% 570% 77% 653% 73% 18% 100% 300% 500% 700% B1 B2 100% 100% 206% 28% 76% 18% 620% 67% 505% 66% 323% 63% 18% 25% 50% 75% 100% 125% 150% 175% Net Time SEQ-UNIT 100% 100% 100% 100% PAR-UNIT 31% 51% 73% 32% GREEDY-SGF 56% 71% 78% 42% 25% 50% 75% 100% 125% 150% Total Time 100% 100% 100% 100% 107% 121% 108% 67% 58% 74% 92% 57% 25% 50% 75% 100% 125% 150% Input 100% 100% 100% 100% 104% 108% 100% 79% 52% 61% 64% 50% 25% 50% 75% 100% 125% C1 C2 C3 C4 Communication 100% 100% 100% 100% 105% 105% 95% 76% 69% 79% 85% 72% Icons from “Business People Icons 11” via vectorpage.com, Creative Commons Attribution 3.0 License Hasselt University National Taiwan University Université Libre de Bruxelles Problem Cloud (AWS, GCP, etc.) Pay-as-you-go Minimize resource usage Keep low time SGF Queries Minimize total time Parallel queries ∩ R ⋉S R ⋉T R ⋉U ⋉ ⋉ ⋉ R S T U BSGF-OPT NP-hard (Nykiel et al. 2010) Greedy: 0 0 0 +200 +300 -100 X1 X2 X3 X1 X2 X3 EVAL Z := X1 ∧(X2 ∨¬X3) MSJ X1 := R(x, y) ⋉S(x, z) MSJ X2 := R(x, y) ⋉T(y) MSJ X3 := R(x, y) ⋉U(x) (a) EVAL Z := X1 ∧(X2 ∨¬X3) MSJ X1 := R(x, y) ⋉S(x, z) X3 := R(x, y) ⋉U(x) MSJ X2 := R(x, y) ⋉T(y) (b) EVAL Z := X1 ∧(X2 ∨¬X3) MSJ X1 := R(x, y) ⋉S(x, z) X2 := R(x, y) ⋉T(y) X3 := R(x, y) ⋉U(x) (c) SGF-OPT NP-hard Greedy: for each leaf find group with highest overlap +dependencies if no overlap, add one query to new group else add a max. overlap query to group remove leaf Z ⋉I H ⋉Q R ⋉S ∧T G ⋉S ∧T Z ⋉I H ⋉Q R ⋉S ∧T G ⋉S ∧T Multi-BSGF Cost