Multiroundalgoritmer används nu ofta i distribuerade databehandlingssystem, men i vilken utsträckning algoritmer kan dra nytta av att köra fler rundor är inte väl förstådd. Detta dokument besvarar denna fråga för flera rundor för problemet med att beräkna equijoin av n relationer. Med tanke på alla frågor Q med bredd w, skärningsbredd iw, ingångsstorlek IN, utgångsstorlek UT, och en kluster av maskiner med M =  och (IN 1 ) minne finns per maskin, där > 1 och w ≥ 1 är konstanter, visar vi att: Intersektionsbredd är en ny idé som vi introducerar för frågor och generaliserade hypertree decompositions (GHDs) av frågor som fångar hur anslutna angränsande komponenter av GHDs är. Vi uppnår vårt första resultat genom att introducera en distribuerad och generaliserad version av Yannakakis algoritm, kallad GYM. GYM tar som ingång alla GHD av Q med bredd w och djup d, och beräknar Q i O(d + log(n) rundor och O(n (n) w + OUT) 2 M ) kommunikationskostnad. Vi uppnår vårt andra resultat genom att visa hur man konstruerar GHDs av Q med bredd max (w, 3iw) och djup O(log(n)). Vi beskriver en annan teknik för att konstruera GHD med längre bredder och kortare djup, som visar andra kompromisser man kan göra mellan kommunikation och antalet rundor. nätverk. Kostnader för algoritmer i dessa system kan delas upp i: 1) lokal beräkning av maskiner; 2) kommunikation mellan maskinerna; och 3) antalet nya omgångar av beräkningar som startas, som kan ha stora omkostnader i vissa system, t.ex. på grund av att du läser indata från disken eller väntar på att resurser ska finnas tillgängliga i klustret. I detta dokument fokuserar vi på kommunikation och antalet rundor, liksom för många databehandlingsuppgifter, beräkningskostnaden i allmänhet subsumeras av kommunikationskostnaden [20, 21]. I detta dokument studeras problemet med att utvärdera en equijoin-fråga Q i flera beräkningsrundor i ett distribuerat kluster. Vi begränsar oss till frågor som är fullständiga, d.v.s. inte innehåller prognoser, men frågor kan innehålla själv-joins. Vi låter n vara antalet relationer, I indatastorleken, UT utgångsstorleken av Q, och M = o(IN) minne tillgängliga per maskin i kluster. Memorystorlekar på maskinerna fångar intuitivt olika parallellismnivåer: när minnesstorlekarna är mindre behöver vi ett större antal maskiner för att utvärdera fogen, vilket ökar parallellismen. Vi antar i hela tidningen att M =  och (IN 1 ) för vissa konstant > 1. För praktiska värden av ingångs- och minnesstorlekar, är en liten konstant. Till exempel, om IN är i terabyte, då även när M är i megabyte, 2. Vår studie av multiround gå algoritmer motiveras av två utvecklingar. För det första har det nyligen visat sig att det finns oöverkomligt höga lägre gränser för kommunikationskostnaden för en allroundalgoritm för att utvärdera vissa gå frågor [2, 5]. Till exempel, för kedjefrågan, C n =R 1 (A 0, A 1 ) R 2 (A 1, A 2 )... R n (A n1, A n ), den lägre gränsen på kommunikationskostnaden för någon en-runda algoritm är ≥ ( IN M ) n/4. 1 Till exempel, om indata är en petabyte, d.v.s., IN=10 15, även när vi har maskiner med tio gigabyte minne, dvs., M = 10 10, kommunikationskostnaden för någon en-round algoritm för att utvärdera C 16 fråga är 100000 petabyte. Dessutom håller denna nedre gräns även när frågeutgången är känd för att vara liten, t.ex., UT = O(IN), och inmatningen har ingen skev [5], vilket innebär att utforma multiround algoritmer är det enda sättet att beräkna sådana går mer effektivt. För det andra har driften av en ny beräkningsomgång minskat från flera minuter i de tidiga systemen (t.ex. Hadoop [4]) till millisekunder i vissa nya system (t.ex., Spark [32], vilket gör det praktiskt att köra algoritmer som består av ett stort antal rundor. Även om multiroundalgoritmer blir vanligt förekommande, är det svårt att förstå hur många algoritmer som kan dra nytta av att köra fler rundor. I den här artikeln besvarar vi denna fråga för equijoin-frågor. Vi beskriver en multiroundalgoritm, kallad GYM, för Generalized Yannakakis i MapReduce (avsnitt 4-5), som är en distribuerad och generaliserad version av Yannakakis algoritm för acykliska frågor [31]. GYM:s prestanda beror på två viktiga strukturella egenskaper hos inmatningsfrågan: djup och bredder av dess generaliserade hypertree nedbrytningar (GHDs). Vi presenterar sedan två algoritmer, Log-GTA (avsnitt 6) och C-GTA (avsnitt 7), för att konstruera GHDs av frågor med olika djup och bredder, exponera ett spektrum av kompromisser som man kan göra mellan antalet rundor och kommunikation med hjälp av GYM. I återstoden av detta avsnitt ger vi en översikt över våra resultat.
Referens REF har infört en multiround gå algoritm kallas GYM, som tar som ingång en generaliserad hypertree nedbrytning (GHD) D av Q. Algoritmen beräknar först flera mellanliggande relationer baserat på D i en omgång med hjälp av Shares.
GYM: A Multiround Distributed Join Algorithm
{'venue': 'ICDT', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}