IP Library › Granted Patent US 12,632,422
Granted Patent B2
US 12,632,422 · App. 17/324,914 · Granted May 19, 2026

Implementation of data access metrics for automated physical database design

Inventors: Michael Brendle (Leimen, DE); Norman May (Karlsruhe, DE); Robert Schulze (Dresden, DE); Alexander Boehm (Schwetzingen, DE); Guido Moerkotte (Schriesheim, DE); Michael Grossniklaus (Kreuzlingen, CH)
Assignee: SAP SE
G06F16/21G06F11/3414G06F11/3428G06F16/213G06F16/215G06F16/217G06F16/2272G06F16/2282G06F16/24545G06F16/2455G06F16/24552G06F16/24575H03M7/6064
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,632,422
App. No.
17/324,914
Filed
May 19, 2021
Granted
May 19, 2026
Kind
B2
Art Unit
2164
USPC
707/803
Abstract

The present disclosure involves systems, software, and computer implemented methods for improved design and implementation of data access metrics for automated physical database design. An example method includes identifying a database workload for which index advisor access counters are to be tracked. Each SQL statement in the database workload is executed. For each SQL statement, attribute sets are determined for which a selection predicate filters a result for an SQL statement. An output cardinality of each selection predicate is determined. A logarithmic counter for an attribute set corresponding to the selection predicate is determined based on the output cardinality of the selection predicate. The determined logarithmic counter is incremented. Respective values for logarithmic counters of the determined attributes are provided to an index advisor. The index advisor determines attribute sets for which to propose an index based on the logarithmic counters of the respective attribute sets.

Claims (60)

1 . A computer-implemented method comprising:

identifying a database workload for which attribute value access counters are to be tracked, wherein the database workload includes at least one SQL (Structured Query Language) statement;

executing each SQL statement in the database workload, wherein executing a respective SQL statement comprises:

determining attribute values of attributes that are accessed when executing the SQL statement; and

for each attribute for which at least one attribute value is accessed:

maintaining value range counters for the attribute that track counts of attribute value accesses within respective value ranges;

maintaining a stream-summary data structure for the attribute that estimates access frequencies of most frequently accessed attribute values of the attribute; and

determining estimated access frequencies for the attribute values of the attribute using both the value range counters for the attribute and the stream summary data structure for the attribute; and

providing the estimated access frequencies for the attribute values of the attributes to a table partitioning advisor, as the attribute value access counters.

2 . The computer-implemented method of claim 1 , wherein the stream-summary data structure for the attribute includes estimated access frequencies for a predetermined number of most frequently accessed attribute values for the attribute.

3 . The computer-implemented method of claim 1 , wherein maintaining value range counters for the attribute comprises, for a first access of a first attribute value of a first attribute:

determining a first value range for the first attribute that includes the first attribute value, from among a collection of value ranges for the first attribute; and

incrementing a first value range counter for the first value range, in response to the first access of the first attribute value.

4 . The computer-implemented method of claim 3 , wherein each value range in the collection of value ranges for the first attribute has a predefined value range size that indicates how many attribute values of a domain of attribute values for the first attribute are included in each value range.

5 . The computer-implemented method of claim 4 , wherein determining estimated access frequencies for the attribute values of the attribute using the value range counters for the attribute and the stream summary data structure for the attribute comprises determining, for each of the attribute values of the attribute in the stream-summary data structure, whether the estimated access frequency of the attribute value in the stream-summary data structure is a valid estimated access frequency of a most frequently accessed attribute value.

6 . The computer-implemented method of claim 5 , wherein determining whether the estimated access frequency of the attribute value in the stream-summary data structure is a valid estimated access frequency of a most frequently accessed attribute value comprises determining whether the estimated access frequency of the attribute value in the stream-summary data structure is significantly larger than a corresponding value range counter for the attribute value in the stream-summary data structure.

7 . The computer-implemented method of claim 6 , wherein determining whether the estimated access frequency of the attribute value in the stream-summary data structure is significantly larger than corresponding value range counter for the attribute value in the stream-summary data structure comprises determining whether the estimated access frequency of the attribute value in the stream-summary data structure is larger than a product of the corresponding value range counter for the attribute value in the stream-summary data structure and a predetermined tolerance parameter.

8 . The computer-implemented method of claim 5 , wherein determining estimated access frequencies for the attribute values of the attribute using the value range counters for the attribute and the stream summary data structure for the attribute comprises determining whether a first value range includes an attribute value with a valid estimated access frequency of a most frequently accessed attribute value in the stream summary data structure.

9 . The computer-implemented method of claim 8 , further comprising, in response to determining that the first value range does not include an attribute value with a valid estimated access frequency of a most frequently accessed attribute value in the stream summary data structure:

for each attribute value in the first value range:

determining an estimated access frequency of the attribute value in the first value range by dividing a first value range counter of the first value range by the predetermined value range size.

10 . The computer-implemented method of claim 8 , further comprising, in response to determining that the first value range includes a first attribute value with a valid estimated access frequency of a most frequently accessed attribute value in the stream summary data structure:

determining an adjusted value range counter for the first value range by subtracting the valid estimated access frequency of the first attribute value from a value range counter for the first value range;

for each attribute value in the first value range other than the first value:

determining an estimated access frequency of the attribute value in the first value range by dividing the adjusted value range counter by the predetermined value range size; and

determining that an estimated access frequency of the first attribute value is equal to the valid estimated access frequency of the first attribute value.

11 . The computer-implemented method of claim 4 , further comprising:

determining value-range based frequency estimates for the attribute values that are included in the first value range; and

providing the value-range based frequency estimates to the table partitioning advisor as the attribute value access counters for the attribute values that are included in the first value range.

12 . The computer-implemented method of claim 10 , wherein determining value-range based frequency estimates for the attribute values that are included in the first value range comprises dividing the first value range counter by the predetermined value range size.

13 . The computer-implemented method of claim 1 , wherein the table partitioning advisor determines one or more table partitioning criteria based on the estimated access frequencies for the attribute values of the attributes.

14 . A system comprising:

one or more computers; and

a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

identifying a database workload for which attribute value access counters are to be tracked, wherein the database workload includes at least one SQL (Structured Query Language) statement;

executing each SQL statement in the database workload, wherein executing a respective SQL statement comprises:

determining attribute values of attributes that are accessed when executing the SQL statement; and

for each attribute for which at least one attribute value is accessed:

maintaining value range counters for the attribute that track counts of attribute value accesses within respective value ranges;

maintaining a stream-summary data structure for the attribute that estimates access frequencies of most frequently accessed attribute values of the attribute; and

determining estimated access frequencies for the attribute values of the attribute using both the value range counters for the attribute and the stream summary data structure for the attribute; and

providing the estimated access frequencies for the attribute values of the attributes to a table partitioning advisor, as the attribute value access counters.

15 . The system of claim 14 , wherein the stream-summary data structure for the attribute includes estimated access frequencies for a predetermined number of most frequently accessed attribute values for the attribute.

16 . The system of claim 14 , wherein maintaining value range counters for the attribute comprises, for a first access of a first attribute value of a first attribute:

determining a first value range for the first attribute that includes the first attribute value, from among a collection of value ranges for the first attribute; and

incrementing a first value range counter for the first value range, in response to the first access of the first attribute value.

17 . The system of claim 16 , wherein each value range in the collection of value ranges for the first attribute has a predefined value range size that indicates how many attribute values of a domain of attribute values for the first attribute are included in each value range.

18 . A computer program product encoded on a non-transitory storage medium, the product comprising non-transitory, computer readable instructions for causing one or more processors to perform operations comprising:

identifying a database workload for which attribute value access counters are to be tracked, wherein the database workload includes at least one SQL (Structured Query Language) statement;

executing each SQL statement in the database workload, wherein executing a respective SQL statement comprises:

determining attribute values of attributes that are accessed when executing the SQL statement; and

for each attribute for which at least one attribute value is accessed:

maintaining value range counters for the attribute that track counts of attribute value accesses within respective value ranges;

maintaining a stream-summary data structure for the attribute that estimates access frequencies of most frequently accessed attribute values of the attribute; and

determining estimated access frequencies for the attribute values of the attribute using both the value range counters for the attribute and the stream summary data structure for the attribute; and

providing the estimated access frequencies for the attribute values of the attributes to a table partitioning advisor, as the attribute value access counters.

19 . The computer program product of claim 18 , wherein the stream-summary data structure for the attribute includes estimated access frequencies for a predetermined number of most frequently accessed attribute values for the attribute.

20 . The computer program product of claim 18 , wherein maintaining value range counters for the attribute comprises, for a first access of a first attribute value of a first attribute:

determining a first value range for the first attribute that includes the first attribute value, from among a collection of value ranges for the first attribute; and

incrementing a first value range counter for the first value range, in response to the first access of the first attribute value.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 20, 2021
From: BRENDLE, MICHAEL; MAY, NORMAN; SCHULZE, ROBERT; BOEHM, ALEXANDER; MOERKOTTE, GUIDO; GROSSNIKLAUS, MICHAEL
To: SAP SE
Reel/Frame 056304/0481 →
Continuity (3)
Continuation 17316901 · May 11, 2021
Provisional Application 63153214 · Feb 24, 2021
Related Publication 20220269653A1 · Aug 25, 2022
References Cited (116)
US 8935205B2 · Hildenbrand et al. · 2015 [cited by applicant]
US 9152626B2 · Seufert et al. · 2015 [cited by applicant]
US 9189520B2 · May et al. · 2015 [cited by applicant]
US 9329899B2 · Ailamaki et al. · 2016 [cited by applicant]
US 9361273B2 · Dannecker et al. · 2016 [cited by applicant]
US 9378233B2 · Lee et al. · 2016 [cited by applicant]
US 9454571B2 · Grosse et al. · 2016 [cited by applicant]
US 9483513B2 · Heidel et al. · 2016 [cited by applicant]
US 9720942B2 · Kaufmann et al. · 2017 [cited by applicant]
US 9747313B2 · Kaufmann et al. · 2017 [cited by applicant]
US 10061808B2 · Kim et al. · 2018 [cited by applicant]
US 10140326B2 · Sherkat et al. · 2018 [cited by applicant]
US 10185744B2 · Bensberg et al. · 2019 [cited by applicant]
US 10248688B2 · Grosse et al. · 2019 [cited by applicant]
US 10261950B2 · Lee et al. · 2019 [cited by applicant]
US 10275508B2 · Bensberg et al. · 2019 [cited by applicant]
US 10282351B2 · Bensberg et al. · 2019 [cited by applicant]
US 10353895B2 · Park et al. · 2019 [cited by applicant]
US 10387127B2 · Hassan · 2019 [cited by applicant]
US 10482085B2 · Moerkotte et al. · 2019 [cited by applicant]
US 10496656B2 · Gaumnitz et al. · 2019 [cited by applicant]
US 10534775B2 · Moerkotte et al. · 2020 [cited by applicant]
US 10545974B2 · Brunel et al. · 2020 [cited by applicant]
US 10592509B2 · Ziegler et al. · 2020 [cited by applicant]
US 10671625B2 · Schulze et al. · 2020 [cited by applicant]
US 10713284B2 · Bensberg et al. · 2020 [cited by applicant]
US 10733185B2 · Psaropoulos et al. · 2020 [cited by applicant]
US 10762071B2 · Schulze et al. · 2020 [cited by applicant]
US 10776353B2 · Schulze et al. · 2020 [cited by applicant]
US 10824673B2 · Rebholz et al. · 2020 [cited by applicant]
US 10872086B2 · Moerkotte et al. · 2020 [cited by applicant]
US 10877956B2 · Park et al. · 2020 [cited by applicant]
US 10885062B2 · Andrei et al. · 2021 [cited by applicant]
US 10891234B2 · Noll et al. · 2021 [cited by applicant]
US 10990427B2 · Kroll et al. · 2021 [cited by applicant]
US 11550762B2 · Brendle et al. · 2023 [cited by applicant]
US 20050203933A1 · Chaudhuri et al. · 2005 [cited by applicant]
US 20050223026A1 · Chaudhuri et al. · 2005 [cited by applicant]
US 20060074872A1 · Gordon · 2006 [cited by applicant]
US 20080071939A1 · Tanaka · 2008 [cited by examiner]
US 20080307009A1 · Anderson et al. · 2008 [cited by applicant]
US 20090077302A1 · Fukuda · 2009 [cited by applicant]
US 20090193042A1 · Hornibrook et al. · 2009 [cited by applicant]
US 20090235252A1 · Weber et al. · 2009 [cited by applicant]
US 20100257151A1 · Lohman et al. · 2010 [cited by applicant]
US 20130204879A1 · Zeng et al. · 2013 [cited by applicant]
US 20140114728A1 · Kaufmann et al. · 2014 [cited by applicant]
US 20140149357A1 · Gupta · 2014 [cited by examiner]
US 20160012089A1 · Sherkat et al. · 2016 [cited by applicant]
US 20160042039A1 · Kaufmann et al. · 2016 [cited by applicant]
US 20160188710A1 · Naik · 2016 [cited by applicant]
US 20160224241A1 · Verrilli et al. · 2016 [cited by applicant]
US 20170017674A1 · Scheuer et al. · 2017 [cited by applicant]
US 20170031967A1 · Chavan · 2017 [cited by examiner]
US 20170031975A1 · Mishra et al. · 2017 [cited by applicant]
US 20170039232A1 · Jayanth et al. · 2017 [cited by applicant]
US 20170075832A1 · Bhimani · 2017 [cited by examiner]
US 20180011892A1 · Kimura · 2018 [cited by applicant]
US 20180024821A1 · Hassan · 2018 [cited by applicant]
US 20180088853A1 · Kotra et al. · 2018 [cited by applicant]
US 20180096006A1 · Das et al. · 2018 [cited by applicant]
US 20180329974A1 · Bensberg et al. · 2018 [cited by applicant]
US 20180357291A1 · Choi et al. · 2018 [cited by applicant]
US 20190130001A1 · May et al. · 2019 [cited by applicant]
US 20190243816A1 · Gaumnitz et al. · 2019 [cited by applicant]
US 20190266272A1 · Wolf et al. · 2019 [cited by applicant]
US 20190271784A1 · Teigland · 2019 [cited by examiner]
US 20190278608A1 · Psaropoulos et al. · 2019 [cited by applicant]
US 20190370257A1 · Wolf et al. · 2019 [cited by applicant]
US 20200026560A1 · Singh et al. · 2020 [cited by applicant]
US 20200117648A1 · Gaumnitz et al. · 2020 [cited by applicant]
US 20200192884A1 · Bao et al. · 2020 [cited by applicant]
US 20200233661A1 · Grosse et al. · 2020 [cited by applicant]
US 20200250167A1 · Brunel et al. · 2020 [cited by applicant]
US 20200387495A1 · Pathak et al. · 2020 [cited by applicant]
US 20200401405A1 · Lasch et al. · 2020 [cited by applicant]
US 20200401530A1 · Abulila et al. · 2020 [cited by applicant]
US 20200403633A1 · Lasch et al. · 2020 [cited by applicant]
US 20220269658A1 · Brendle et al. · 2022 [cited by applicant]
US 20220269684A1 · Brendle et al. · 2022 [cited by applicant]
Extended European Search Report issued in European Application No. 22157240.7 on Aug. 9, 2022, 10 pages. [cited by applicant]
U.S. Appl. No. 16/739,352, Noll et al. [cited by applicant]
U.S. Appl. No. 17/316,901, Brendle et al. [cited by applicant]
U.S. Appl. No. 17/324,874, Brendle et al. [cited by applicant]
U.S. Appl. No. 17/324,896, Brendle et al. [cited by applicant]
Agrawal et al., “Database tuning advisor for microsoft sql server 2005.” Proceedings of the 2005 ACM SIGMOD international conference on Management of data, Jun. 2005, 12 pages. [cited by applicant]
Athanassoulis et al., “Optimal column layout for hybrid workloads.” Proceedings of the VLDB Endowment 12.13, Sep. 2019, 2393-2407, 15 pages. [cited by applicant]
Boncz et al., “JCC-H: adding join crossing correlations with skew to TPC-H.” Technology Conference on Performance Evaluation and Benchmarking. Springer, Cham, Aug. 2017, 17 pages. [cited by applicant]
Curino et al., “Schism: a workload-driven approach to database replication and partitioning.” Proceedings of the VLDB Endowment vol. 3, No. 1, 2010, 10 pages. [cited by applicant]
Damme et al., “From a comprehensive experimental survey to a cost-based selection strategy for lightweight integer compression algorithms.” ACM Transactions on Database Systems (TODS) 44.3, Jun. 2019, 46 pages. [cited by applicant]
Das et al., “Automated demand-driven resource scaling in relational database-as-a-service.” Proceedings of the 2016 International Conference on Management of Data, Jun. 2016, 12 pages. [cited by applicant]
Funke et al., “Compacting transactional data in hybrid OLTP & OLAP databases.” Proceedings of the VLDB Endowment vol. 5, No. 11, Aug. 2012, 12 pages. [cited by applicant]
Gurajada et al., “Btrim: hybrid in-memory database architecture for extreme transaction processing in vldbs.” Proceedings of the VLDB Endowment 11.12, Aug. 2018, 1889-1901, 13 pages. [cited by applicant]
Huang et al., “X-Engine: An optimized storage engine for large-scale E-commerce transaction processing.” Proceedings of the 2019 International Conference on Management of Data, Jun. 2019, 15 pages. [cited by applicant]
Kester et al., “Access path selection in main-memory optimized data systems: Should I scan or should I probe?” Proceedings of the 2017 ACM International Conference on Management of Data, May 2017, 16 pages. [cited by applicant]
Kossmann et al., “Magic mirror in my hand, which is the best in the land? an experimental evaluation of index selection algorithms.” Proceedings of the VLDB Endowment 13.12, Jul. 2020, 2382-2395, 14 pages. [cited by applicant]
Leis et al., “How good are query optimizers, really?. ” Proceedings of the VLDB Endowment 9.3, Nov. 2015, 204-215, 12 pages. [cited by applicant]
Lemke et al., “Speeding up queries in column stores: a case for compression.” DaWaK, 2010, 117-129, 13 pages. [cited by applicant]
Levandoski et al., “Identifying hot and cold data in main-memory databases.” 2013 IEEE 29th International Conference on Data Engineering (Icde). IEEE, Apr. 2013, 12 pages. [cited by applicant]
Lu et al., “Speedup your analytics: Automatic parameter tuning for databases and big data systems.” Proceedings of the VLDB Endowment, Aug. 2019, 4 pages. [cited by applicant]
May et al., “SAP HANA—The evolution of an in-memory DBMS from Pure OLAP processing towards mixed workloads.” Datenbanksysteme für Business, Technologie und Web, BTW, 2017, 19 pages. [cited by applicant]
Metwally et al., “Efficient computation of frequent and top-k elements in data streams.” International conference on database theory. Springer, Berlin, Heidelberg, Jan. 2005, 21 pages. [cited by applicant]
Nathan et al., “Learning multi-dimensional indexes.” Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Jun. 2020, 16 pages. [cited by applicant]
Noll et al., “Analyzing memory accesses with modern processors.” Proceedings of the 16th International Workshop on Data Management on New Hardware, Jun. 2020, 9 pages. [cited by applicant]
Rao et al., “Automating physical database design in a parallel database.” Proceedings of the 2002 Acm Sigmod international conference on Management of data, Jun. 2002, 12 pages. [cited by applicant]
Serafini et al., “Clay: Fine-grained adaptive partitioning for general database schemas.” Proceedings of the VLDB Endowment 10.4, Nov. 2016, 445-456, 12 pages. [cited by applicant]
Sherkat et al., “Native store extension for SAP HANA.” Proceedings of the VLDB Endowment 12.12, Aug. 2019, 2047-2058, 12 pages. [cited by applicant]
Storm et al., “Adaptive self-tuning memory in DB2.” Proceedings of the 32nd international conference on Very large data bases, Sep. 2006, 12 pages. [cited by applicant]
TPC, Transaction Processing Performance Council. “TPC Benchmarktm E. Revision 2.18.0”, 2018, 138 pages. [cited by applicant]
Non-Final Office Action in U.S. Appl. No. 17/324,874, dated Jun. 6, 2023, 35 pages. [cited by applicant]
Non-Final Office Action in U.S. Appl. No. 17/324,896, dated Oct. 6, 2022, 30 pages. [cited by applicant]
Final Office Action in U.S. Appl. No. 17/324,896, dated Jan. 26, 2023, 26 pages. [cited by applicant]
Final Office Action in U.S. Appl. No. 17/324,874, mailed on Dec. 14, 2023, 35 pages. [cited by applicant]
Final Office Action in U.S. Appl. No. 17/324,874, mailed on Sep. 19, 2024, 34 pages. [cited by applicant]
Non-Final Office Action in U.S. Appl. No. 17/324,874, mailed on Apr. 25, 2024, 30 pages. [cited by applicant]
Non-Final Office Action in U.S. Appl. No. 17/324,874, mailed on May 6, 2025, 17 pages. [cited by applicant]