Aggregation in Main Memory

March302001DGRCFedStatsVisitAggregationinMainMemoryKennethA.RossColumbiaUniversityMarch302001DGRCFedStatsVisitResearchExperienceComplexqueryprocessingDataWarehousingMainmemorydatabasesStudents:KaziZaman,JunyanDingMarch302001DGRCFedStatsVisitMediatorQueryUnifiedResultsUserMain-MemoryDBMSTraditionalDBMS...ScenarioAMarch302001DGRCFedStatsVisitMediatorDataRequestUnifiedResultsUserWebTraditionalDBMS...ScenarioBMainMemoryDBSequenceOfInteractiveQueriesMarch302001DGRCFedStatsVisitMediatorDataRequestUnifiedResultsUserWebTraditionalDBMS...ScenarioCMainMemoryDBGraphicalUserInterfaceDynamicQueryMarch302001DGRCFedStatsVisitOutlineIntroductiontoDatacubesFrameworksforqueryingcubesTheMainMemorybasedframeworkExperimentalResultsConclusionsandPlanMarch302001DGRCFedStatsVisitTheCUBEBYOperatorStateYearGradeSalesCA1997Regular90NY1997Premium70CA1998Premium65NY1998Premium95StateYearGradeSalesCA1997Regular90CA1997ALL90ALL1997Regular90CAALLRegular90ALL1997Regular90ALL1997ALL160ALLALLRegular90CAALLALL155ALLALLALL320CUBEBY(sumSales)LargeincreaseintotalSize,especiallywithmanydimensions…….AdditionalrecordsMarch302001DGRCFedStatsVisitLatticeRepresentationState,Year,GradeState,YearState,GradeYear,GradeStateYearGradeMarch302001DGRCFedStatsVisitModelingQueriesSliceQueriesaskforasingleaggregaterecordSELECTState,year,sum(sales)FROMBLS-12345GROUPBYState,yearHAVINGState=“NY”ANDyear=“1998”March302001DGRCFedStatsVisitExistingFrameworksState,Year,GradeState,YearState,GradeYear,GradeStateYearGradeChoosesubsetofcubetomaterializebasedonworkload.MaterializeondiskAppropriaterecordrecoveredorcomputedforincomingslicequeryDrawbacks:IgnoresClusteringofRelationondisk.Smallestunitofmaterializationistoobig.March302001DGRCFedStatsVisitOurapproachState,Year,GradeState,YearState,GradeYear,GradeStateYearGradeThefullcubeisoftenlargerthanavailablememory,but...Thefinestgranularityaggregatemayfit.Anyrecordcanbecomputedwithouthavingtogotodisk.Howshouldthefinestgranularitybeorganized?March302001DGRCFedStatsVisitFrameworkLevel-1StoreLevel-2StorerecordsinlinkedlistsSlotdirectorySelectedcoarserecordsinhashtableFinestgranularitycuboidQueryqMarch302001DGRCFedStatsVisitTheLevel-1StoreRecordsareKey,Valuepairsstoredinahashtable.RecordscancontainALL’sGivenqueryQ,formcompositekeyandchecklevel-1store(constanttime).Ifnotfound,uselevel-2storeKeyValuea155b234c212…...March302001DGRCFedStatsVisitTheLevel-2StoreLevel-2StorerecordsinlinkedlistsSlotdirectoryFinestgranularitycuboidSlotdirectoryisorganizedasamultidimensionalarray:level2[sz1][sz2][sz3][sz4]Eachslotpointstoalinkedlistofelements.RecordsplacedaccordingtosetofmappingfunctionsHMarch302001DGRCFedStatsVisitUsingtheLevel-2storeb4QueryQwithoutALL’sd5a3c2Slot4Slot3Slot7Slot1Accesslistdenotedbylevel2[4][3][7][1];aggregatethosematching(a3,b4,c2,d5).March302001DGRCFedStatsVisitUsingtheLevel-2storeALLQueryQwithALL’sALLa3c2Slot4ListofSlotsSlot7ListofSlotsAccesslistsmatchinglevel2[4][*][7][*];aggregatethosematching(a3,*,c2,*).March302001DGRCFedStatsVisitDemoShowsmultidimensionaldataset(subsetofcolumnsof5%CensussampleforNYin1990).Userasksqueries:fastanswers.Future:UserInterfaceasksmanyqueries,withdisplaychanginginteractively.demoMarch302001DGRCFedStatsVisitExperimentalResultsQueryProcessingTimevsAdditionalMemoryUsed(realdataset,10^6records,8dimensions)051015020406080AdditionalMemoryUsedinMBAveragetimeperqueryinmillisecondsQueryCostScanningallrecordstakes194ms.March302001DGRCFedStatsVisitImportanceofWork•Aggregationisfundamentaltoanalysis.•Makeanalysisinteractive,evenformanydimensions.•Makeavarietyofaggregategranularitiesavailable,wherepossible.March302001DGRCFedStatsVisitContributionsAMainMemorybasedframeworkforansweringdatacubequeriesefficiently.QueryPerformanceinthe2-4msrangewhichismoreefficientthangoingtodisk.March302001DGRCFedStatsVisitPlanIntegratewithuserinterfacetogeneratedynamicqueries.Self-tuningcapability.Multipledatasets.Workwithagenciestogeneratevalue–Forintra-agencyanalysis–Forenhanceddatadissemination