US 9,063,982 B2
`(10) Patent No.:
`az) United States Patent
`Bestgen etal.
`(45) Date of Patent:
`*Jun. 23, 2015
`
`
`US009063982B2
`
`(54) DYNAMICALLY ASSOCIATING DIFFERENT
`QUERY EXECUTION STRATEGIES WITH
`SELECTIVE PORTIONS OF A DATABASE
`TABLE
`
`(71)
`
`(72)
`
`Applicant: International Business Machines
`Corporation, Armonk, NY (US)
`
`Inventors: Robert Joseph Bestgen, Dodge Center,
`MN(US); Shantan Kethireddy,
`Chicago, IL (US); Jeffrey Wayne
`Tenner, Rochester, MN (US)
`
`(73)
`
`Assignee:
`
`International Business Machines
`Corporation, Armonk, NY (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`This patent is subject to a terminal dis-
`claimer.
`
`(21)
`
`(22)
`
`(65)
`
`(63)
`
`(51)
`
`(52)
`
`(58)
`
`Appl. No.: 13/748,670
`Filed:
`Jan. 24, 2013
`
`Prior Publication Data
`US 2013/0132405 Al
`May23, 2013
`
`Related U.S. Application Data
`
`Continuation of application No. 11/181,713, filed on
`Jul. 14, 2005, now Pat. No. 8,386,463.
`Int. Cl
`GO6F 11/30
`GO06F 1730
`US.Cl
`CPC ..... GO6F 17/3053 (2013.01); GO6FCols.OD
`
`Field of Classification Search
`USPC loci ceeescreescnecesescneseneneseecneees 707/713, 719
`See application file for complete search history.
`
`,
`
`(2006.01)
`(2006.01)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,404,510 A
`5,590,319 A
`5,668,987 A
`5,819,255 A
`5,822,747 A
`5,924,094 A
`
`4/1995 Smith etal.
`12/1996 Cohen etal.
`9/1997 Schneider
`10/1998 Celiset al.
`10/1998 Graefe et al.
`7/1999 Sutter
`(Continued)
`
`OTHER PUBLICATIONS
`
`D. Chatziantoniouetal., “Groupwise Processing of Relational Que-
`ries”, Proceedings of the 23rd VLDB Conference (1997).
`(Continued)
`
`Primary Examiner — Sherief Badawi
` 455!S¢ant Examiner — Sabana S Rahman
`(74) Attorney, Agent, or Firm — Roy W. Truelson
`
`ABSTRACT
`(57)
`Aquery facility for database queries dynamically determines
`whether selective portions of a database table are likely to
`benefit from separate query execution strategies, and con-
`structs an appropriate separate execution strategies accord-
`ingly. Preferably, the database containsat least onerelatively
`large table comprising multiple partitions, each sharing the
`definitional structure of the table and containing a different
`respective discrete subset of the table records. The query
`facility compares metadata for different partitions to deter-
`mine whether sufficiently large differences exist among the
`partitions, and in appropriate cases selects one or more par-
`titions for separate executionstrategies. Preferably, partitions
`:
`:
`at
`are ranked for separate evaluation using a weighting formula
`which takes into account: (a) the numberof indexes for the
`partition, (b) recency ofchangeactivity, and (c) the size ofthe
`
`partition.
`
`17 Claims, 7 Drawing Sheets
`
`
`|_-601
`Genersie Strategy
`for Query x
`Estimate Execution|/602
`Timefor Strategy
`
`
`
`
`
`
`
`
`
`
` 604
`+“ ¥
`Select Partition
`Compute Weighted
`Score
`
`
`Y
`Save Straegy in
`10
`Select Fist L
`
`
`
`Execution Strategy
`Cendidetes
`Bloc
`
`
`Re-Write Query ee"
`Generate Multiple]
`612
`Strategiesfor
` 613
`Respective Fartitions
`x
`Union of Strategies}
`
`
`
`PETITIONERS EX1014
`Page 1
`
`PETITIONERS EX1014
`Page 1
`
`

`

`US 9,063,982 B2
`
`Page 2
`
`2002/0035559 Al
`2002/0049687 Al
`2002/0103793 Al
`2003/0084030 Al
`2004/0122845 Al*
`2004/0249810 Al
`2004/0260684 Al
`2005/0038784 Al
`2005/0097099 Al*
`2005/0160102 Al
`2005/0192937 Al
`2005/0210010 A1*
`2006/0080285 Al
`2006/0101001 Al
`2006/0155679 Al
`2006/0173852 Al
`2006/0212429 Al
`2006/0218123 A1*
`2007/0016432 Al
`2007/0027860 Al
`2007/0061487 Al
`2007/0124276 Al
`2007/0226176 Al
`2008/0033914 Al
`
`3/2002 Croweetal.
`4/2002 Helsperetal.
`8/2002 Kelleret al.
`5/2003 Dayet al.
`6/2004 Lohmanetal. ou. 707/102
`12/2004 Dasetal.
`12/2004 Agrawal etal.
`2/2005 Zait et al.
`5/2005 Kapooretal. we 1707/3
`7/2005 Abdoet al.
`9/2005 Barsnesset al.
`9/2005 Larsonet al. woe 1707/3
`4/2006 Chowdhuri
`5/2006 Lindsayet al.
`7/2006 Kothuri etal.
`8/2006 Bestgenet al.
`9/2006 Brunoetal.
`9/2006 Chowdhuriet al. 0.00.00... 707/2
`1/2007 Piggott et al.
`2/2007 Bestgen etal.
`3/2007 Mooreetal.
`5/2007 Weissman etal.
`9/2007 Bestgen etal.
`2/2008 Chemiacketal.
`
`OTHER PUBLICATIONS
`
`A. Shatdal et al., “Adaptive Parallel Aggregation Algorithms”, Pro-
`ceedings of the 1995 ACM-SIGMOD Conference (May 1995).
`“Using the Design Advisor to migrate from a single-partition to a
`multiple-partition
`database,”
`http://publib.boulder.ibm.com/
`infocenter/db2help/topic/com.ibm.db2.doc/admin/t0011 .
`.
`. (publi-
`cation date unknown).
`Stocker,et al., “Integrating Semi-Join-Reducersinto State-of-the-Art
`Query Processors”, IEEE Computer Society, 2001.
`R. Niemiec, “Oracle9i Introduces List Partitioning”, (Oracle Maga-
`zine Jul/Aug. 2002).
`“Getting to Know Oracle 81, Chapter 2: Oracle8i New Features
`(Oracle Corp. 1999).
`“Event 10128: debug partition elimination”, published at www.
`oracleadvice.com/Tips/partprune.htm (publication date unknown).
`
`* cited by examiner
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`10/1999
`2/2000
`2/2000
`2/2000
`7/2000
`8/2000
`4/2001
`8/2001
`1/2002
`2/2002
`10/2002
`5/2003
`5/2003
`6/2003
`8/2003
`9/2003
`11/2003
`2/2004
`6/2004
`7/2004
`8/2004
`9/2004
`11/2004
`8/2005
`10/2005
`3/2006
`7/2006
`9/2006
`10/2006
`11/2006
`12/2006
`1/2007
`2/2007
`2/2007
`11/2007
`4/2008
`7/2008
`6/2010
`2/2013
`
`Waclawsky et al.
`Celis et al.
`Osbornet al.
`Leungetal.
`Lohman etal.
`Lohman etal.
`Chaudhuriet al.
`Subramanian etal.
`Cochraneetal.
`Lohman et al. occ V1
`Marusak
`Koskas
`Popaetal.
`Ziauddin et al.
`Cazemier etal.
`Andrei
`Getchius et al.
`MacNicolet al.
`Bestgenet al.
`Lohman etal.
`Fernandezetal.
`Kapooret al.
`Cotneretal.
`Gibsonetal.
`Zaitet al.
`Cruanesetal.
`Bourbonnaiset al.
`Gupta et al nee V1
`Barsnesset al.
`Bossman etal.
`Gatto
`Kapooret al.
`Witkowski et al.
`Malloyetal.
`Basuetal.
`Agrawalet al.
`Brownetal.
`Andersonet al.
`Bestgenet al.
`
`AAAAAAB
`
`l
`Bl
`Bl
`Bl
`Bl
`B2
`Bl
`Bl
`Bl
`Bl
`Bl
`B2
`B2
`B2
`Bl
`Bl
`Bl
`B2
`Bl
`Bl
`B2
`Bl
`
`5,974,457
`6,021,405
`6,026,391
`6,032,143
`6,092,062
`6,112,198
`6,223,171
`6,275,818
`6,339,769
`6,345,267
`6,470,335
`6,564,212
`6,567,802
`6,581,055
`6,609,123
`6,618,719
`6,643,640
`6,691,101
`6,754,652
`6,763,359
`6,785,673
`6,789,071
`6,816,874
`6,931,401
`6,957,225
`7,020,661
`7,076,508
`7,111,020
`7,130,838
`7,139,749
`7,149,716
`7,171,399
`7,177,855
`7,181,450
`7,299,239
`7,366,716
`7,395,537
`7,734,615
`8,386,463
`
`PETITIONERS EX1014
`Page 2
`
`PETITIONERS EX1014
`Page 2
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet1 of 7
`
`US 9,063,982 B2
`
`100N
`
`104
`
`102
`
`CPU
`
`MEMORY
`
`411
`
`112
`
`143
`
`114
`
`
`
`TERMINAL
`VF
`
`121
`
`STORAGE
`VF
`
`VO DEVICE
`VF
`
`NETWORK
`VF
`
`=
`(mm
`
`=O
`
`a
`
`123
`
`424
`
`2
`
`125
`
`<>
`
`peat
`
`>
`
`127
`
`
`
`PETITIONERS EX1014
`Page 3
`
`PETITIONERS EX1014
`Page 3
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 2 of 7
`
`US 9,063,982 B2
`
`
`
`12
`
`Query Optimizer
`
`213
`
`Query Engine
`
`OS Kernel
`
`|I
`
`II|I|II|II|II|I|II|II|II|II|I|II|4
`
`User App A
`
`User App B
`
`Database
`Management
`System
`
`FIG. 2
`
`PETITIONERS EX1014
`Page 4
`
`PETITIONERS EX1014
`Page 4
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 3 of 7
`
`US 9,063,982 B2
`
`yo
`
`303
`
`304
`
`305
`
`
`Val1A Val1B|ee Val1X
`
`
`Val2A Val2B|ae Val2X
`
`302—>
`
`301A
`
`
`
`301B VaIMA|VaIMB pe|VaIMx
`
`VaINA|VaINB|ee|VaINX
`Val(N+1)A|Val(N+1)B pee Val(N+1)X
`
`Val(L+1)A|Val(L+1)B fae|Val(L+1)X
`
`
`
`301C
`
`FIG. 3
`
`PETITIONERS EX1014
`Page 5
`
`PETITIONERS EX1014
`Page 5
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 4 of 7
`
`US 9,063,982 B2
`
`Query Data
`
`Query ID
`
`414 Query
`
`401
`
`402
`
`FIG. 4
`
`PETITIONERS EX1014
`Page 6
`
`PETITIONERS EX1014
`Page 6
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 5 of 7
`
`US 9,063,982 B2
`
`Formulate and
`Submit New Query
`
`Existing Query
`
`
`
` Select and Submit
`
`
`Parse Query to
`Create Object
`
`Suitable
`Strategy
`
`
`Strategy
`Exists
`507
`?
`
`
`Look for
`Another Strategy
`
`Generate
`Execution
`
`?
`Strategy Block
`(Fig.6)
`
`
` Select Strategy Execute Query
`
`Per Strategy
`( Fig. 7)
`
`
`
`Return Results
`
`
`
`to Requestor
`
`FIG. 5
`
`PETITIONERS EX1014
`Page 7
`
`PETITIONERS EX1014
`Page 7
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 6 of 7
`
`US 9,063,982 B2
`
`START
`
`Generate Strategy
`for Query
`
`Estimate Execution
`Time for Strategy
`
`601
`
`602
`
`603
`
`Partitions
`
`ov Candidate List
`
`
`
`
` Candidates
`
`More
`Partitions
`?
`
`on List
`2
`
`Y
`Select First L
`Candidates
`
`Re-Write Query
`
`Generate Multiple
`Strategies for
`Respective Partitions
`
`;
`Union of Strategies
`
`Save Strategy in
`Execution Strategy
`Block
`
`614
`
`610
`
`611
`
`612
`
`613
`
`FIG. 6
`
`PETITIONERS EX1014
`Page 8
`
`\
`
`
`
`6
`
`Add to
`
`PETITIONERS EX1014
`Page 8
`
`

`

`U.S. Patent
`
`Jun. 23, 2015
`
`Sheet 7 of 7
`
`US 9,063,982 B2
`
`START
`
`701
`
`Execute Strategy
`Instructions
`
`(Partitioned) Database
`
`Examine Default
`Subset Using Default
`Strategy
`
`Examine Partition A
`Using Partition A
`Strategy
`
`Examine Partition B
`Using Partition B
`Strategy
`
`702
`
`703
`
`704
`
`Examination of
`
`Table ( ETC.)
`
`705
`
`Union Results Sets
`
`Execute Remaining
`Strategy Instructions
`
`707
`
`DONE
`
`FIG. 7
`
`706
`
`PETITIONERS EX1014
`Page 9
`
`PETITIONERS EX1014
`Page 9
`
`

`

`US 9,063,982 B2
`
`1
`DYNAMICALLY ASSOCIATING DIFFERENT
`QUERY EXECUTION STRATEGIES WITH
`SELECTIVE PORTIONS OF A DATABASE
`TABLE
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This is a continuation of U.S. patent application Ser. No.
`11/181,713, filed Jul. 14, 2005, entitled “Method and Appa-
`ratus for Dynamically Associating Different Query Execu-
`tion Strategies with Selective Portions of a Database Table”,
`which is herein incorporated by reference. This application
`claimspriority under 35 U.S.C. §120 of US. patent applica-
`tion Ser. No. 11/181,713, filed Jul. 14, 2005.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to digital data pro-
`cessing, and more particularly to the generation and execu-
`tion of database queries in a digital computer system.
`
`BACKGROUNDOF THE INVENTION
`
`In the latter half of the twentieth century, there began a
`phenomenon knownas the information revolution. While the
`information revolution is a historical development broaderin
`scope than any one event or machine, no single device has
`cometo represent the information revolution more than the
`digital electronic computer. The development of computer
`systems has surely been a revolution. Each year, computer
`systems grow faster, store more data, and provide more appli-
`cations to their users.
`
`A modern computer system typically comprises hardware
`in the form of one or more central processing units (CPU) for
`processing instructions, memory for storing instructions and
`other data, and other supporting hardware necessary to trans-
`fer information, communicate with the external world, and so
`forth. From the standpoint of the computer’s hardware, most
`systems operate in fundamentally the same manner. Proces-
`sors are capable of performing a limited set of very simple
`operations, such as arithmetic,
`logical comparisons, and
`movement of data from one location to another. But each
`
`operation is performed very quickly. Programs whichdirect a
`computer to perform massive numbersofthese simple opera-
`tions give the illusion that the computer is doing something
`sophisticated. What is perceived by the user as a new or
`improved capability of a computer system is made possible
`by performingessentially the sameset of very simple opera-
`tions, but doing it muchfaster. Therefore continuing improve-
`ments to computer systems require that these systems be
`madeeverfaster.
`
`The overall speed at which a computer system performs
`day-to-day tasks (also called “throughput”) can be increased
`by making various improvements to the computer’s hardware
`design, which in one way or another increase the average
`numberof simple operations performedper unit of time. The
`overall speed of the system can also be increased by making
`algorithmic improvements to the system design, and particu-
`larly, to the design of software executing on the system.
`Unlike most hardware improvements, many algorithmic
`improvements to software increase the throughput not by
`increasing the average number of operations executed per
`unit time, but by reducing the total number of operations
`which must be executed to perform a given task.
`Complex systems may be used to support a variety of
`applications, but one commonuseis the maintenanceoflarge
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`databases, from which information may be obtained. Large
`databases usually support some form of database query for
`obtaining information whichis extracted from selected data-
`basefields and records. Such queries can consumesignificant
`system resources, particularly processor resources, and the
`speed at which queries are performed can have a substantial
`influence on the overall system throughput.
`Conceptually, a database may be viewed as one or more
`tables of information, each table having a large number of
`entries (analogous ta rows of a table), each entry having
`multiple respective data fields (analogous to columnsofthe
`table). The function ofa database query is to find all rows, for
`whichthe data in the columns of the row matches someset of
`parameters defined by the query. A query may be as simple as
`matching a single column field to a specified value, but is
`often far more complex, involving multiple field values and
`logical conditions. A query may also involve multiple tables
`(referred to as a “join” query), in which the query findsall sets
`of N rows, one row from each respective one of N tables
`joined by the query, where the data from the columnsof the N
`rows matches someset of query parameters.
`Execution of a query involves retrieving and examining
`records in the database according to somesearchstrategy. For
`any given logical query, not all search strategies are equal.
`Various factors may affect the choice of optimum search
`strategy. One of the factors affecting choice of optimum
`search strategy is the sequential order in which multiple con-
`ditions joined by a logical operator, such as AND or OR,are
`evaluated. The sequential order of evaluation is significant
`becausethefirst evaluated condition is evaluated with respect
`to all the entries in a database table, but a later evaluated
`condition need only be evaluated with respect to some subset
`of records which werenoteliminated from the determination
`
`earlier. Therefore, as a generalrule,it is desirable to evaluate
`those conditions which are most selective (i.¢., eliminate the
`largest number of records from further consideration) first,
`and to evaluate conditions which are less selectivelater.
`Other factors can also affect the choice of optimum execu-
`tion strategy. For example, certain auxiliary database struc-
`tures (sometimescalled metadata) may, ifappropriately used,
`provide shortcuts for evaluating a query. One well known type
`of auxiliary database structure is an index. An index is con-
`ceptually a sorting of entries in a database table according to
`the value of one or more corresponding fields (columns). For
`example, if the database table contains entries about people,
`one ofthe fields may contain a birthdate, and a corresponding
`index containsa sorting of the records by birthdate. Ifa query
`requests the records of all persons born before a particular
`date, the sorted index is used to find the responsive entries,
`without the need to examine each and every entry to deter-
`mine whether there is a match. A well-designed database
`typically contains a respective index for eachfield having an
`ordered value which is likely to be used in queries. Other
`forms of auxiliary database record mayalso be used.
`Some databases employpartitioned tables, which can be
`used to advantage in evaluating certain queries. Partitioning
`meansthat a larger conceptual database table is divided into
`multiple discrete portions (“partitions”), each entry in the
`table being allocated to a respective one of the partitions. A
`partition is usually a discrete data entity, such as a file, but
`contains the samedefinitionalstructure (i.e., numberoffields
`in each entry, type of data in each respective field, etc.) as all
`other partitions of the same table. Partitioning may be per-
`formedfor a variety of reasons, and is usually performed on
`very large tables as a meansof breaking the data into subsets
`of some conveniently workable size. In many cases, records
`are allocated to partitions based on somekey value. If the
`PETITIONERS EX1014
`Page 10
`
`PETITIONERS EX1014
`Page 10
`
`

`

`US 9,063,982 B2
`
`3
`logical conditions of a query are such that it can be known
`that, for a given large table which is partitioned, all entries
`satisfying the query will be contained in some subsetof the
`partitions, then it is not necessary to examine entries in the
`otherpartitions not in the subset, resulting in a considerable
`savings at query execution time.
`large databases typically
`To support database queries,
`include a query engine which executes the queries according
`to some automatically selected search strategy, using the
`known characteristics ofthe database and other factors. Some
`
`large database applications further have query optimizers
`which construct search strategies, and save the query andits
`corresponding searchstrategy for reuse. These strategies may
`include, amongother things, the order in which conditions are
`evaluated and whether an auxiliary data structure such as an
`index will be used. A query optimizeror similar function may
`generate a search strategy for a query based on certain
`assumptions about the use of auxiliary data structures or the
`numberofentries eliminated from consideration by certain
`logical conditions. Where these assumptions are erroneous,
`the resultant query execution strategy may be significantly
`less than optimal.
`Wherea database table involved in a query is divided into
`multiple partitions, the query engine will separately examine
`the records in each applicable partition for satisfaction of the
`query conditions. As explained above, in some cases it may be
`inferred from the query conditions that no records within a
`particular partition or subset of partitions will satisfy the
`query, and in this case the query optimizer may construct the
`query to by-pass examination of these partitions. However,
`among, the examinedpartitions(i.e., those which can not be
`eliminated from examination beforehand based on the known
`query and partition parameters), there may well be differ-
`ences in data distribution, auxiliary structures or other char-
`acteristics which would affect the choice of optimal query
`execution strategy.
`Ifa commonquery execution strategy is constructedforall
`partitions which can not be eliminated from consideration,
`this strategy will typically be based on average or common
`characteristics ofthe partitions. In this case, there is a risk that
`at least some partitions will have characteristics at variance
`with the average, andthat the query execution strategy will be
`sub-optimal for these partitions.
`In order to deal with different data characteristics of dif-
`ferent partitions, it is known to separately analyze and con-
`struct an independent query execution strategy for each par-
`tition. However, construction of an appropriate query
`execution strategy involves considerable analytical overhead.
`The overhead of constructing a separate and independent
`query executionstrategy for each respectivepartition can well
`outweigh the benefits of improved execution efficiency from
`tailoring the executionstrategy to the partition. As the number
`ofpartitions ofa database table grows, this overhead becomes
`increasingly burdensome.
`A need exists for improved techniques for constructing
`query execution strategies against large, partitioned database
`tables. In particular, a need exists, not necessarily recognized,
`for an improved database query engine or optimizer which
`can automatically make intelligent choices in determining
`when to construct separate query execution strategies for
`different subsets of records a database.
`
`SUMMARYOF THE INVENTION
`
`A query engine (or optimizer) which supports database
`queries dynamically determines whether selective portions of
`a database table are likely to benefit from separate query
`
`30
`
`35
`
`40
`
`45
`
`4
`execution strategies, and with respect to any selective portion
`determined likely to benefit from such a separate query
`execution strategy, constructs an appropriate strategy using
`characteristics of the selection portion.
`In the preferred embodiment, a database contains at least
`one relatively large table which is partitioned into multiple
`partitions, each sharing the definitional structure of the table
`and containing a different respective discrete subset of the
`table records. If a query is generated againstdata in thetable,
`a query engine or optimizer compares metadata for different
`partitions to determine whethersufficiently large differences
`exist among the partitions, and in appropriate cases selects
`one or morepartitions for separate evaluation. A separate and
`independent query execution strategy is then constructed for
`each ofthe selected partitions, with a general strategy being
`constructed for the remainingpartitions.
`In the preferred embodiment, partitions are ranked for
`separate evaluation using a weighting formula which takes
`into account: (a) the numberof indexes for the partition, (b)
`recency of changeactivity, and (c) the sizeof the partition,it
`being understood that numerousother factors could addition-
`ally or alternatively be taken into account. If the weighted
`score of one or more partitions exceeds a pre-determined
`threshold, then those partitions having the highest score and
`exceeding the threshold are selected, up to a pre-determined
`selection limit. It is possible that no partitions will be selected,
`or that a numberofpartitions fewer than the selection limit
`will be selected. A separate query strategy is then constructed
`for each selected partition, using the data characteristics of
`the partition.
`A techniquefor selectively identifying partitions for inde-
`pendent query optimization as described herein can be imple-
`mented using very little overhead. By intelligently selecting
`only somepartitions for separate query optimization, the
`overhead of optimizing every partition independently is
`avoided, and separate optimization is performed in those
`fewer but significant cases whereit is likely to make a real
`difference in query execution performance. In thoseselective
`partitions, a separate query executionstrategy, independently
`optimized using the characteristicsofthepartition,is likely to
`provide significant query execution performance improve-
`ments.
`
`The details of the present invention, both asto its structure
`and operation, can best be understood in reference to the
`accompanying drawings, in which like reference numerals
`refer to like parts, and in which:
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`FIG.1 is a high-level block diagram of the major hardware
`components of a computer system for executing database
`queries and dynamically associating different query execu-
`tion strategies with different database portions, according to
`the preferred embodimentof the present invention.
`FIG. 2 is a conceptual illustration of the major software
`components of a computer system for executing database
`queries and dynamically associating different query execu-
`tion strategies with different database portions, according to
`the preferred embodiment.
`FIG. 3 is a conceptual representation of the structure of a
`partitioned database table, according to the preferred embodi-
`ment.
`
`FIG.4 is a conceptual representation of a persistent query
`object, according to the preferred embodiment.
`FIG. 5 is a flow diagram illustrating at a high level the
`process of executing a database query, according to the pre-
`ferred embodiment.
`
`PETITIONERS EX1014
`Page 11
`
`PETITIONERS EX1014
`Page 11
`
`

`

`US 9,063,982 B2
`
`5
`FIG. 6 showsin greater detail the process of generating a
`query execution strategy for a database table having multiple
`partitions, accordingto the preferred embodiment.
`T'1lG. 7 shows in greater detail the process of executing a
`query using an execution strategy which is separately opti-
`mizedfor different partition of a database table, according to
`the preferred embodiment.
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`Referring to the Drawing, wherein like numbers denote
`like parts throughoutthe several views, FIG. 1 is a high-level
`representation of the major hardware components of a com-
`puter system 100 for use in generating and executing database
`queries, dynamically determining whetherdifferent portions
`ofa queried databaseare likely to benefit from different query
`execution strategies, and generating different strategies as
`required by the determination made, according to the pre-
`ferred embodiment of the present invention. CPU 101 is at
`least one general-purpose programmable processor which
`executes instructions and processes data from main memory
`102. Main memory 102 is preferably a random access
`memory using any ofvarious memory technologies, in which
`data is loaded from storage or otherwise for processing by
`CPU 101.
`
`One or more communications buses 105 provide a data
`communication path for transferring data among CPU 101,
`main memory 102 and various I/O interface units 111-114,
`which mayalso be known as I/O processors (IOPs) or I/O
`adapters (IOAs). The I/O interface units support communica-
`tion with a variety of storage and I/O devices. For example,
`terminalinterface unit 111 supports the attachmentof one or
`moreuser terminals 121-124. Storage interface unit 112 sup-
`ports the attachment of one or more direct access storage
`devices (DASD) 125-127 (whichare typically rotating mag-
`netic disk drive storage devices, although they could alterna-
`tively be other devices, including arrays of disk drives con-
`figured to appearas a single large storage device to a host). I/O
`device interface unit 113 supports the attachment of any of
`various other types of I/O devices, such as printer 128 and fax
`machine 129,
`it being understood that other or additional
`types of I/O devices could be used. Network interface 114
`supports a connectionto external network 130 for communi-
`cation with one or more other digital devices. Network 130
`may be any ofvarious local or wide area networks known in
`the art. For example, network 130 may be an Ethernet local
`area network, or it may be the Internet. Additionally, network
`interface 114 might support connection to multiple networks.
`Tt should be understoodthat FIG.1 is intended to depict the
`representative major components of system 100 at a high
`level, that individual components mayhave greater complex-
`ity than represented in FIG.1, that components other than or
`in addition to those shown in FIG. 1 maybepresent, and that
`the number, type and configuration of such components may
`vary, and that a large computer system will typically have
`more components than represented in FIG. 1. Several particu-
`lar examples of such additional complexity or additional
`variations are disclosed herein, it being understoodthat these
`are by way of example only andare not necessarily the only
`such variations.
`
`Although only a single CPU 101 is shownfor illustrative
`purposes in FIG. 1, computer system 100 may contain mul-
`tiple CPUs, as is knownin the art. Although main memory
`102 is shown in FIG.1 as a single monolithic entity, memory
`102 mayin fact be distributed and/or hierarchical, as is known
`in the art. E.g., memory may exist in multiple levels ofcaches,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`and these caches may be further divided by function, so that
`one cacheholdsinstructions while another holds non-instruc-
`
`tion data which is used by the processor or processors.
`Memory mayfurther be distributed and associated with dif-
`ferent CPUsor sets of CPUs, as is known in any of various
`so-called non-uniform memory access (NUMA) computer
`architectures. Although communications buses 105 are
`shown in FIG. 1 as a single entity, in fact communications
`among various system componentsis typically accomplished
`through a complex hierarchy of buses, interfaces, and sa
`forth, in which higher-speed paths are used for communica-
`tions between CPU 101 and memory 102, and lower speed
`paths are used for communications with I/O interface units
`111-114. Buses 105 maybe arrangedin any ofvarious forms,
`such as point-to-point links in hierarchical, star or web con-
`figurations, multiple hierarchical buses, parallel and redun-
`dant paths, etc. For example, as is known in a NUMAarchi-
`tecture, communicationspaths are arranged on a nodal basis.
`Buses may use, e.g., an industry standard PCI bus, or any
`other appropriate bus technology. While multiple I/O inter-
`face units are shown which separate buses 105 from various
`communications paths running to the various I/O devices, it
`would alternatively be possible to connect someorall of the
`I/O devices directly to one or more system buses.
`Computer system 100 depicted in FIG. 1 has multiple
`attached terminals 121-124, such as might be typical of a
`multi-user “mainframe” computer system. Typically, in such
`a case the actual numberof attached devices is greater than
`those shown in FIG.1, although the present invention is not
`limited to systemsofany particular size. User workstations or
`terminals which access computer system 100 might also be
`attached to and communicate with system 100 over network
`130. Computer system 100 mayalternatively be a single-user
`system, typically containing only a single user display and
`keyboard input, or a system such as a server containing, no
`directly attached terminals. Furthermore, while the invention
`herein is describedfor illustrative purposes as embodiedin a
`single computer system,the present invention could alterna-
`tively be implemented using a distributed network of com-
`puter systems in communication with one another, in which
`different functions or steps described herein are performed on
`different computer systems.
`While various system components have been described
`and shown at a high level, it should be understood that a
`typical computer system contains many other components
`not shown, whichare not essential to an understanding of the
`present invention. In the preferred embodiment, computer
`system 100 is acomputer system based on the IBM AS/400™
`or i/Series™architecture, it being understoodthat the present
`invention could be implemented on other computer systems.
`FIG. 2 is a conceptual illustration of the major software
`components of system 100 in memory 102. Operating system
`kernel 201 is executable code andstate data providing various
`low-level software functions, such as device interfaces, man-
`agement of memory pages, managementand dispatching of
`multiple tasks, etc. as is well-knownin the art. A structured
`database 202 contains data which is maintained by computer
`system 100 and for which the system provides access to one
`or more users, who maybe directly attached to system 100 or
`may be remote clients who access system 100 through a
`network using a client/server access protocol.
`Database 202 contains one or more tables 203, 204 (of
`which two are shown in FIG. 2), each having a plurality of
`entries or records, each entry containing at least one (and
`usually many) fields, as is well known in the art. Database
`tables 203, 204 might contain almost any type of data which
`is provided to users by acomputer system. In accordance with
`PETITIONERS EX1014
`Page 12
`
`PETITIONERS EX1014
`Page 12
`
`

`

`US 9,063,982 B2
`
`7
`the preferred embodiment,at least one databasetable (repre-
`sented in FIG. 2 as table 203) comprises multiple partitions,
`each partition containing somediscrete portion ofthe entries
`in table 203. Associated with the database tables are one or
`
`more auxiliary data structures 205-208, also sometimes
`referred to as metadata. Auxiliary data structures characterize
`the structure ofthe database anddata therein, and are useful in
`various tasks involved in database management, particularly
`in executing queries against the database. Examples of aux-
`iliary data structures include database indexes 205-206, mate-
`rialized query table 207, and histogram 208, it being under-
`stood that other types of metadata mayexist.
`Database management system 211 provides basic func-
`tions for the managementof database 202. Database manage-
`ment system 211 maytheoretically support an arbitrary num-
`ber of database tables, which may or may not haverelated
`information, although only two tables are shown in FIG. 2.
`Database managementsystem 211 preferably allowsusers to
`perform basic database operations, such as defining a data-
`base, altering the definition of the database, creating, editing
`and removing recordsin the database, viewing records in the
`database, defining database indexes, and so forth. Among the
`functions supported by database management system 211 is
`the makingofqueries against data in database tables 203, 204.
`Query support functions in database management system 211
`include query optimizer 212 and query engine 213. Database
`management system 211 may further contain any of various
`more advanced database functions. Although data