Komplexa frågor för massiva dataanalys jobb har blivit allt vanligare. Många sådana frågor innehåller vanliga underuttryck, antingen inom en enda fråga eller bland flera frågor in som ett parti. Konventionella frågeoptimering inte utnyttja dessa underuttryck och producera suboptimala planer. Problemet med multi-query optimering (MQO) är att generera en optimal kombinerad utvärderingsplan genom att beräkna gemensamma underuttryck en gång och återanvända dem. Uttömmande algoritmer för MQO utforska ett O(n n ) sökutrymme. Således har detta problem främst behandlats med hjälp av olika heuristiska algoritmer, utan att ge några teoretiska garantier för kvaliteten på deras lösning. I detta dokument, istället för det konventionella kostnadsminimeringsproblemet, behandlar vi problemet som maximering av en linjär omvandling av kostnadsfunktionen. Vi föreslår en girig algoritm för denna förändrade formulering av problemet, som under svaga, intuitiva antaganden, ger en approximationsfaktor garanti för denna formulering. Vi fortsätter att visa att denna faktor är optimal, om inte P = NP. En annan anmärkningsvärd punkt om vår algoritm är att den enkelt kan införlivas i befintliga transformationsbaserade optimerare. Vi föreslår slutligen optimeringar som kan användas för att förbättra effektiviteten hos vår algoritm.
Ett nytt arbete utarbetade en approximationsalgoritm som körs i tid quadratic till antalet gemensamma underuttryck och ger teoretiska garantier på kvaliteten på den erhållna lösningen REF.
Efficient and Provable Multi-Query Optimization
{'venue': "PODS '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}