THESIS (OTHER THAN BRIEF EXCERPTS REQUIRING ONLY P

PARALLELRELATIONALOLAPByToddEavisSUBMITTEDINPARTIALFULFILLMENTOFTHEREQUIREMENTSFORTHEDEGREEOFDOCTOROFPHILOSOPHYATDALHOUSIEUNIVERSITYHALIFAX,NOVASCOTIAJUNE27,2003c°CopyrightbyToddEavis,2003DALHOUSIEUNIVERSITYDEPARTMENTOFCOMPUTERSCIENCETheundersignedherebycertifythattheyhavereadandrecommendtotheFacultyofGraduateStudiesforacceptanceathesisentitled\ParallelRelationalOLAPbyToddEavisinpartialful¯llmentoftherequirementsforthedegreeofDoctorofPhilosophy.Dated:June27,2003ExternalExaminer:VirendraBhavsarResearchSupervisor:AndrewRau-ChaplinExamingCommittee:QigangGaoEvangelosMiliosiiDALHOUSIEUNIVERSITYDate:June27,2003Author:ToddEavisTitle:ParallelRelationalOLAPDepartment:ComputerScienceDegree:Ph.D.Convocation:OctoberYear:2003PermissionisherewithgrantedtoDalhousieUniversitytocirculateandtohavecopiedfornon-commercialpurposes,atitsdiscretion,theabovetitleupontherequestofindividualsorinstitutions.SignatureofAuthorTHEAUTHORRESERVESOTHERPUBLICATIONRIGHTS,ANDNEITHERTHETHESISNOREXTENSIVEEXTRACTSFROMITMAYBEPRINTEDOROTHERWISEREPRODUCEDWITHOUTTHEAUTHOR'SWRITTENPERMISSION.THEAUTHORATTESTSTHATPERMISSIONHASBEENOBTAINEDFORTHEUSEOFANYCOPYRIGHTEDMATERIALAPPEARINGINTHISTHESIS(OTHERTHANBRIEFEXCERPTSREQUIRINGONLYPROPERACKNOWLEDGEMENTINSCHOLARLYWRITING)ANDTHATALLSUCHUSEISCLEARLYACKNOWLEDGED.iiiTothetwowomeninmylife:AmberandBailey.ivTableofContentsTableofContentsvListofAcronymsxListofTablesxivListofFiguresxvAbstractiAcknowledgementsii1Introduction11.1OverviewofPrimaryResearch......................31.1.1ParallelizingtheDataCube...................41.1.2ComputingPartialCubesinParallel..............51.1.3ParallelMulti-dimensionalIndexing...............51.2OurParallelDesignModel........................71.3ALookAhead...............................112AnIntroductiontoOLAPandtheDataCube122.1Introduction................................122.2DecisionSupportSystems........................132.2.1TheHistoricalContextofOLAP................152.3De¯ningOLAP..............................172.3.1OLAP:AFunctionalDe¯nition.................192.3.2OLAP:TheFASMIDe¯nition..................202.4TheDataWarehouse...........................232.4.1Architecture............................242.4.2TheStarSchema.........................262.4.3MOLAP,ROLAPandMulti-dimensionalData.........27v2.5TheDataCube..............................292.5.1TheDataCubeOperator....................342.6DataCubeAlgorithms..........................342.6.1TopDown.............................352.6.2BottomUp............................402.6.3Array-based............................442.7Conclusions................................493ComputingFullDataCubesinParallel513.1Introduction................................513.2RelatedWork...............................523.3Motivation.................................603.4ANewApproachtoParallelizingtheDataCube............623.4.1TheTargetArchitecture.....................623.4.2ASequentialBase.........................643.4.3PartitioningforParallelComputation..............653.4.4TheParallelPipeSortAlgorithm................693.5OptimizingPerformance.........................713.5.1OptimizingSortingOperations.................733.5.2DataMovement..........................763.5.3AggregationOperations.....................813.5.4Input/OutputPatterns......................853.6TheCostingModel............................893.6.1CuboidSizeEstimation.....................903.6.1.1Cardinality-basedEstimation.............913.6.1.2SampleScaling.....................913.6.1.3AProbabilisticMethod................923.6.1.4OurOwnProbabilisticApproach...........933.6.2PipelineCostEstimation.....................953.6.2.1Input/Output......................963.6.2.2Scanning........................973.6.2.3Sorting.........................983.6.3Puttingitalltogether......................993.7Implementation..............................1023.7.1GeneratingDataCubeInput..................1033.8Analysis..................................1033.8.1TheSchedulingPhase......................1063.8.2WorkloadPartitioning......................1073.9ExperimentalEvaluation........................1123.9.1ParallelSpeedup.........................114vi3.9.2DataSetSize...........................1173.9.3DimensionCount.........................1193.9.4Over-SamplingFactor......................1213.9.5RecordSkew...........................1213.9.6PipelinePerformance.......................1243.10ReviewofResearchObjectives......................1253.11Conclusions................................1274ComputingPartialCubesinParallel1294.1Introduction................................1294.2RelatedWork...............................1304.3Motivation.................................1374.4ANewPartialCubeMethod.......................1384.4.1AddingNon-EssentialNodestotheSelectedSet........1394.4.2BuildingtheCompleteScheduleTree..............1454.5AnalysisandOptimization........................1544.5.1Complexity............................1544.5.2ReducingtheCostofBuildingtheEssentialTree.......1554.5.2.1RecursivePipelineGeneration.............1554