数据管理系统的近似技术

ApproximationTechniquesforDataManagementSystems“Wearedrowningindatabutstarvedforknowledge”JohnNaisbittCS186Fall2005TraditionalQueryProcessingExactanswersNOTalwaysrequiredDSSapplicationsusuallyexploratory:earlyfeedbacktohelpidentify“interesting”regionsAggregatequeries:precisionto“lastdecimal”notneedede.g.,“WhatpercentageoftheUSsalesareinNJ?”SQLQueryExactAnswerDecision

Support

Systems

(DSS)LongResponseTimes!GB/TBPrimarilyforAggregatequeriesGoalistoquicklyreporttheleadingdigitsofanswersInsecondsinsteadofminutesorhoursMostusefulifcanprovideerrorguaranteesE.g.,Averagesalary

$59,000+/-$500(with95%confidence)in10secondsvs.$59,152.25in10minutesAchievedbyansweringthequerybasedoncompactsynopsesofthedataSpeed-upobtainedbecausesynopsesareordersofmagnitudesmallerthantheoriginaldataFastApproximateAnswersApproximateQueryProcessingHowdoyoubuildeffectivedatasynopses???SQLQueryExactAnswerDecision

Support

Systems

(DSS)LongResponseTimes!GB/TBCompactDataSynopses“Transformed”QueryKB/MBApproximateAnswerFAST!!Sampling:BasicsIdea:AsmallrandomsampleSofthedataoftenwell-representsallthedataForafastapproxanswer,applythequerytoS&“scale”theresultE.g.,R.ais{0,1},Sisa20%sample selectcount(*)fromRwhereR.a=0 select5*count(*)fromSwhereS.a=0110111110000111110111010110110Red=inSR.aEst.count=5*2=10,Exactcount=10Unbiased:Forexpressionsinvolvingcount,sum,avg:theestimatorisunbiased,i.e.,theexpectedvalueoftheansweristheactualanswer,evenfor(most)querieswithpredicates!LeverageextensiveliteratureonconfidenceintervalsforsamplingActualansweriswithintheinterval[a,b]withagivenprobability

E.g.,54,000±600withprob90%Sampling:ConfidenceIntervalsIfpredicates,SaboveissubsetofsamplethatsatisfiesthepredicateQualityoftheestimatedependsonlyonthe

varianceinR&|S|afterthepredicate:So10Ksamplemaysufficefor10Browrelation!Advantageoflargersamples:canhandlemoreselectivepredicatesGuarantees?90%ConfidenceInterval(±)Methodas(S)(R)3.16*(S)/sqrt(|S|)Chebyshev(est.(R))always3.16*(R)/sqrt(|S|)Chebyshev(known(R))always1.22*(MAX-MIN)/sqrt(|S|)Hoeffdingas|S|

1.65*(S)/sqrt(|S|)CentralLimitTheoremConfidenceintervalsforAverage:selectavg(R.A)fromR(CanreplaceR.AwithanyarithmeticexpressionontheattributesinR)(R)=standarddeviationofthevaluesofR.A;(S)=s.d.forS.ASamplingfromDatabasesSamplingdisk-residentdataisslowRow-levelsamplinghashighI/Ocost:

mustbringinentirediskblocktogettherowBlock-levelsampling:rowsmaybehighlycorrelatedRandomaccesspattern,possiblyviaanindexNeedtoaccountforthevariablenumberofrowsinapage,childreninanindexnode,etc.AlternativesRandomphysicalclustering:destroys“natural”clusteringPrecomputedsamples:mustincrementallymaintain(atspecifiedsize)Fasttouse:packedindiskblocks,cansequentiallyscan,canstoreasrelationandleveragefullDBMSquerysupport,canstoreinmainmemoryOne-PassUniformSamplingBestchoiceforincrementalmaintenanceLowoverheads,norandomdataaccessReservoirSampling[Vit85]:MaintainsasampleSofafixed-sizeMAddeachnewitemtoSwithprobabilityM/N,whereNisthecurrentnumberofdataitemsIfaddanitem,evictarandomitemfromSInsteadofflippingacoinforeachitem,determinethenumberofitemstoskipbeforethenexttobeaddedtoSHistogramsPartitionattributevalue(s)domainintoasetofbucketsIssues:HowtopartitionWhattostoreforeachbucketHowtoestimateananswerusingthehistogramLonghistoryofuseforselectivityestimationwithinaqueryoptimizerRecentlyexploredasatoolforfastapproximatequeryprocessing1-DHistogramsNumberofbucketsB<<domainsizeEachbucketjuststoresatotalcountDistributeduniformlyacrossvaluesinthebucketPartitioncriteriaEqui-width:equalnumberofdomainvaluesperbucket(bad!!)Equi-depth/height:equalcount(“mass”)perbucketV-Optimal:minimizetotalvarianceofvaluecountsinbucketsCountinbucketDomainvalues1234567891011121314151617181920AnsweringQueriesUsingHistogramsAnsweringqueriesfrom1-Dhistograms(ingeneral):(Implicitly)mapthehistogrambacktoanapproximaterelation,&applythequerytotheapproximaterelationInsideeachbucket:UniformityAssumptionContinuousvaluemapping12345678910111213141516171819201234567891011121314151617181920Neednumberofdistinctineachbucket321231Countspreadevenlyamongbucketvalues-Uniformspreadmapping4R.A15HaarWaveletSynopsesWavelets:mathematicaltoolforhierarchicaldecompositionoffunctions/signalsHaarwavelets:simplestwaveletbasis,easytounderstandandimplementRecursivepairwiseaveraginganddifferencingatdifferentresolutionsResolutionAveragesDetailCoefficientsD=[2,2,0,2,3,5,4,4][2,1,4,4][0,-1,-1,0][1.5,4][0.5,0][2.75][-1.25]3210Haarwaveletdecomposition:[2.75,-1.25,0.5,0,0,-1,-1,0]HaarWaveletCoefficientsHierarchicaldecompositionstructure(a.k.a.ErrorTree)Conceptualtoolto“visualize”coefficientsupports&datareconstructionReconstructdatavaluesd(i)d(i)=(+/-1)*(coefficientonpath)Rangesumcalculationd(l:h)d(l:h)=simplelinearcombinationofcoefficientsonpathstol,hOnlyO(logN)terms22023544-1.252.750.500-10-1+-+++++++------

Originaldata3=2.75-(-1.25)+0+(-1)6=4*2.75+4*(-1.25)WaveletDataSynopsesComputeHaarwaveletdecompositionofDCoefficientthresholding:onlyB<<|D|coefficientscanbekeptBisdeterminedbytheavailablesynopsisspaceApproximatequeryenginecandoallitsprocessingoversuchcompactcoefficientsynopses(joins,aggregates,selections,etc.)Conventionalthresholding:TakeBlargestcoefficientsinabsolute

normalizedvalue

NormalizedHaarbasis:dividecoefficientsatresolutionjbyAllothercoefficientsareignored(assumedtobezero)ProvablyoptimalintermsoftheoverallSum-Squared(L2)ErrorMulti-dimensionalDataSynopsesProblem:ApproximatethejointdatadistributionofmultipleattributesMotivationSelectivityestimationforquerieswithmultiplepredicatesApproximatinggeneralrelations1020403590120AgeSalaryConventionalapproach:Attribute-ValueIndependence(AVI)assumptionsel(p(A1)&p(A2)&...)=sel(p(A1))*sel(p(A2)*...Simple--one-dimensionalmarginalssufficeBUT:almostalwaysinaccurate,grosserrorsinpracticeMulti-dimensionalHistogramsUsesmallnumberofmulti-dimensionalbucketstodirectlyapproximatethejointdatadistributionUniformspread&frequencyapproximationwithinbucketsn(i)=no.ofdistinctvaluesalongAi,F=totalbucketfrequencyapproximatedatapointsonan(1)*n(2)*...uniformgrid,eachwithfrequencyF/(n(1)*n(2)*...)1020403590120ActualDistribution(ONEBUCKET)16ApproximateDistributionDataSynopsesinCommercialDBMSsSamplingoperatorsans1-DhistogramsareavailableinmostcommercialDBMSsOracle,DB2,SQLServer,…Usedinternallybutalsoexposedtouser(e.g.,store“sampleview”)SQLServerhassupportfor2-Dhistograms!Thenextstep:SynopsesforXML!?!Howdoyoueffectivelysummarizeagraphstructureforquerieslike“//a//b[d]/*/c”??Data-StreamManagementTraditionalDBMS–datastoredinfinite,persistent

datasets

DataStreams–distributed,continuous,unbounded,rapid,timevarying,noisy,...Data-StreamManagement–varietyofmodernapplicationsNetworkmonitoringandtrafficengineeringTelecomcall-detailrecordsNetworksecurityFinancialapplicationsSensornetworksWeblogsandclickstreamsNetworksGenerateMassiveDataStreamsBroadband

InternetAccessConvergedIP/MPLSNetworkPSTNDSL/CableNetworksEnterprise

NetworksVoiceoverIPFR,ATM,IPVPNNetworkOperationsCenter(NOC)SNMP/RMON,NetFlowrecordsBGPOSPFPeerSNMP/RMON/NetFlowdatarecordsarrive24x7fromdifferentpartsofthenetworkTrulymassivestreamsarrivingatrapidratesAT&Tcollects600-800GigaBytesofNetFlowdataeachday!Typicallyshippedtoaback-enddatawarehouse(offsite)foroff-lineanalysisSourceDestination

Duration

BytesProtocol1220Khttp1624Khttp1520Khttp1940Khttp2658Khttp27100Kftp32300Kftp1880KftpExampleNetFlowIPSessionDataReal-TimeData-StreamAnalysisNeedabilitytoprocess/analyzenetwork-datastreamsinreal-time

Asrecordsstreamin:lookatrecordsonlyonceinarrivalorder!Withinresource(CPU,memory)limitationsoftheNOCCriticaltoimportantNMtasksDetectandreacttoFraud,Denial-of-Serviceattacks,SLAviolationsReal-timetrafficengineeringtoimproveload-balancingandutilizationDBMS(Oracle,DB2)Back-endDataWarehouseOff-lineanalysis–Dataaccessisslow,expensiveConvergedIP/MPLSNetworkPSTNDSL/CableNetworksEnterprise

NetworksNetworkOperationsCenter(NOC)BGPPeerR1R2R3Whatarethetop(mostfrequent)1000(source,dest)pairsseenbyR1overthelastmonth?SELECTCOUNT(R1.source,R1.dest)FROMR1,R2WHERER1.source=R2.sourceSQLJoinQueryHowmanydistinct(source,dest)pairshavebeenseenbybothR1andR2butnotR3?Set-ExpressionQueryData-Stream

Processing

ModelApproximateanswersoftensuffice,e.g.,trendanalysis,anomalydetectionRequirementsforstreamsynopsesSinglePass:Eachrecordisexaminedatmostonce,in(fixed)arrivalorderSmall

Space:LogorpolylogindatastreamsizeReal-time:Per-recordprocessingtime(tomaintainsynopses)mustbelow

StreamProcessingEngineApproximateAnswerwithErrorGuarantees“Within2%ofexactanswerwithhighprobability”StreamSynopses(inmemory)ContinuousDataStreamsQueryQR1Rk(GBs/TBs)(KBs)DistinctValueEstimationProblem:Findthenumberofdistinctvaluesinastreamofvalueswithdomain[0,...,N-1]Zerothfrequencymoment,L0(Hamming)streamnormStatistics:numberofspeciesorclassesinapopulationImportantforqueryoptimizersNetworkmonitoring:distinctdestinationIPaddresses,source/destinationpairs,requestedURLs,etc.Example(N=64)Hardproblemforrandomsampling![CCMN00]Mustsamplealmosttheentiretabletoguaranteetheestimateiswithinafactorof10withprobability>1/2,regardlessoftheestimatorused!Datastream:305301751037Numberofdistinctvalues:5Assumeahashfunctionh(x)thatmapsincomingvaluesxin[0,…,N-1]uniformlyacross[0,…,2^L-1],whereL=O(logN)Letlsb(y)denotethepositionoftheleast-significant1bitinthebinaryrepresentationofyAvaluexismappedtolsb(h(x))MaintainHashSketch=BITMAParrayofLbits,initializedto0Foreachincomingvaluex,setBITMAP[lsb(h(x))]=1Hash(akaFM)SketchesforCountDistinctx=5h(x)=101100lsb(h(x))=2000001BITMAP543210Hash(akaFM)SketchesforCountDistinctByuniformitythroughh(x):Prob[BITMAP[k]=1]=Prob[]=Assumingddistinctvalues:expectd/2tomaptoBITMAP[0],d/4tomaptoBITMAP[1],...LetR=