Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 1 of 49 PageID #: 500
`
`Exhibit K
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 2 of 49 PageID #: 501
`1111111111111111 IIIIII IIIII 11111 1111111111 1111111111 11111 111111111111111 1111111111 11111111
`
`US 20060218123Al
`
`c19) United States
`c12) Patent Application Publication
`Chowdhuri et al.
`
`c10) Pub. No.: US 2006/0218123 Al
`Sep. 28, 2006
`(43) Pub. Date:
`
`(54) SYSTEM AND METHODOLOGY FOR
`PARALLEL QUERY OP TIMIZATION USING
`SEMANTIC-BASED PARTITIONING
`
`(51)
`
`Int. Cl.
`
`Publication Classification
`
`(75)
`
`Inventors: Sudipto R. Chowdhuri, Dublin, CA
`(US); Mihnea Andrei, Issy !es
`Moulineaux (FR)
`
`Correspondence Address:
`JOHN A. SMART
`708 BLOSSOM HILL RD., #201
`LOS GATOS, CA 95032-3503 (US)
`
`(73) Assignee: SYBASE, INC., Dublin, CA (US)
`
`(21) Appl. No.:
`
`10/908,956
`
`(22) Filed:
`
`Jun. 2, 2005
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/594,310, filed on Mar.
`28, 2005.
`
`200
`
`CLIENT(S)
`210
`
`NETWORK
`220
`
`SQL STM(S)
`
`PC(S) OR
`TERMINAL(S)
`
`211
`
`___.
`
`___,��
`
`________
`
`QUERY
`RESULT(S)
`
`(2006.01)
`G06F 17130
`(52) U.S. Cl. .................................................................. 707/2
`
`(57)
`
`ABSTRACT
`
`A system and methodology for parallel query optimization
`using semantic-based partitioning is described. In one
`embodiment, for example, in a database system comprising
`a database storing data in database tables, a method is
`described for improving query performance by dynamically
`partitioning the data, the method comprises steps of: receiv­
`ing a query requesting data from the database; generating a
`plurality of subplans for executing the query, each subplan
`including one or more operators for performing relational
`operations; adding operators for partitioning data and per­
`forming a given relational operation in parallel to at least
`some of the plurality of subplans; and building a plan for
`execution of the query based, at least in part, upon selecting
`subplans having favorable execution costs
`
`SERVER
`230
`
`ENGINE
`
`J,
`NORMALIZER
`J,
`COMPILER
`OPTIMIZER
`CODE GENERATOR
`J,
`EXECUTION UNIT
`J,
`ACCESS METHODS
`
`260
`
`261
`
`263
`
`265
`
`266
`
`267
`
`269
`
`270
`
`240
`DATABASE SERVER
`SYSTEM
`
`245
`
`250
`
`255
`
`Cloudera Exhibit 1003 - Page 1 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 3 of 49 PageID #: 502
`
`Patent Application Publication Sep. 28, 2006 Sheet 1 of 21
`
`
`
`
`
`
`
`
`
`(s)|LINn
`
`| || ||
`
`Cloudera Exhibit 1003 - Page 2 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 4 of 49 PageID #: 503
`
`Cloudera Exhibit 1003 - Page 3 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 5 of 49 PageID #: 504
`
`Patent Application Publication Sep. 28, 2006 Sheet 3 of 21
`
`US 2006/0218123 A1
`
`SORT
`
`GROUPBY
`
`305
`
`-
`
`303
`
`HASHJOIN
`
`-
`
`301 Y
`
`SCAN
`
`SCAN
`
`3O8
`
`t
`
`- so
`
`309
`
`DATA
`
`DATA
`
`FIG. 3A
`
`Cloudera Exhibit 1003 - Page 4 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 6 of 49 PageID #: 505
`
`Cloudera Exhibit 1003 - Page 5 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 7 of 49 PageID #: 506
`
`Patent Application Publication Sep. 28, 2006 Sheet 5 of 21
`
`US 2006/0218123 A1
`
`400
`
`4O6
`
`
`
`GROUP BY
`
`TABLE A
`
`
`
`456
`
`
`
`
`
`GROUP BY
`454a
`
`GROUP BY
`454b
`
`GROUP BY
`454d
`
`GROUP BY
`454C
`
`453
`
`Xchg
`(Partition)
`
`- -21 P H(A1)
`
`
`
`
`
`451
`
`Cloudera Exhibit 1003 - Page 6 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 8 of 49 PageID #: 507
`
`Patent Application Publication Sep. 28, 2006 Sheet 6 of 21
`
`US 2006/0218123 A1
`
`
`
`
`
`504
`
`SCALARAGG
`
`TABLE A
`
`FIG. 5A
`550
`
`557
`
`556
`
`555
`
`SCALARAGG
`554b
`
`SCALARAGG SCALARAGG
`554
`554d
`C
`
`
`
`553
`
`SCALARAGG
`554a
`
`
`
`Xchg
`(Partition)
`
`2- ROUND-ROBIN
`
`
`
`
`
`551
`
`TABLE A
`
`FIG. 5B
`
`Cloudera Exhibit 1003 - Page 7 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 9 of 49 PageID #: 508
`
`Patent Application Publication Sep. 28, 2006 Sheet 7 of 21
`
`US 2006/0218123 A1
`
`6OO
`
`PLAN OR
`SET OF PLANS
`
`610
`
`
`
`SEARCHENGINE
`
`(JOIN ORDERING/OPERATOR
`SELECTION BASED ON
`PARTITIONING AND MULTI
`DIMENSIONAL COSTING)
`SEMANTIC
`PARTITIONING 615
`
`601
`
`62O
`
`604
`
`PARALLEL
`SCHEDULER
`
`COST BASED
`SCHEDULE
`GENERATION
`
`BEST PLAN
`WITH
`SCHEDULE
`
`
`
`QUERY TREE
`
`CODE GENERATION
`
`FIG. 6
`
`Cloudera Exhibit 1003 - Page 8 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 10 of 49 PageID #: 509
`
`Patent Application Publication Sep. 28, 2006 Sheet 8 of 21
`
`US 2006/0218123 A1
`
`Xchg
`(3 STREAMS)
`
`
`
`
`
`JOIN
`(3 STREAMS)
`
`
`
`us
`
`
`
`Xchg
`(1 TO 3)
`
`
`
`
`
`SCAN B
`(3 STREAMS)
`
`SCANA
`(1 STREAM)
`
`ILLUSTRATES A 1
`TO N SPLIT
`
`FIG. 7A
`
`RidJoin (RID) ON A
`
`Hash Union Distinct
`(RID)
`
`INDEX SCANA
`(a2 = 20)
`
`FIG. 7B
`
`
`
`
`
`
`
`
`
`INDEX SCANA
`(a3 > 34)
`
`
`
`INDEX SCANA
`(a1 < 10)
`
`Cloudera Exhibit 1003 - Page 9 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 11 of 49 PageID #: 510
`
`Patent Application Publication Sep. 28, 2006 Sheet 9 of 21
`
`US 2006/0218123 A1
`
`Xchg: k TOd
`(RID)
`
`INDEX SCANA
`(a3 > 34)
`
`Xchg: dTO 1
`
`RidJoin (RID) ONA
`
`Hash Union Distinct
`(RID)
`
`Xchg: k TOd
`(RID)
`
`NCE s: A
`
`FIG 7C
`
`
`
`
`
`RidJoin (A)
`
`
`
`
`
`
`
`Hash Union Distinct
`
`Xchg k to d
`(RID)
`
`INDEX SCANA
`(a1 < 10)
`
`
`
`SCAN (CACHE KNOWN)
`(10, 20, 30)
`
`SCAN (CACHE
`UNKNOWN) (GW, GW)
`
`FIG. 7D
`
`Cloudera Exhibit 1003 - Page 10 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 12 of 49 PageID #: 511
`
`Patent Application Publication Sep. 28, 2006 Sheet 10 of 21
`
`US 2006/0218123 A1
`
`Xchg (N to 1)
`
`NLJOIN
`
`FIG. 8A
`
`
`
`
`
`INDEX SCAN (B) USING
`IB(b2,b3), PB(b2,b1)
`
`SCANA, PA(a3)
`
`FIG. 8B
`
`
`
`
`
`Xchg (MTO 1)
`
`UPDATE
`
`
`
`NLJOIN (a1 = b 1)
`
`
`
`Repl-Xchg (NTOM)
`
`FIG. 8C
`
`Cloudera Exhibit 1003 - Page 11 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 13 of 49 PageID #: 512
`
`Patent Application Publication Sep. 28, 2006 Sheet 11 of 21
`
`US 2006/0218123 A1
`
`SCAN (A): PA(a3)
`
`
`
`
`
`
`
`INDEX SCAN(B) USING
`IB(b2, b3) and PB1(b4)
`
`Cloudera Exhibit 1003 - Page 12 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 14 of 49 PageID #: 513
`
`Patent Application Publication Sep. 28, 2006 Sheet 12 of 21
`
`US 2006/0218123 A1
`
`N | NOEN
`
`
`
`
`
`
`
`Cloudera Exhibit 1003 - Page 13 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 15 of 49 PageID #: 514
`
`Cloudera Exhibit 1003 - Page 14 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 16 of 49 PageID #: 515
`
`Patent Application Publication Sep. 28, 2006 Sheet 14 of 21
`
`US 2006/0218123 A1
`
`MERGE JOIN 1 (EVEN)
`
`MERGE JOIN 2 (ODD)
`
`
`
`Xchg (SPLIT TO ODD
`AND EVEN)
`
`FIG. 9D
`
`Xchg(1-100)
`
`STREAM 1
`(1-25)
`
`STREAM2
`(26-50)
`
`STREAM 3
`(51-75)
`
`STREAM 4
`(76-100)
`
`FIG. 9E
`
`Cloudera Exhibit 1003 - Page 15 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 17 of 49 PageID #: 516
`
`Patent Application Publication Sep. 28, 2006 Sheet 15 of 21
`
`US 2006/0218123 A1
`
`
`
`Xchg (N to 1)
`/ /
`ASH JON
`
`SCAN (A); PA(a1)
`
`SCAN B, PB(b1)
`
`
`
`
`
`FIG. 1 OA
`
`Xchg (dTO 1)
`
`
`
`HASH JOIN (a1=b1 and
`a2=b2)
`
`
`
`Xchg (a1, a2) (N to D)
`
`Xchg (b1, b2) (M to D)
`
`
`
`
`
`AGGOP SUM
`
`
`
`JOINOP
`
`FIG 10C
`
`Cloudera Exhibit 1003 - Page 16 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 18 of 49 PageID #: 517
`
`Patent Application Publication Sep. 28, 2006 Sheet 16 of 21
`
`US 2006/0218123 A1
`
`
`
`
`
`
`
`
`
`
`
`Aggop SUM
`
`Xchg (NTO 1)
`
`
`
`GroupedAg
`
`FIG 1 OE
`
`
`
`GrpAgg (SUM)
`
`
`
`Xchg(NTO 1)
`
`
`
`GrpAgg(COUNT)
`
`SCAN(NSTREAMS)
`
`FIG 1 OF
`
`Cloudera Exhibit 1003 - Page 17 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 19 of 49 PageID #: 518
`
`Patent Application Publication Sep. 28, 2006 Sheet 17 of 21
`
`US 2006/0218123 A1
`
`
`
`
`
`Xchg(N to 1)
`/N
`STREAMS)
`u-21
`Xchg(PA'(a2, a3)
`
`
`
`M STREAMS)
`
`FIG. 1 1A
`
`
`
`SINGLE STREAM
`
`
`
`/N
`STREAMS)
`u-21
`Xchg(PA'(a2, a3)
`NSTREAMS)
`
`
`
`GroupedAgg
`(MSTREAMS)
`
`
`
`
`
`SCAN(PA(a1)
`M STREAMS)
`
`FIG 11B
`
`Cloudera Exhibit 1003 - Page 18 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 20 of 49 PageID #: 519
`
`Patent Application Publication Sep. 28, 2006 Sheet 18 of 21
`
`US 2006/0218123 A1
`
`FILTER
`
`
`
`Xchg (d - 1)
`
`AggAny(PB'(b3))
`
`
`
`
`
`Hash.Join (a1=b2)
`
`Nested LoopJoin
`
`
`
`SCAN B(PB(b1))
`
`SCAN A(PA(a1))
`
`FIG. 12A
`
`Xchg (dTO 1)
`
`
`
`Hash Union Distinct
`
`
`
`Xchg(NTO d)
`
`Xchg(MTO d)
`
`Xchg(KTO d)
`
`
`
`
`
`FIG. 12B
`
`Cloudera Exhibit 1003 - Page 19 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 21 of 49 PageID #: 520
`
`Patent Application Publication Sep. 28, 2006 Sheet 19 of 21
`
`US 2006/0218123 A1
`
`BEGIN
`
`1300
`
`QUERY IS RECEIVED (E.G., SQL QUERY CONTAINING SELECT
`STATEMENT AND GROUPING ON COLUMNA1 OF TABLEA).
`
`OUERY PARSED AND NORMALIZED AND INTERNAL
`REPRESENTATION OF QUERY (LOGICALOPERATOR TREE)
`GENERATED.
`
`
`
`
`
`SEARCHENGINE LOOKS AT LOGICAL OPERATIONS TO BE DONE
`AND DETERMINES WHAT PARTITIONINGS MIGHT BE USEFUL
`(USEFUL PARTITIONING). FOR EACH OPERATION, SEARCH
`ENGINE LOOKSAT CURRENT PARTITIONING AVAILABLE FOR
`THAT OPERATION AND WHAT PARTITIONING MIGHT BE USEFUL
`FOR THE OPERATION.
`
`SEARCHENGINE STARTS BUILDING PLANS IN BOTTOM-UP
`FASHON STARTING AT BOTTOM OF LOGICAL OPERATOR TREE.
`BUILDS FIRST SUBPLAN (SUBPLAN A) WITH SCANNODE.
`
`SEARCHENGINE BUILDS SECOND SUBPLAN (SUBPLANB)
`INCLUDING SCAN AND Xchg OPERATORS. Xchg PARTITIONS
`DATA INTO MULTIPLE STREAMS (E.G., FOUR STREAMS
`PARTITIONED BASED ON HASHING ON COLUMNA1) AS
`PARTITIONING ON A1 ISPOTENTIALLY USEFUL FOR UPSTREAM
`GROUPING OPERATION ON COLUMN A1
`
`CONTINUE TO FIG. 13B
`v
`FIG. 13A
`
`1302
`
`1303
`
`1304
`
`1305
`
`1306
`
`Cloudera Exhibit 1003 - Page 20 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 22 of 49 PageID #: 521
`
`Patent Application Publication Sep. 28, 2006 Sheet 20 of 21
`
`US 2006/0218123 A1
`
`CONTINUE FROM FIG. 13A
`
`1307
`
`EVALUATE SUBPLANA AND SUBPLAN BTO DETERMINE IF ONE
`CAN BE PRUNED. SUBPLAN B, EVENTHOUGHMORE
`EXPENSIVE, IS RETAINED AS SUBPLAN BHAS"USEFUL
`PARTITIONING." PROPERTY WHICH SUBPLAN A DOES NOT HAVE.
`
`GROUPING OPERATION (GROUP BY) ADDED TO SUBPLAN A.
`
`
`
`GROUPING OPERATION ADDED TO SUBPLAN BBY CLONING
`GROUP BY FOUR WAYS FOR PERFORMING GROUPNG
`OPERATION IN PARALLEL ON FOUR PARTITIONS IN SUBPLANB
`
`EVALUATE SUBPLANA AND SUBPLAN BTO DETERMINE IF ONE
`CAN BE PRUNED. SUBPLAN A, EVENTHOUGHMORE
`EXPENSIVE, IS RETAINED AS SUBPLAN A HAS"USEFUL
`PARTITIONING" DEGREENEEDED UPSTREAM IN PLAN BEING
`CONSTRUCTED.
`
`XCHG OPERATOR ADDED TO SUBPLAN BABOVE GROUPNG
`OPERATION TO MERGE THE FOUR STREAMS (FROMFOUR
`GROUP BY OPERATORS) BACK INTO A SINGLE STREAM.
`
`SUBPLANA AND SUBPLAN B COMPARED TO DETERMINE IF ONE
`CAN BE PRUNED. SUBPLANA AND SUBPLAN B NOW HAVE
`SAME PARTITIONING DEGREE AND SUBPLAN WHICH IS MORE
`EXPENSIVE (E.G., SUBPLANA) IS PRUNED.
`
`1308
`
`1309
`
`131 O
`
`1311
`
`1312
`
`FIG. 13B
`
`Cloudera Exhibit 1003 - Page 21 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 23 of 49 PageID #: 522
`
`Patent Application Publication Sep. 28, 2006 Sheet 21 of 21
`
`US 2006/0218123 A1
`
`14OO
`
`JOIN
`
`1406 "USELESS" 4
`(2)
`-/
`
`RANGE
`
`(1) PUSH-DOWN
`- TO ANY
`1 (2) CHANGE TO
`"USELESS"
`
`1405
`
`/
`/
`
`P.
`
`RANGE 4
`(1)
`
`Jer
`
`1403
`
`N
`
`SCAN
`
`14O4
`
`41
`
`SCAN
`
`14O1
`
`14O2
`
`TABLE A
`
`TABLE B
`
`FIG. 14
`
`Cloudera Exhibit 1003 - Page 22 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 24 of 49 PageID #: 523
`
`US 2006/0218123 A1
`
`Sep. 28, 2006
`
`SYSTEMAND METHODOLOGY FOR PARALLEL
`QUERY OPTIMIZATION USING
`SEMANTIC-BASED PARTITIONING
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`0001. The present application is related to and claims the
`benefit of priority of the following commonly-owned, pres
`ently-pending provisional application(s): application Ser.
`No. 60/594,310 (Docket No. SYB/0120.00), filed Mar. 28,
`2005, entitled “System and Methodology for Parallel Query
`Optimization Using Semantic-Based Partitioning, of which
`the present application is a non-provisional application
`thereof. The present application is related to the following
`commonly-owned, presently-pending application(s): appli
`cation Ser. No. 10/711,931 (Docket No. SYB/0114.00), filed
`Oct. 13, 2004, entitled “Database System with Methodology
`for Parallel Schedule Generation in a Query Optimizer. The
`disclosures of each of the foregoing applications are hereby
`incorporated by reference in their entirety, including any
`appendices or attachments thereof, for all purposes.
`
`COPYRIGHT STATEMENT
`0002 A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`APPENDIX DATA
`0003 Computer Program Listing Appendix under Sec.
`1.52(e): This application includes a transmittal under 37
`C.F.R. Sec. 1.52(e) of a Computer Program Listing Appen
`dix. The Appendix, which comprises text file(s) that are
`IBM-PC machine and Microsoft Windows Operating Sys
`tem compatible, includes the below-listed file(s). All of the
`material disclosed in the Computer Program Listing Appen
`dix can be found at the U.S. Patent and Trademark Office
`archives and is hereby incorporated by reference into the
`present application.
`0004 Object Description: SourceCode.txt, size: 87487
`Bytes, created: Jun. 1, 2005 5:57:28 PM; Object ID: File No.
`1: Object Contents: Source code.
`
`BACKGROUND OF INVENTION
`0005 1. Field of the Invention
`0006 The present invention relates generally to data
`processing environments and, more particularly, to a system
`and methodology for parallel query optimization using
`semantic-based partitioning.
`0007 2. Description of the Background Art
`0008 Computers are very powerful tools for storing and
`providing access to vast amounts of information. Computer
`databases are a common mechanism for storing information
`on computer systems while providing easy access to users.
`A typical database is an organized collection of related
`information stored as “records' having “fields” of informa
`tion. As an example, a database of employees may have a
`record for each employee where each record contains fields
`
`designating specifics about the employee, Such as name,
`home address, salary, and the like.
`0009 Between the actual physical database itself (i.e., the
`data actually stored on a storage device) and the users of the
`system, a database management system or DBMS is typi
`cally provided as a Software cushion or layer. In essence, the
`DBMS shields the database user from knowing or even
`caring about the underlying hardware-level details. Typi
`cally, all requests from users for access to the data are
`processed by the DBMS. For example, information may be
`added or removed from data files, information retrieved
`from or updated in such files, and so forth, all without user
`knowledge of the underlying system implementation. In this
`manner, the DBMS provides users with a conceptual view of
`the database that is removed from the hardware level. The
`general construction and operation of database management
`systems is well known in the art. See e.g., Date, C., “An
`Introduction to Database Systems, Seventh Edition’, Part I
`(especially Chapters 1-4). Addison Wesley, 2000.
`0010 SQL queries express what results are requested but
`do not state how the results should be obtained. In other
`words, the query itself does not tell how the query should be
`evaluated by the DBMS. Rather, a component of the DBMS
`called the optimizer determines the “plan” or the best
`method of accessing the data to implement the SQL query.
`The optimizer is responsible for transforming an SQL
`request into an access plan composed of specific implemen
`tations of the algebraic operator Selection, projection, join,
`and so forth. The role of a query optimizer in a relational
`DBMS system is to find an adequate execution plan from a
`search space of many semantically equivalent alternatives.
`0011
`Relational database queries are broadly classified
`into simple transactional queries found in online transaction
`processing (OLTP) environments, and complex queries
`found in operational decision support system (DSS) envi
`ronments. Although existing database systems are in wide
`use in DSS applications and in OLTP applications, there is
`a growing user demand for Supporting both types of queries
`in a single system. Users need a solution capable of handling
`complex queries and also having the ability to process large
`data sets for both local and distributed systems. They are
`looking for a robust database server system platform for
`running mixed workload applications that demand Superior
`performance for queries from both OLTP and DSS domains,
`Sometimes across distributed and heterogeneous database
`servers. This environment is referred to as an operational
`decision Support system (operational DSS), since it allows
`running complex queries as well as performing regular
`OLTP processing.
`0012 Users are also looking for the applications to
`provide improved performance. A problem in current data
`base systems is that as the quantities of data managed by a
`database system grows, the efficiency of relational opera
`tions (e.g., SQL queries) against the data maintained in the
`database decreases. The efficiency of relational operations,
`and in particular each of the various SQL operators (e.g.,
`joins, unions, and the like) that are used in executing
`database queries in modern database systems, starts dete
`riorating at a rate that is almost exponential to the quantity
`of data that must be handled by the SQL operator. Strategies
`that can be used to improve query performance involve
`reducing the total amount of work that needs to be done in
`
`Cloudera Exhibit 1003 - Page 23 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 25 of 49 PageID #: 524
`
`US 2006/0218123 A1
`
`Sep. 28, 2006
`
`executing a query and/or by dividing the work that needs to
`be done in executing the query among multiple processors.
`In order to effectively divide the work to be done among
`multiple processors, what is needed is an effective technique
`for partitioning the data to be operated on during the
`processing of the query into Smaller fragments so that
`operations on those fragments can be performed concur
`rently.
`0013 Unfortunately, existing partitioning strategies have
`a number of limitations. Current solutions only work for a
`Small Subset of SQL operations. Existing partitioning solu
`tions may be able to take advantage of the partitioning (e.g.,
`range partitioning) of a data table. For example, assume that
`a customer table is range partitioned on a customer id
`column, with customer ids<=1000 in P1 (partition one),
`1001-2000 in P2, 2001-3000 in P3, and so forth. With
`certain simple queries, such as a query requesting the data
`rows where customer id is greater than 2000 (e.g., SELECT
`* FROM customers WHERE customeridd2000), existing
`solutions can eliminate P1 and P2. However, existing solu
`tions do not provide capabilities for handling more complex
`operations such as joins, unions, distinctness, and so forth.
`Existing partitioning techniques do not provide a general
`ized solution applicable to all database operations, including
`complex SQL operations such as grouping, joins, distinct
`operations, unions, and the like. In addition, current solu
`tions rely to a large extent on partitioning of the underlying
`data. A better Solution that does not require partitioning of
`the underlying data is needed.
`0014. The ability to execute portions of a query in
`parallel provides increased efficiency and performance by
`dividing query operations into Subtasks which can then be
`executed across multiple resources like CPUs or disks
`simultaneously. However, to provide for more efficient par
`allel query processing, what is needed is a solution that
`provides the ability to efficiently partition data so that
`multiple Subtasks or operations can be performed simulta
`neously. The solution should be generalized so that it is
`Suitable for use in conjunction with database queries involv
`ing complex operations such as grouping, joins, unions, and
`distinctness. Ideally, the solution should also provide for
`partitioning data dynamically during the process of execut
`ing a query, without requiring partitioning of the database
`tables. The present invention provides a solution for these
`and other needs.
`SUMMARY OF INVENTION
`0015. A system and methodology for parallel query opti
`mization using semantic-based partitioning is described. In
`one embodiment, for example, in a database system com
`prising a database storing data in database tables, a method
`of the present invention is described for improving query
`performance by dynamically partitioning the data, the
`method comprises steps of receiving a query requesting
`data from the database; generating a plurality of Subplans for
`executing the query, each Subplan including one or more
`operators for performing relational operations; adding
`operators for partitioning data and performing a given
`relational operation in parallel to at least some of the
`plurality of Subplans; and building a plan for execution of
`the query based, at least in part, upon selecting Subplans
`having favorable execution costs.
`0016.
`In another embodiment, for example, in a database
`system, a method of the present invention is described for
`
`optimization of a query requesting data from a database, the
`method comprises steps of constructing a tree of relational
`operators based on the query, each relational operator for
`performing a given relational operation; determining
`whether dividing data processed by a particular relational
`operator in the tree is useful for executing a relational
`operation in parallel; if partitioning of a particular relational
`operator is determined to be useful, creating a revised tree by
`adding operators to the tree for dividing data processed by
`the particular relational operator and executing the particular
`relational operator in parallel over the divided data; and
`generating a plan for execution of the query based on the
`revised tree.
`0017. In yet another embodiment, for example, a data
`base system of the present invention for dynamically parti
`tioning data during query processing is described that com
`prises: a module for generating a plurality of plan fragments
`for obtaining data requested by a query from database tables
`of the database system; a partitioning module for creating
`additional plan fragments by adding operators for dynami
`cally partitioning data and processing the partitioned data in
`parallel to at least Some of the plan fragments; and a module
`for constructing a final plan for execution of the query based,
`at least in part, upon selecting plan fragments having opera
`tors for dynamically partitioning data and processing the
`partitioned data in parallel when dynamically partitioning
`data is determined to be advantageous.
`0018. In another embodiment, for example, in a database
`system comprises a database storing data in database tables,
`a method of the present invention is described for improving
`query performance comprising: receiving a query specifying
`a join of two or more database tables; as data is retrieved
`from the database during processing of the query, partition
`ing the data into separate memory buffers; and processing
`the query in parallel by concurrently processing the data in
`the memory buffers.
`
`BRIEF DESCRIPTION OF DRAWINGS
`0019 FIG. 1 is a very general block diagram of a
`computer system (e.g., an IBM-compatible system) in which
`Software-implemented processes of the present invention
`may be embodied.
`0020 FIG. 2 illustrates the general structure of a client/
`server database system Suitable for implementing the present
`invention.
`0021
`FIG. 3A is a block diagram of a serial operator tree
`illustrating a serial plan for executing a query.
`0022 FIG. 3B is a block diagram of a parallel operator
`tree fragment illustrating how exchange operators (iterators)
`are used to parallelize the serial query execution plan of
`FG. 3A
`0023 FIGS. 4A-B are block diagrams illustrating opera
`tor trees for serial and parallel plans which may be built by
`the optimizer for executing a query.
`0024 FIGS. 5A-B comprise block diagrams illustrating
`operator trees created for serial and parallel plans for a query
`involving a non-attribute sensitive operation.
`0025 FIG. 6 is a high-level functional diagram illustrat
`ing the two phases of optimization performed in the system
`of the present invention.
`
`Cloudera Exhibit 1003 - Page 24 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 26 of 49 PageID #: 525
`
`US 2006/0218123 A1
`
`Sep. 28, 2006
`
`0026 FIGS. 7A-D comprise block diagrams of operator
`trees illustrating several OR Strategies.
`0027 FIGS. 8A-G comprise block diagrams of operator
`trees illustrating several join partitioning and repartitioning
`strategies
`0028 FIGS. 9A-E comprise block diagrams of operator
`trees illustrating several merge join partitioning strategies.
`0029 FIG. 10A is a block diagram of an operator tree
`showing a parallel hash join where both operands are
`equi-partitioned on the joining predicates.
`0030 FIG. 10B is a block diagram of an operator tree
`showing both sides of a hash join being repartitioned.
`0031
`FIG. 10C is a block diagram illustrating an
`example of a scalar aggregate with an N to 1 merge.
`0032 FIG. 10D is a block diagram illustrating an
`example of a serial aggregation preceded by an N to 1
`merge.
`0033 FIG. 10E is a block diagram illustrating a parallel
`Vector aggregation of an example query.
`0034 FIG. 10F is a block diagram of an operator tree
`illustrating a centralized two phase aggregation approach.
`0035 FIG. 11A is a block diagram illustrating an
`example of grouped aggregation with minimal partitioning.
`0036 FIG. 11B is a block diagram of an operator tree
`illustrating a de-centralized two phase aggregation
`approach.
`0037 FIG. 12A is a block diagram of an operator tree
`showing an example of correlated subquery processing.
`0038 FIG. 12B is a block diagram of an operator tree
`illustrating repartitioning of operands to perform a parallel
`hash based union.
`0039 FIGS. 13 A-B comprise a single flowchart illustrat
`ing the method steps of the operations of the present
`invention for semantic-based partitioning in query optimi
`Zation.
`0040 FIG. 14 is block diagram of an operator tree
`representing a plan that may be built for executing a query.
`
`DETAILED DESCRIPTION
`0041 Glossary
`0042. The following definitions are offered for purposes
`of illustration, not limitation, in order to assist with under
`standing the discussion that follows.
`0.043 Core optimizer: The core optimizer is a component
`of the present invention that generates a set of optimal query
`plans that are then analyzed to select the best plan (i.e., the
`plan having most favorable execution costs).
`0044 Cost based pruning: Cost based pruning is a type of
`pruning technique where portions of a search space (tree
`shapes, permutations, access methods) are skipped purely
`based on cost estimates applicable to a query.
`0045 Directed acyclic graph: A directed graph is a graph
`whose edges are ordered pairs of vertices (nodes). Each edge
`of a directed graph can be followed from one node (vertex)
`
`to the next. A directed acyclic graph is a directed graph
`where no path starts and ends at the same node.
`0046) Dynamic partition elimination: Dynamic partition
`elimination refers to methodology of the present invention
`for eliminating one or more partitions from the list of
`partitions to be scanned when the value of a parameter or a
`variable is determined at runtime. This methodology is also
`applicable for a column whose value becomes known for the
`inner scan of a nested loop join.
`0047 Enforcer: The enforcer nodes (operators) generate
`properties Such as ordering, partitioning, and the like. At
`each node in a search graph all useful properties are made
`available either through eager enforcement by explicitly
`applying the enforcer or derived from child nodes. In prior
`database server systems properties were obtained by explic
`itly enforcing them, in Some cases unnecessarily, when
`available as side-products of child operators.
`0048 Equi-partitioned: Refers to two tables having com
`patible partitioning keys and partitioning criteria. If two
`tables have the same number of partition keys with com
`patible data types, and the partition criteria Such as the
`intervals are the same for the range partitions, the two tables
`are considered equi-partitioned.
`0049. Equivalence class: An equivalence class describes
`the set of Subplans that combine a given Subset of generic
`tables. The equivalence class also contains the logical prop
`erties of those subplans.
`0050 Execution engine operators: The execution module
`of the currently preferred embodiment of the present inven
`tion represents the query plan as a tree of operators (similar
`to the optimizer's physical plan-tree). These operators are
`referred to herein as execution engine operators or Lava
`engine operators (LeOp).
`0051
`Existence scan: An existence scan is based on
`stopping the scan of an existence table as soon as a tuple was
`fully qualified at the top level, when each existence table is
`placed only after all non-existence tables correlated to it. It
`is typically introduced by tables from a flattened EXISTS
`Subquery.
`0052 Expression partitioning: A partition condition
`specified by an expression involving attributes of a table that
`evaluates much like the SQL case statement to reference a
`specific partition.
`0053 Functional index: An index in which the index key
`contains functions on the attributes of the table. The index
`key could be an expression instead of a column list.
`0054 Generic Column: The term generic column nor
`mally refers to a column of a table referenced in a query, but
`may also refer to an abstraction that includes interesting
`expressions (e.g., those that can be used in an expression
`join).
`0055 Generic table: A generic table normally refers to a
`table referenced in a query, but also is a convenient abstrac
`tion to represent any object that is permutated in the join
`order by the optimizer. For example, a subquery can be
`modeled as a generic table.
`0056 Global index: Global indexes refer to indexes on
`partitioned tables. A global index results when an index and
`
`Cloudera Exhibit 1003 - Page 25 of 48
`
`

`

`Case 4:23-cv-01147-ALM Document 22-14 Filed 05/23/24 Page 27 of 49 PageID #: 526
`
`US 2006/0218123 A1
`
`Sep. 28, 2006
`
`the table have different partitioning strategies such that the
`index leaf pages of the global indexes point to more than one
`partition.
`0057 Hash: A hash (or hash value) is a smaller data type
`(e.g., number) that represents another, larger, data type
`(usually a string). A hash is typically a number that is
`generated from a string of text by a hashing function. The
`hash is substantially smaller than the text itself, and is
`generated in Such a way that it is unlikely that some other
`text will produce the same hash value. Hashes play a role in
`security systems (e.g., to ensure that transmitted messages or
`files have not been tampered with). Hashing is also a method
`for facilitating access to data records. Consider, for example,
`a list of names: John Smith, Sarah Jones, and Roger Adams.
`To create an index, called a hash table, for these records, one
`would apply a hashing function to each name to produce a
`unique numeric value such as the following: 1345873 John
`Smith, 3097905 Sarah Jones, 4060964 Roger Adams. To
`search for the record containing the name Sarah Jones, one
`just needs to reapply the hashing function, which directly
`yields the index key to the record. This is much more
`efficient than searching through all the records until the
`matching record is found.
`0.058 Hash based aggregation: A strategy for evaluating
`“GROUP B