We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Pessimistic Cardinality Estimation

00:00

Formal Metadata

Title
Pessimistic Cardinality Estimation
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
In this work we introduce a novel approach to the problem of cardinality estimation over multijoin queries. Our approach leveraging randomized hashing and data sketching to tighten these bounds beyond the current state of the art. We demonstrate that the bounds can be injected directly into the cost based query optimizer framework enabling it to avoid expensive physical join plans. We outline our base data structures and methodology, and how these bounds may be introduced to the optimizer's parameterized cost function as a new statistic for physical join plan selection. We demonstrate a complex tradeoff space between the tightness of our bounds and the size and complexity of our data structures. This space is not always monotonic as one might expect. In order combat this non-monotonicity, we introduce a partition budgeting scheme that guarantees monotonic behavior. We evaluate ourmethods on GooglePlus community graphs~citegoogleplus, and the Join Order Benchmark (JOB)~citeLeis:2015:GQO:2850583.2850594. In the presence of foreign key indexes, we demonstrate a 1.7times improvement in aggregate (time summed over all queries in benchmark) physical query plan runtime compared to plans chosen by Postgres using the default cardinality estimation methods. When foreign key indexes are absent, this advantage improves to over 10times.
Magneto-optical driveData managementEstimationBound stateQuery languageProjective planeClassical physicsEstimatorLecture/Conference
Query languageUniformer RaumIndependence (probability theory)EstimatorQuery languageTheory of relativityMultiplicationCASE <Informatik>Product (business)Computer animation
Mathematical optimizationQuery languageUniformer RaumIndependence (probability theory)Bound stateGraph (mathematics)Library catalogEntropie <Informationstheorie>Variable (mathematics)LogarithmUniform convergenceAttribute grammarFunction (mathematics)Exponential functionDegree (graph theory)SoftwareGraph (mathematics)Nichtlineares GleichungssystemRandomizationPositional notationQuery languageInstance (computer science)Coefficient of determinationBound statePattern languageWell-formed formulaAbsolute valueFunction (mathematics)SummierbarkeitRandom variableGleichverteilungTerm (mathematics)Group actionPresentation of a groupRow (database)Finite-state machineVariable (mathematics)Theory of relativityGraph (mathematics)PseudonymizationNumberChainInformationCountingEntropie <Informationstheorie>Casting (performing arts)Student's t-testTable (information)Distribution (mathematics)Key (cryptography)Cross-correlationUniformer RaumCombinational logicMultiplication signQuicksortStatisticsProduct (business)ExponentiationProjective planeMaxima and minimaInequality (mathematics)Insertion lossCondition numberMobile WebWorkloadDivisorReal numberMachine visionForm (programming)WordEuler anglesPlastikkarteSimilarity (geometry)CASE <Informatik>PlanningIndependence (probability theory)SkewnessAttribute grammarDifferent (Kate Ryan album)Complex (psychology)Validity (statistics)Series (mathematics)MultiplicationRight angleNormal (geometry)Run time (program lifecycle phase)Mathematical optimizationCharacteristic polynomialComputer animation
Partition (number theory)Bound stateMathematical optimizationQuery languageHash functionCompilation albumDatabaseStatisticsWell-formed formulaDigital filterPredicate (grammar)Run time (program lifecycle phase)Exponential functionGraph (mathematics)Performance appraisalBenchmarkSkewnessComplex systemTopologyCross-correlationError messageDefault (computer science)Maxima and minimaSubject indexingLinear mapProcess (computing)Scale (map)Limit (category theory)Exclusive orReal numberMaxima and minimaPlanningHistogramCross-correlationFehlerschrankeAverageDefault (computer science)SkewnessChemical equationDifferent (Kate Ryan album)Formal grammarPerformance appraisalRun time (program lifecycle phase)Form (programming)EstimatorBound statePredicate (grammar)Multiplication signQuery languageHash functionTheory of relativityCorrespondence (mathematics)Characteristic polynomialInstance (computer science)Endliche ModelltheorieNumberWorkloadSpacetime2 (number)BenchmarkEntropie <Informationstheorie>WordGraph (mathematics)Group actionGraph (mathematics)Table (information)CountingStatisticsDegree (graph theory)Well-formed formulaMathematical optimizationEvent horizonFunction (mathematics)SubsetGame theoryPartition (number theory)CASE <Informatik>Similarity (geometry)Block (periodic table)Derivation (linguistics)Grass (card game)Patch (Unix)1 (number)Point (geometry)SummierbarkeitCollisionoutputStrategy gameInformationKey (cryptography)Order of magnitudePropagatorSubject indexingOperator (mathematics)Inclusion mapProcess (computing)Cartesian coordinate systemVisualization (computer graphics)Nichtlineares GleichungssystemComplex (psychology)Electric generatorAttribute grammarData modelAlgorithmMessage passingComputer animation
Transcript: English(auto-generated)