Distinct value estimation for query planning
US11663213B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 25, 2020 |
| Grant date | May 30, 2023 |
| Priority date | — |
| Expiry date | Dec 31, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/24549
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The problem of distinct value estimation has many applications, but is particularly important in the field of database technology where such information is utilized by query planners to generate and optimize query plans. Introduced is a novel technique for estimating the number of distinct values in a given dataset without scanning all of the values in the dataset. In an example embodiment, the introduced technique includes gathering multiple intermediate probabilistic estimates based on varying samples of the dataset, 2) plotting the multiple intermediate probabilistic estimates against indications of sample size, 3) fitting a function to the plotted data points, and 4) determining an overall distinct value estimate by extrapolating the objective function to an estimated or known total number of values in the dataset.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.