IP Library › Granted Patent US 12,437,522
Granted Patent B2
US 12,437,522 · App. 17/566,996 · Granted Oct 7, 2025

Adapting learned cardinality estimators to data and workload drifts

Inventors: Yao Lu (Redmond, WA); Srikanth Kandula (Redmond, WA); Beibin Li (Redmond, WA)
Assignee: MICROSOFT TECHNOLOGY LICENSING, LLC
G06V10/776G06N3/045G06V10/7747
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,437,522
App. No.
17/566,996
Granted
Oct 7, 2025
Kind
B2
Abstract

A method of updating a trained cardinality estimation model includes receiving a cardinality estimation model with cardinality labels and detecting a drift in underlying data or predicates of the cardinality estimation model. The type of the detected drift is determined and new test queries that mimic test queries for the detected drift are synthesized. A portion of the synthesized test queries is selected to reduce annotation cost and used to update the cardinality estimation model.

Claims (49)

1. A method of updating a trained cardinality estimation model implement in a computing system, the method comprising:

receiving a cardinality estimation model with training predicates and cardinality labels;

detecting a drift in underlying data or predicates of the cardinality estimation model;

determining a type of the detected drift;

based on the type of the detected drift, synthesizing new test queries that mimic test queries for the detected drift;

selecting a portion of the new or synthesized test queries to annotate with cardinality labels so as to reduce annotation cost; and

updating the cardinality estimation model with newer predicates and cardinality labels.

2. The method of claim 1 , wherein the detecting is performed periodically.

3. The method of claim 1 , wherein the detecting is performed when an evaluation error of the cardinality estimation model on the test queries exceeds a threshold beyond the error observed during training.

4. The method of claim 1 , wherein the determining the type of the detected drift comprises counting a fraction of rows that are new or have changed since the cardinality estimation model was last trained and measuring a change in ground truth cardinality for one or more canary predicates.

5. The method of claim 1 , wherein the determining the type of the detected drift comprises determining that the number of new queries available is below the number of annotated queries necessary to train the cardinality estimation model or when an insufficient number of queries have ground truth labels.

6. The method of claim 1 , further comprising:

injecting newly arrived predicates into a query pool;

computing and using embeddings for the query predicates;

updating a generator and discriminator if synthetic queries are needed; and

updating the embeddings.

7. The method of claim 1 , further comprising determining a plurality of types of the drifts.

8. The method of claim 6 , further comprising using learned embeddings of query predicates to decouple adaptation components from featurizations used by the cardinality estimation model.

9. The method of claim 6 , further comprising synthesizing new query predicates using predicate embeddings in the query pool.

10. The method of claim 9 , further comprising receiving a predicate embedding as input and predicting whether a given predicate resembles a training, test, or generated workload.

11. A computing system, comprising:

one or more processors; and

a computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by the processor, cause the computing system to perform operations comprising:

detecting a drift in underlying data or predicates of a cardinality estimation model;

determining a type of the detected drift;

based on the type of the detected drift, synthesizing new test queries that mimic test queries for the detected drift;

selecting a portion of the new or synthesized test queries to annotate with cardinality labels so as to reduce annotation cost; and

outputting newer predicates and cardinality labels for updating the cardinality estimation model.

12. The computing system of claim 11 , wherein the determining the type of the detected drift comprises counting a fraction of rows that are new or have changed since the cardinality estimation model was last trained, and measuring a change in ground truth cardinality for one or more canary predicates.

13. The computing system of claim 11 , wherein the determining the type of the drift comprises determining that the number of new queries available is below the number of annotated queries necessary to train the cardinality estimation model or when an insufficient number of queries have ground truth labels.

14. A computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

detecting a drift in underlying data or predicates of a cardinality estimation model;

determining a type of the detected drift;

based on the type of the detected drift, synthesizing new test queries that mimic test queries for the detected drift;

selecting a portion of the new or synthesized test queries to annotate with cardinality labels so as to reduce annotation cost; and

outputting newer predicates and cardinality labels for updating the cardinality estimation model.

15. The computer-readable storage medium of claim 14 , further comprising computer-executable instructions stored thereupon which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

injecting newly arrived predicates into a query pool;

computing embeddings for the newly arrived predicates;

updating a generator and discriminator if synthetic queries are needed; and

updating the embeddings.

16. The computer-readable storage medium of claim 15 , further comprising computer-executable instructions stored thereupon which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

using learned embeddings of query predicates to decouple components from featurizations used by the cardinality estimation model.

17. The computer-readable storage medium of claim 15 , further comprising computer-executable instructions stored thereupon which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

synthesizing new query predicates using predicate embeddings in the query pool.

18. The computer-readable storage medium of claim 15 , further comprising computer-executable instructions stored thereupon which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

receiving a predicate embedding as input and predicting whether a given predicate resembles a training, test, or generated workload.

19. The computer-readable storage medium of claim 14 , wherein the detecting is performed periodically.

20. The computer-readable storage medium of claim 14 , wherein the detecting is performed when an evaluation error of the cardinality estimation model on the test queries exceeds a threshold beyond the error observed during training.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 31, 2022
From: LU, YAO; KANDULA, SRIKANTH; LI, BEIBIN
To: MICROSOFT TECHNOLOGY LICENSING, LLC
Reel/Frame 061595/0495 →
Continuity (1)
Related Publication 20230215150A1 · Jul 6, 2023
References Cited (74)
US 6108648A · Lakshmi · 2000 [cited by examiner]
US 10942923B1 · Zhang · 2021 [cited by examiner]
US 11625398B1 · Bhuyan · 2023 [cited by examiner]
US 11720565B2 · Kalil · 2023 [cited by examiner]
US 20020198867A1 · Lohman · 2002 [cited by examiner]
US 20040128287A1 · Keller · 2004 [cited by examiner]
US 20080306903A1 · Larson · 2008 [cited by examiner]
US 20150248467A1 · Buteau · 2015 [cited by examiner]
US 20160260011A1 · Corvinelli · 2016 [cited by examiner]
US 20170323200A1 · Corvinelli · 2017 [cited by examiner]
US 20180329951A1 · Yu · 2018 [cited by examiner]
US 20180329955A1 · Chaudhuri · 2018 [cited by examiner]
US 20190303475A1 · Jindal · 2019 [cited by examiner]
US 20200379963A1 · Lopes · 2020 [cited by examiner]
US 20210056108A1 · Shmueli · 2021 [cited by examiner]
US 20210089532A1 · Patel · 2021 [cited by examiner]
US 20210263932A1 · Shaffer · 2021 [cited by examiner]
US 20210263935A1 · Hertzschuch · 2021 [cited by examiner]
US 20210406744A1 · Dutt · 2021 [cited by examiner]
US 20220067045A1 · Kalil · 2022 [cited by examiner]
US 20220164346A1 · Mitra · 2022 [cited by examiner]
Halford, Max, Philippe Saint-Pierre, and Franck Morvan. “Selectivity correction with online machine learning.” arXiv preprint arXiv:2009.09884 (2020). [cited by examiner]
Zhu, Rong, et al. “FLAT: fast, lightweight and accurate method for cardinality estimation.” arXiv:2011.09022v5 [cs.DB] May 19, 2021. [cited by examiner]
“International Search Report and Written Opinion Issued in PCT Application No. PCT/US22/051893”, Mailed Date: Mar. 20, 2023, 13 Pages. [cited by applicant]
“TPC-H Vesion 2 and Version 3”, Retrieved from: https://web.archive.org/web/20210415131313/http://tpc.org/tpch/, Apr. 15, 2021, 2 Pages. [cited by applicant]
Bruno, et al., “STHoles: A Multidimensional Workload-Aware Histogram”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, May 21, 2001, pp. 211-222. [cited by applicant]
Chaudhuri, Surajit, “An Overview of Query Optimization in Relational Systems”, In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1, 1998, pp. 34-43. [cited by applicant]
Choi, et al., “Self-ensembling With Gan-based Data Augmentation for Domain Adaptation in Semantic Segmentation”, In Proceedings of the IEEE/CVF International Conference on Computer Vision, Sep. 2, 2019, pp. 6830-6840. [cited by applicant]
Ding, et al., “ALEX: An Updatable Adaptive Learned Index”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, Jun. 14, 2020, pp. 969-984. [cited by applicant]
Ditzler, et al., “Learning in Nonstationary Environments: A Survey”, In Journal of IEEE Computational Intelligence Magazine, vol. 10, Issue 4, Nov. 2015, pp. 12-25. [cited by applicant]
Dutt, et al., “Efficiently approximating selectivity functions using low overhead regression models”, In Proceedings of the VLDB Endowment, vol. 13, Issue 12, Jul. 1, 2020, pp. 2215-2228. [cited by applicant]
Dutt, et al., “Selectivity Estimation for Range Predicates Using Lightweight Models”, In Proceedings of the VLDB Endowment, vol. 12, Issue 9, May 1, 2019, pp. 1044-1057. [cited by applicant]
Fan, et al., “Relational Data Synthesis Using Generative Adversarial Networks: A Design Space Exploration”, In Repository of arXiv:2008.12763v1, Aug. 28, 2020, 20 Pages. [cited by applicant]
Felzenszwalb, et al., “A Discriminatively Trained, Multiscale, Deformable Part Model”, In Proceedings of IEEE conference on computer vision and pattern recognition, Jun. 23, 2008, pp. 1-8. [cited by applicant]
Gama, et al., “A Survey on Concept Drift Adaptation”, In Journal of ACM Computing Surveys, vol. 46, Issue 4, Article 44, Mar. 2014, 37 Pages. [cited by applicant]
Getoor, et al., “Selectivity Estimation using Probabilistic Models”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, May 21, 2001, 12 Pages. [cited by applicant]
Goodfellow, et al., “Deep Learning”, In Publication of MIT Press, Nov. 10, 2016, 802 Pages. [cited by applicant]
Goodfellow, et al., “Generative Adversarial Nets”, In Journal of Advances in Neural Information Processing Systems, vol. 27, Jun. 10, 2014, 9 Pages. [cited by applicant]
Guo, et al., “Long Text Generation via Adversarial Training With Leaked Information”, In Repository of arXiv:1709.08624v1, Sep. 24, 2017, 14 Pages. [cited by applicant]
Haynes, et al., “Visual Road: A Video Data Management Benchmark”, In Proceedings of the International Conference on Management of Data, Jun. 30, 2019, pp. 972-987. [cited by applicant]
Hilprecht, et al., “DeepDB: Learn From Data, Not From Queries!”, In Repository of arXiv:1909.00607v1, Sep. 2, 2019, 13 Pages. [cited by applicant]
Hoffman, et al., “Cycada: Cycle-Consistent Adversarial Domain Adaptation”, In Proceedings of the 35th International Conference on Machine Learning, Jul. 3, 2018, 10 Pages. [cited by applicant]
Hong, et al., “Conditional Generative Adversarial Network for Structured Domain Adaptation”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Dec. 17, 2018, pp. 1335-1344. [cited by applicant]
Zhu, Xiaojin, “Semi-Supervised Learning Literature Survey”, In Technical Report of University of Wisconsin-Madison Department of Computer Sciences, Sep. 7, 2005, 39 Pages. [cited by applicant]
Karras, et al., “A Style-Based Generator Architecture for Generative Adversarial Networks”, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Mar. 29, 2019, pp. 4401-4410. [cited by applicant]
Kipf, et al., “Learned Cardinalities: Estimating Correlated Joins With Deep Learning”, In Repository of arXiv:1809.00677V1, Sep. 3, 2018, 6 Pages. [cited by applicant]
Kraska, et al., “The Case for Learned Index Structures”, In Proceedings of the International Conference on Management of Data, Jun. 10, 2018, pp. 489-504. [cited by applicant]
Krizhevsky, et al., “ImageNet Classification with Deep Convolutional Neural Networks”, In Journal of Advances in Neural Information Processing Systems, vol. 25, Dec. 3, 2012, 9 Pages. [cited by applicant]
Zhang, et al., “Adversarial Feature Matching for Text Generation”, In Proceedings of the 34th International Conference on Machine Learning, vol. 70, Aug. 2017, 10 Pages. [cited by applicant]
Kumar, et al., “Melgan: Generative Adversarial Networks for Conditional Waveform Synthesis”, In Proceedings of 33rd Conference on Neural Information Processing Systems, Dec. 8, 2019, 12 Pages. [cited by applicant]
Li, et al., “Perceptual Generative Adversarial Networks for Small Object Detection.”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Jun. 20, 2017, pp. 1222-1230. [cited by applicant]
Lu, et al., “Accelerating Machine Learning Inference with Probabilistic Predicates”, In Proceedings of the International Conference on Management of Data, Jun. 10, 2018, pp. 1493-1508. [cited by applicant]
Lu, et al., “Recommender System Application Developments: A Survey”, In Journal of Decision Support Systems, vol. 74, Jun. 1, 2015, 38 Pages. [cited by applicant]
Ma, et al., “Active Learning for ML Enhanced Database Systems”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, Jun. 11, 2020, pp. 175-191. [cited by applicant]
Frid-Adar, et al., “GAN-based Synthetic Medical Image Augmentation for Increased CNN Performance in Liver Lesion Classification”, In Journal of Neurocomputing, vol. 321, Dec. 10, 2018, 10 Pages. [cited by applicant]
Manning, et al., “Foundations of statistical natural language processing”, In Publications of MIT Press, May 1999, 353 Pages. [cited by applicant]
Marcus, et al., “Neo: A Learned Query Optimizer”, In Proceedings of the VLDB Endowment, vol. 12, Issue 1, Sep. 2018, pp. 1705-1718. [cited by applicant]
Muller, et al., “Improved selectivity estimation by combining knowledge from sampling and synopses”, In Proceedings of the VLDB Endowment, vol. 11, Issue 9, May 1, 2018, pp. 1016-1028. [cited by applicant]
Nguyen, et al., “Active Learning Using Pre-Clustering”, In Proceedings of The Twenty-First International Conference on Machine Learning, Jul. 4, 2004, 8 Pages. [cited by applicant]
Ratner, et al., “Snorkel: Fast Training Set Generation For Information Extraction”, In Proceedings of the ACM International Conference on Management of Data, May 14, 2017, pp. 1683-1686. [cited by applicant]
Sandfort, et al., “Data Augmentation Using Generative Adversarial Networks (cycleGAN) to Improve Generalizability in CT Segmentation Tasks”, In Journal of Scientific Reports, vol. 9, Issue 1, Nov. 15, 2019, 9 Pages. [cited by applicant]
Fruhwirth-Schnatter, Sylvia , “Data Augmentation and Dynamic Linear Models”, In Journal of Time Series Analysis, Mar. 15, 1994, 18 Pages. [cited by applicant]
Settles, Burr, “Active Learning Literature Survey”, In Technical Report 1648 of Computer Sciences, University of Wisconsin-Madison, Jan. 2009, 67 Pages. [cited by applicant]
Shrivastava, et al., “Training region-based object detectors with online hard example mining”, In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Jun. 27, 2016, pp. 761-769. [cited by applicant]
Simrad, Patricey. , “Best Practices for Convolutional Neural Networks Applied to Visual Document Analysis”, In Proceedings of the Seventh International Conference on Document Analysis and Recognition, Aug. 6, 2003, 6 Pa… [cited by applicant]
Tulyakov, et al., “Mocogan: Decomposing Motion and Content for Video Generation”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Jul. 17, 2017, pp. 1526-1535. [cited by applicant]
Tzoumas, et al., “Efficiently adapting graphical models for selectivity estimation”, In the Journal of VLDB, vol. 22, Issue 1, Feb. 2013, pp. 3-27. [cited by applicant]
Wang, et al., “Are We Ready for Learned Cardinality Estimation”, In Proceedings of the VLDB Endowment, vol. 14, Sep. 2020, pp. 1640-1654. [cited by applicant]
Wang, et al., “Low-shot learning from imaginary data”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Jun. 18, 2018, pp. 7278-7286. [cited by applicant]
Wold, et al., “Principal component analysis”, In Journal of Chemometrics and intelligent laboratory systems, vol. 2, Issue 1-3, Aug. 1987, pp. 37-52. [cited by applicant]
Yan, et al., “Fast Approximate Spectral Clustering”, In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jun. 28, 2009, pp. 907-916. [cited by applicant]
Yang, et al., “Deep Unsupervised Cardinality Estimation”, In Proceedings of the VLDB Endowment, vol. 13, No. 1, Sep. 2019, pp. 279-292. [cited by applicant]
Yu, et al., “Automatic Speech Recognition”, In Publication of Springer, 2016, 330 Pages. [cited by applicant]
International Preliminary Report on Patentability received for PCT Application No. PCT/US2022/051893, Jul. 11, 2024, 08 pages. [cited by applicant]