勿误是什么意思| 左传是一部什么体史书| 补办身份证要带什么| 为什么叫智齿| 为什么不能踩死蜈蚣| 早上吃什么| 子宫内膜脱落是什么意思| 欣喜若狂的近义词是什么| 白龙马叫什么名字| 人为什么会说梦话| 打喷嚏流鼻涕吃什么药好| 尿毒症是什么原因引起的| 孩子反复发烧是什么原因| 蝙蝠属于什么动物| 猴子屁股为什么是红色| 芝柏手表什么档次| 云南是什么民族| 心理学属于什么学科| 三点水一个高念什么| 马眼是什么意思| 幼儿园什么时候报名| 什么是伟哥| 香叶是什么树叶| 股市xd是什么意思| 劲酒是什么酒| 宝宝什么时候断奶最好| 护理专业是干什么的| 肚脐下方是什么部位| 医学ca是什么意思| 朗朗原名叫什么| 马克笔是什么笔| 宫寒吃什么好得快| 男人为什么会得前列腺炎| 早餐吃什么简单又营养| 春节是什么时候| 吃榴莲有什么好处和坏处| 观音坐莲什么意思| poem是什么意思| 心绞痛吃什么药好| 梦见生了个女儿是什么意思| 产检请假属于什么假| 手指甲没有月牙是什么原因| 子宫脱落是什么原因引起的| 吃得什么填词语| 松花蛋是什么蛋做的| 仔是什么意思| 颈椎问题挂什么科| 阴茎进入阴道是什么感觉| 28岁属什么生肖| 沉香有什么好处| 特药是什么意思| 祛湿是什么意思| 便秘缺什么维生素| 腰肌劳损什么症状| 容易长口腔溃疡是什么原因| 桑葚是什么季节的| 印度人为什么用手抓饭吃| 抖腿是什么原因| 皮粉色是什么颜色| 两个方一个土读什么| 额头长痘什么原因| 米粉和米线有什么区别| 减肥头晕是什么原因| 男生小肚子疼是什么原因| 女频是什么| 舌苔发黄是什么原因引起的| 宫颈管分离什么意思| 桦树茸有什么作用| 48年属什么生肖| afi是胎儿的什么意思| 抗血小板是什么意思| 指是什么意思| 88年的龙是什么命| 贵族是什么意思啊| 1953年是什么生肖| 黄体什么意思| 肌肉拉伤挂什么科| 黄色裤子配什么颜色上衣| 取环后吃什么恢复子宫| 胃息肉吃什么药| 沙肝是什么| 嘴角上扬是什么意思| 身上没力气没劲是什么原因| 冻感冒吃什么药| 马眼是什么意思| 海尔洗衣机e3是什么故障| 天灵盖是什么意思| 用纸可以折什么| 白蛋白低是什么原因| 天降甘霖什么意思| 日晡潮热是什么意思| 瓠子是什么| 缺镁吃什么食物补充最快| 榴莲皮有什么功效| 世界七大奇迹分别是什么| 为什么会打呼| 来月经同房有什么影响| 端午节什么时候吃粽子| 皮肤溃烂化脓用什么药| 为什么医生说直肠炎不用吃药| 挖空细胞是什么意思啊| 理气是什么意思| 饮食清淡主要吃什么| 左侧卵巢内无回声是什么意思| 腻歪是什么意思| 便黑色大便是什么情况| 女人眉尾有痣代表什么| 为什么门牙突然有缝了| 宠辱不惊是什么意思| 曩是什么意思| 检查脂肪肝做什么检查| 杯弓蛇影的寓意是什么| 头晕呕吐是什么原因引起的| 9月19是什么星座| 钢铁锅含眼泪喊修瓢锅这是什么歌| 口腔溃疡用什么药好得快| 没有什么过不去| 益母草长什么样子图片| 男人不够硬吃什么好| 3.22是什么星座| 喝茶叶有什么好处| 一个草字头一个见念什么| 这是什么树| 海关清关什么意思| 女性缓解疲劳吃什么好| 车牌号选什么数字吉利| 嘴角烂了是什么原因| 汗腺是什么| 嘴唇黑是什么原因| 一个入一个肉念什么| 妨夫是什么意思| 夏天床上铺什么凉快| cea升高是什么意思| 血热是什么原因引起的| 张若昀原名叫什么| 膀胱是什么| 印迹杂交技术检查什么| 锲而不舍是什么生肖| 芍药什么时候开花| 超导是什么意思| 打嗝多是什么原因| 打嗝是什么原因引起的| 心衰吃什么药好| 血管脆是什么原因| 功劳叶的别名叫什么| 活塞是什么| 事业编制是什么意思| 穗字五行属什么| 丙型肝炎病毒抗体阴性什么意思| white是什么意思颜色| 唐僧是什么转世| 均码是什么意思| 猫叫什么名字好听| 梦到杀人是什么意思| 胃胀气吃什么药| 什么叫前列腺钙化| 12月生日是什么星座| 羽字五行属什么的| shuuemura是什么牌子| 渣男之首是什么星座| p是什么意思医学| 总胆红素高是什么意思| 用字五行属什么| 同比和环比是什么意思| 种猪是什么意思| 卯木代表什么| 痔疮手术后可以吃什么水果| 太监是什么| 尿潜血1十是什么原因| 龙虾和什么不能一起吃| 黑道日为什么还是吉日| 锦纹是什么中药| 尿路感染吃什么药好| 罗字五行属什么| 信五行属什么| 母鸡学公鸡叫什么征兆| 嘴唇有点发黑是什么原因引起的| 手麻去医院挂什么科| 头皮痒用什么止痒最好| 老年人吃饭老是噎着是什么原因| 弥可保是什么药| 人类祖先是什么动物| pnh是什么病| 牙痛吃什么消炎药| 甲状腺球蛋白抗体低说明什么| 口腔脱皮是什么原因引起的| 溺爱的意思是什么| 胸变大是什么原因| 什么食物含维生素c最多| 列装是什么意思| 弱视是什么意思| 茶色是什么颜色| 三叉神经疼吃什么药| 无花果什么时候种植| 心跳和心率有什么区别| 倒立有什么好处| 高血压有什么危害| 婴儿长牙有什么症状| 什么是单核细胞百分比| 为什么一直下雨| 3月9号是什么星座| 江西古代叫什么| 小孩出汗多是什么原因| 接触性皮炎用什么药| 入珠是什么意思| 炖大骨头放什么调料| 学英语先从什么学起| vs的意思是什么| 脑血管堵塞有什么症状| 七月十五日是什么节日| 临界点是什么意思| 组胺是什么| 怀孕脉象是什么样子| 氟斑牙是什么原因造成的| 后期是什么意思| 肚脐上面疼是什么原因| 白居易号什么居士| 牛肉汤配什么菜好吃| 甲鱼是什么| 嫡是什么意思| 婴儿睡觉头上出汗多是什么原因| 好色是什么意思| 化疗有什么副作用| 颤抖是什么意思| 月非念什么| 一什么家| 过敏什么东西不能吃| 温州什么最出名| 阿尼是什么意思| 戾气太重是什么意思| 黄痰咳嗽吃什么药| 发难是什么意思| 分割线是什么意思| 包粽子用什么米| mj是什么单位| 鸡吃什么| 国籍填什么| pas什么意思| 摩尔是什么| 父亲节送什么| 1991年五行属什么| 神疲乏力吃什么中成药| 朝是什么意思| 王字旁的字跟什么有关| 血糖低吃什么补的最快| 水手是干什么的| 肝功能异常是什么意思| 女孩和女人有什么区别| 右额头上有痣代表什么| 老气横秋是什么意思| teeth是什么意思| 梦见放生鱼是什么意思| 白细胞和淋巴细胞偏高是什么原因| 安康鱼长什么样| 八月份什么星座| 做梦掉牙齿是什么预兆| 女性脉弦是什么意思| 布洛芬吃多了有什么后果| 宫颈纳氏腺囊肿是什么意思| 血小板减少吃什么| 珍珠米是什么米| 功名是什么意思| 潘金莲属什么生肖| 妊娠试验阴性是什么意思| 百度

KPL第4周大势英雄盘点 五杀诸葛亮重回出场率

System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries Download PDF

Info

Publication number
US7085754B2
US7085754B2 US10/090,275 US9027502A US7085754B2 US 7085754 B2 US7085754 B2 US 7085754B2 US 9027502 A US9027502 A US 9027502A US 7085754 B2 US7085754 B2 US 7085754B2
Authority
US
United States
Prior art keywords
query
tables
pass
join
optimum
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime, expires
Application number
US10/090,275
Other versions
US20030167272A1 (en
Inventor
Joseph F. Sinnott, Jr.
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Priority to US10/090,275 priority Critical patent/US7085754B2/en
Assigned to INTERNATIONAL BUSINESS MACHINES CORPORATION reassignment INTERNATIONAL BUSINESS MACHINES CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: SINNOTT, JOSEPH F., JR.
Publication of US20030167272A1 publication Critical patent/US20030167272A1/en
Application granted granted Critical
Publication of US7085754B2 publication Critical patent/US7085754B2/en
Adjusted expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24Querying
    • G06F16/245Query processing
    • G06F16/2453Query optimisation
    • G06F16/24534Query rewriting; Transformation
    • G06F16/24542Plan optimisation
    • G06F16/24544Join order optimisation
    • YGENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10STECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00Data processing: database and file management or data structures
    • Y10S707/99931Database or file accessing
    • Y10S707/99932Access augmentation or optimizing

Definitions

  • This invention relates in general to database management systems performed by computers, and in particular to a system and method for determining the optimum join sequence and a lowest cost access path plan used in processing a multi-table SQL query in a relational database.
  • RDBMS Relational Database Management System
  • DBMS database management system
  • SQL Structured Query Language
  • the SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Organization (ANSI) and the International Standards Organization (ISO).
  • Algorithms used to determine the optimum join sequence for relational database queries which involve multiple tables can be very expensive in terms of CPU and storage use.
  • One such algorithm known as the Dynamic Programming Algorithm, can increase such usage proportional to 2**N, where N is the number of tables in the query. Therefore, it is very important that such algorithms be very efficient in their use of resources.
  • One preferred embodiment of the present invention is a computer-based method for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system.
  • the method is performed in two passes.
  • the first pass is used for determining an optimum join sequence for joining the plurality of tables from the query.
  • the second pass uses the optimum join sequence for creating a lowest cost access path plan for processing the multi-table query.
  • the first pass performs successive steps until creation of a simulated composite table having all tables from the query, wherein each step creates a set of miniplans for simulating all possible joins of a predetermined subset of the query tables and uses a cost model calculations for estimating and saving the least expensive join from this set of joins.
  • Another preferred embodiment of the present invention is a system implementing the above-mentioned method embodiment of the present invention.
  • Yet another preferred embodiment of the present invention includes a computer usable medium tangibly embodying a program of instructions executable by the computer to perform method steps of the above-mentioned method embodiment of the present invention.
  • FIG. 1 illustrates a computer hardware and software environment enabling the two-pass Dynamic Programming Algorithm, according to the preferred embodiments of the present invention
  • FIG. 2 illustrates a flowchart of the two-pass Dynamic Programming Algorithm, according to the preferred embodiments of the present invention.
  • FIG. 3 illustrates a flowchart of the first pass of the Dynamic Programming Algorithm, according to the preferred embodiments of the present invention.
  • the goal of the one-pass Dynamic Programming Algorithm used in processing a multi-table SQL query is to determine the complete detailed access path plan and to provide a great amount of supporting data, usually recorded in EXPLAIN tables.
  • the present invention discloses a system, method and a computer usable medium embodying a program of instructions executable by a computer to perform the method of the present invention for solving the CPU time and storage use expense problem of the prior art. It determines the optimum join sequence for relational database multi-tables queries by executing the Dynamic Programming Algorithm in two steps (passes), and is named a two-pass Dynamic Programming Algorithm.
  • the goal of the first pass is only to determine the best join sequence for joining the N tables in the query. It is the goal of the second pass to make use of this optimum join sequence to determine the detailed access path plan and the supporting data for processing the multi-table query.
  • FIG. 1 illustrates an exemplary computer hardware and software environment usable by the preferred embodiments of the present invention, including a computer system 102 having one or more conventional processors 104 executing instructions stored in an associated computer memory 105 , and having a computer system terminal 108 .
  • the operating memory 105 can be loaded with instructions received through an optional storage drive or through an interface with a computer network.
  • the processor 104 is connected to one or more electronic storage devices 106 , such as disk drives, that store one or more relational databases. They may comprise, for example, optical disk drives, magnetic tapes and/or semiconductor memory. Each storage device permits receipt of a computer usable medium, such as a magnetic media diskette, magnetic tape, optical disk, semiconductor memory and other machine-readable storage device, and allows for method program steps recorded on the computer usable medium be read and transferred into the computer memory.
  • the recorded program instructions may include the code for the method embodiment of the present invention. Alternatively, the program steps can be received into the operating memory from a computer over the network.
  • Operators of the computer system terminal 108 use a standard operator terminal interface (not shown), such as IMS/DB/DC, CICS, TSO, OS/2 or other similar interface, to transmit electrical signals to and from the computer system 102 , that represent commands for performing various tasks, such as search and retrieval functions, termed queries, against the databases stored on the electronic storage device 106 .
  • these queries conform to the Structured Query Language (SQL) standard, and invoke functions performed by a DataBase Management System (DBMS) 112 located at the computer system 102 , such as a Relational DataBase Management System (RDBMS) software.
  • SQL Structured Query Language
  • RDBMS Relational DataBase Management System
  • the RDBMS software is the DB2 product, offered by IBM for the AS400, OS390 or OS/2 operating systems, the Microsoft Windows operating systems, or any of the UNIX-based operating systems supported by the DB2.
  • the present invention has application to any RDBMS software that uses SQL, and may similarly be applied to non-SQL queries and probably even to non-relational databases.
  • FIG. 1 further illustrates a software environment enabling preferred embodiments of the present invention.
  • the computer system 102 further includes the two-pass Dynamic Programming Algorithm 110 software of the present invention.
  • the two-pass Dynamic Programming Algorithm 110 software is the computer-based method used for determining the optimum join sequence and the least cost access path for a relational database multi-tables query by performing the Dynamic Programming Algorithm in two passes 202 and 204 , as illustrated in FIG. 2 .
  • the goal of the first pass 202 is only to estimate the optimum join sequence for joining the tables in the query. It is the goal of the second pass 204 to use this optimum join sequence to determine the detailed access path plan and the supporting data for the multi-table query execution.
  • the two-pass Dynamic Programming Algorithm 110 simulates the construction of composite tables at each step.
  • Each composite table, except for the final one, contains a subset of the N tables.
  • the final composite table contains all N tables.
  • the strategy used to add a table to a composite table to create a second composite table which has one more table in it is represented internally by a control structure called a miniplan. Therefore, a miniplan represents each step of a generated access path plan.
  • the miniplan contains information such as: which index to use, which join method to use, and whether or not any sorting of the one of composite tables or the new table is required as a part of the process. It also contains some supporting data.
  • a cost model is used to estimate the cost of each step of the algorithm so that alternatives can be compared.
  • the cost is calculated in terms of CPU instructions time and I/O counts required to add a new table to a given composite table.
  • the two-pass algorithm allows partial results of the cost model calculations to be saved for a given table and index, during the first pass, and used in subsequent calculations. This results in significant savings in CPU time.
  • each composite table is represented internally by a control structure called a Cost structure.
  • the Cost structure contains information such as which tables are in the composite table, the cost of building the composite table and the various row orderings that might be possible.
  • the two-pass algorithm of the present invention was implemented as a part of the Dynamic Programming Algorithm of DB2 z/OS Version 7 product.
  • Some preferred embodiments of the present invention in the first pass of the algorithm use miniplan prototypes to avoid saving all information used by the algorithm in the miniplans, which is redundant. Moreover, in these preferred embodiments, the first pass saves partial results and retrieves them as similar situations are encountered when the algorithm proceeds. Miniplan prototypes and saving/restoring partial results are the options available in DB2 z/OS Version 8 product.
  • the first pass 202 of the two-pass Dynamic Programming Algorithm 110 of the present invention proceeds as follows in FIG. 3 .
  • the first pass performs following successive steps until a creation of a final simulated composite table having all tables from the query is detected in step 302 , when the routine returns in step 304 . Otherwise, each step 306 creates a set of miniplans for simulating all possible joins of a predetermined subset of the query tables, and each step 308 uses cost model calculations for estimating and saving the least expensive join from the set of joins, thereby determining the optimum join sequence.
  • step one of step 306 for each of the N tables from the query, simulates the construction of a one-table composite table.
  • the access path plan chosen to do this makes use of local predicates and any indexes that are available and can be used.
  • Cost and needed miniplan structures are built and filled in.
  • Step two of step 306 for each of the simulated one-table composite tables created in step one, determines whether the number of rows in any of these tables is exactly one or less. If there are any of these tables, this step simulates the joining of all of them together. For example, if there are 3 one-row, one-table composite tables, the algorithm simulates the building of a 3-table composite table. This is done to reduce the cost because the joining is performed at the beginning of the join sequence. For each created composite table Cost structure and needed miniplan structures are built and filled in.
  • Step three of step 306 tests whether a simulated one-row composite table was built in step two above. If so, the algorithm simulates the joining of the tables not in the one-row composite table to the one-row composite table in turn, to create a new set of composite tables. In the previous example, each composite table in this new set of composite tables will have 4 tables in it and there will be N- 3 of them. For each created composite table Cost structure and needed miniplan structures are built and filled in.
  • Step four of step 306 of the algorithm proceeds as follows. Given a set of composite tables with T tables in each T-composite table, the algorithm simulates the construction of composite tables with T+1 tables in each. This is performed by simulating the addition of a new table to a T-composite table to form a T+1-composite table. The new table must not already be in the T-composite table and may have to satisfy other constraints in order to be eligible for joining. For each new simulated T+1-composite table, a Cost structure and needed miniplan structures are built and filled in. Since there can be alternative ways to build a particular T+1-composite table, only the least expensive way is saved and the more expensive ways are discarded.
  • the process of the algorithm of the present invention continues until the construction of the final N-composite table is simulated, which indicates the end of the first pass.
  • the second pass the only output from the first pass, namely the optimum sequence in which the tables are joined in the N-composite table, is input in the algorithm.
  • the second pass makes use of this optimum join sequence of the simulated N-composite table to determine the detailed access path plan and the supporting data of the query plan. Therefore, the construction of the composite tables is simulated in the optimum join sequence.
  • Steps one to three of the second pass are identical to these steps in the first pass. Namely, step one of the second pass, for each of the N tables from the query, simulates the construction of a one-table composite table.
  • the access path plan chosen to do this makes use of local predicates, and any indexes that are available and can be used. For each created composite table Cost and needed miniplan structures are built and filled in.
  • Step two of the second pass for each of the simulated one-table composite tables created in step one, determines whether the number of rows in any of these tables is exactly one or less. If there are any of these tables, this step simulates the joining of all of them together. For each created composite table Cost and needed miniplan structures are built and filled in.
  • Step three of the second pass tests whether a simulated one-row composite table was built in step two above. If so, the algorithm simulates the joining of the tables not in the one-row composite table to the one-row composite table in turn, to create a new set of composite tables. For each created composite table Cost and needed miniplan structures are built and filled in.
  • step four of the second pass the next table in the join sequence is known, so the building of only one T+1-composite table is simulated, namely the composite table which results from adding the next table in the join sequence to the T-composite table. It determines the detailed access path plan and the supporting data of the query, used to describe how the system should process the query to obtain the result set.
  • the created Cost and miniplan structures contain all of the information needed by any following steps in the BIND or execution processes.
  • the number of Cost structures and miniplans is small.
  • the number of Cost structures is equal to two times the number of tables in the query.
  • the size of each miniplan is large, in order to hold the above plan and EXPLAIN tables information. Because each miniplan is unique, no attempt is made to generate miniplan prototypes, there is no saving of partial results and there is no Cost structure reuse.
  • the only information needed to be saved during the first pass is information which supports the determination of the optimum join sequence.
  • the first pass there is no need to save any of the supporting data used in the prior art for the EXPLAIN tables or most of the information detailing which indexes are used.
  • by breaking the algorithm into two passes significant reductions in CPU time and storage use have been achieved. For example, the storage space used for one 15-table query dropped from approximately 94 MB to approximately 3 MB by implementing this approach.
  • each saved miniplan requires in excess of 1000 bytes and in complex queries there can be tens of thousands of these miniplans.
  • only some miniplan prototypes needed to support the first pass algorithm are saved.
  • the storage required for each of these saved miniplan prototypes is 22 bytes, because each miniplan in the present invention does not have to hold the whole miniplan and EXPLAIN table supporting information. Therefore, the information which in the prior art needed to be saved tens of thousands of times is reduced to 8 bytes, 4 bytes of which address the one applicable miniplan prototype.
  • a cost model is invoked to estimate the cost in CPU and I/O resources required to add a new table to a given composite table.
  • the two-pass algorithm allows only partial results of these calculations to be saved for a given table and index during the first pass, and they are used in subsequent calculations. This results in significant savings in CPU time and I/O resources.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Operations Research (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

An apparatus, article of manufacture and computer-based method is provided for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system. The method is performed in two passes. The first pass is used for determining an optimum join sequence for joining the plurality of tables from the query. The second pass uses the optimum join sequence for creating a lowest cost access path plan for processing the query. The first pass performs successive steps until creation of a simulated composite table having all tables from the query, wherein each step creates a set of miniplans for simulating all possible joins of a predetermined subset of the query tables and uses a cost model calculations for estimating and saving the least expensive join from this set of joins.

Description

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular to a system and method for determining the optimum join sequence and a lowest cost access path plan used in processing a multi-table SQL query in a relational database.
2. Description of Related Art
Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. RDBMS software using a Structured Query Language (SQL) interface is well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Organization (ANSI) and the International Standards Organization (ISO).
Algorithms used to determine the optimum join sequence for relational database queries which involve multiple tables can be very expensive in terms of CPU and storage use. One such algorithm, known as the Dynamic Programming Algorithm, can increase such usage proportional to 2**N, where N is the number of tables in the query. Therefore, it is very important that such algorithms be very efficient in their use of resources.
In the conventional Dynamic Programming Algorithm the goal of the algorithm used in processing a multi-table SQL query is to determine the complete detailed access path plan and to provide a great amount of supporting data, usually recorded in EXPLAIN tables. This is very expensive.
Therefore, there is a need for a simple and optimized method and system able to solve the CPU time and storage usage expense problem by determining the optimum join sequence for relational database multi-tables queries.
SUMMARY OF THE INVENTION
The foregoing and other objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments, which makes reference to several drawing figures.
One preferred embodiment of the present invention is a computer-based method for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system. The method is performed in two passes. The first pass is used for determining an optimum join sequence for joining the plurality of tables from the query. The second pass uses the optimum join sequence for creating a lowest cost access path plan for processing the multi-table query. The first pass performs successive steps until creation of a simulated composite table having all tables from the query, wherein each step creates a set of miniplans for simulating all possible joins of a predetermined subset of the query tables and uses a cost model calculations for estimating and saving the least expensive join from this set of joins.
Another preferred embodiment of the present invention is a system implementing the above-mentioned method embodiment of the present invention.
Yet another preferred embodiment of the present invention includes a computer usable medium tangibly embodying a program of instructions executable by the computer to perform method steps of the above-mentioned method embodiment of the present invention.
BRIEF DESCRIPTION OF THE DRAWINGS
Referring now to the drawings in which like reference numbers represent corresponding parts throughout:
FIG. 1 illustrates a computer hardware and software environment enabling the two-pass Dynamic Programming Algorithm, according to the preferred embodiments of the present invention;
FIG. 2 illustrates a flowchart of the two-pass Dynamic Programming Algorithm, according to the preferred embodiments of the present invention; and
FIG. 3 illustrates a flowchart of the first pass of the Dynamic Programming Algorithm, according to the preferred embodiments of the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
In the following description of the preferred embodiments reference is made to the accompanying drawings, which form the part thereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural and functional changes may be made without departing from the scope of the present invention.
As mentioned above, in the prior art the goal of the one-pass Dynamic Programming Algorithm used in processing a multi-table SQL query is to determine the complete detailed access path plan and to provide a great amount of supporting data, usually recorded in EXPLAIN tables.
The present invention discloses a system, method and a computer usable medium embodying a program of instructions executable by a computer to perform the method of the present invention for solving the CPU time and storage use expense problem of the prior art. It determines the optimum join sequence for relational database multi-tables queries by executing the Dynamic Programming Algorithm in two steps (passes), and is named a two-pass Dynamic Programming Algorithm.
Therefore, in the present invention the goal of the first pass is only to determine the best join sequence for joining the N tables in the query. It is the goal of the second pass to make use of this optimum join sequence to determine the detailed access path plan and the supporting data for processing the multi-table query.
FIG. 1 illustrates an exemplary computer hardware and software environment usable by the preferred embodiments of the present invention, including a computer system 102 having one or more conventional processors 104 executing instructions stored in an associated computer memory 105, and having a computer system terminal 108. The operating memory 105 can be loaded with instructions received through an optional storage drive or through an interface with a computer network.
The processor 104 is connected to one or more electronic storage devices 106, such as disk drives, that store one or more relational databases. They may comprise, for example, optical disk drives, magnetic tapes and/or semiconductor memory. Each storage device permits receipt of a computer usable medium, such as a magnetic media diskette, magnetic tape, optical disk, semiconductor memory and other machine-readable storage device, and allows for method program steps recorded on the computer usable medium be read and transferred into the computer memory. The recorded program instructions may include the code for the method embodiment of the present invention. Alternatively, the program steps can be received into the operating memory from a computer over the network.
Operators of the computer system terminal 108 use a standard operator terminal interface (not shown), such as IMS/DB/DC, CICS, TSO, OS/2 or other similar interface, to transmit electrical signals to and from the computer system 102, that represent commands for performing various tasks, such as search and retrieval functions, termed queries, against the databases stored on the electronic storage device 106. In the present invention, these queries conform to the Structured Query Language (SQL) standard, and invoke functions performed by a DataBase Management System (DBMS) 112 located at the computer system 102, such as a Relational DataBase Management System (RDBMS) software. In the preferred embodiments of the present invention, the RDBMS software is the DB2 product, offered by IBM for the AS400, OS390 or OS/2 operating systems, the Microsoft Windows operating systems, or any of the UNIX-based operating systems supported by the DB2. Those skilled in the art will recognize, however, that the present invention has application to any RDBMS software that uses SQL, and may similarly be applied to non-SQL queries and probably even to non-relational databases.
FIG. 1 further illustrates a software environment enabling preferred embodiments of the present invention. In the system shown in FIG. 1 the computer system 102 further includes the two-pass Dynamic Programming Algorithm 110 software of the present invention. As mentioned above, the two-pass Dynamic Programming Algorithm 110 software is the computer-based method used for determining the optimum join sequence and the least cost access path for a relational database multi-tables query by performing the Dynamic Programming Algorithm in two passes 202 and 204, as illustrated in FIG. 2. The goal of the first pass 202 is only to estimate the optimum join sequence for joining the tables in the query. It is the goal of the second pass 204 to use this optimum join sequence to determine the detailed access path plan and the supporting data for the multi-table query execution.
The two-pass Dynamic Programming Algorithm 110 simulates the construction of composite tables at each step. Each composite table, except for the final one, contains a subset of the N tables. The final composite table contains all N tables. The strategy used to add a table to a composite table to create a second composite table which has one more table in it is represented internally by a control structure called a miniplan. Therefore, a miniplan represents each step of a generated access path plan. The miniplan contains information such as: which index to use, which join method to use, and whether or not any sorting of the one of composite tables or the new table is required as a part of the process. It also contains some supporting data.
In the algorithm of the present invention a cost model is used to estimate the cost of each step of the algorithm so that alternatives can be compared. The cost is calculated in terms of CPU instructions time and I/O counts required to add a new table to a given composite table. The two-pass algorithm allows partial results of the cost model calculations to be saved for a given table and index, during the first pass, and used in subsequent calculations. This results in significant savings in CPU time. Further, each composite table is represented internally by a control structure called a Cost structure. The Cost structure contains information such as which tables are in the composite table, the cost of building the composite table and the various row orderings that might be possible.
The two-pass algorithm of the present invention was implemented as a part of the Dynamic Programming Algorithm of DB2 z/OS Version 7 product. Some preferred embodiments of the present invention in the first pass of the algorithm use miniplan prototypes to avoid saving all information used by the algorithm in the miniplans, which is redundant. Moreover, in these preferred embodiments, the first pass saves partial results and retrieves them as similar situations are encountered when the algorithm proceeds. Miniplan prototypes and saving/restoring partial results are the options available in DB2 z/OS Version 8 product.
The first pass 202 of the two-pass Dynamic Programming Algorithm 110 of the present invention proceeds as follows in FIG. 3. The first pass performs following successive steps until a creation of a final simulated composite table having all tables from the query is detected in step 302, when the routine returns in step 304. Otherwise, each step 306 creates a set of miniplans for simulating all possible joins of a predetermined subset of the query tables, and each step 308 uses cost model calculations for estimating and saving the least expensive join from the set of joins, thereby determining the optimum join sequence.
In more detail, step one of step 306, for each of the N tables from the query, simulates the construction of a one-table composite table. The access path plan chosen to do this makes use of local predicates and any indexes that are available and can be used. For each created composite table Cost and needed miniplan structures are built and filled in.
Step two of step 306, for each of the simulated one-table composite tables created in step one, determines whether the number of rows in any of these tables is exactly one or less. If there are any of these tables, this step simulates the joining of all of them together. For example, if there are 3 one-row, one-table composite tables, the algorithm simulates the building of a 3-table composite table. This is done to reduce the cost because the joining is performed at the beginning of the join sequence. For each created composite table Cost structure and needed miniplan structures are built and filled in.
Step three of step 306 tests whether a simulated one-row composite table was built in step two above. If so, the algorithm simulates the joining of the tables not in the one-row composite table to the one-row composite table in turn, to create a new set of composite tables. In the previous example, each composite table in this new set of composite tables will have 4 tables in it and there will be N-3 of them. For each created composite table Cost structure and needed miniplan structures are built and filled in.
Step four of step 306 of the algorithm proceeds as follows. Given a set of composite tables with T tables in each T-composite table, the algorithm simulates the construction of composite tables with T+1 tables in each. This is performed by simulating the addition of a new table to a T-composite table to form a T+1-composite table. The new table must not already be in the T-composite table and may have to satisfy other constraints in order to be eligible for joining. For each new simulated T+1-composite table, a Cost structure and needed miniplan structures are built and filled in. Since there can be alternative ways to build a particular T+1-composite table, only the least expensive way is saved and the more expensive ways are discarded.
The process of the algorithm of the present invention continues until the construction of the final N-composite table is simulated, which indicates the end of the first pass. In the second pass the only output from the first pass, namely the optimum sequence in which the tables are joined in the N-composite table, is input in the algorithm. The second pass makes use of this optimum join sequence of the simulated N-composite table to determine the detailed access path plan and the supporting data of the query plan. Therefore, the construction of the composite tables is simulated in the optimum join sequence.
Steps one to three of the second pass are identical to these steps in the first pass. Namely, step one of the second pass, for each of the N tables from the query, simulates the construction of a one-table composite table. The access path plan chosen to do this makes use of local predicates, and any indexes that are available and can be used. For each created composite table Cost and needed miniplan structures are built and filled in.
Step two of the second pass, for each of the simulated one-table composite tables created in step one, determines whether the number of rows in any of these tables is exactly one or less. If there are any of these tables, this step simulates the joining of all of them together. For each created composite table Cost and needed miniplan structures are built and filled in.
Step three of the second pass tests whether a simulated one-row composite table was built in step two above. If so, the algorithm simulates the joining of the tables not in the one-row composite table to the one-row composite table in turn, to create a new set of composite tables. For each created composite table Cost and needed miniplan structures are built and filled in.
In step four of the second pass the next table in the join sequence is known, so the building of only one T+1-composite table is simulated, namely the composite table which results from adding the next table in the join sequence to the T-composite table. It determines the detailed access path plan and the supporting data of the query, used to describe how the system should process the query to obtain the result set. The created Cost and miniplan structures contain all of the information needed by any following steps in the BIND or execution processes.
In the second pass, although there is a great amount of supporting data created in the EXPLAIN tables, the number of Cost structures and miniplans is small. The number of Cost structures is equal to two times the number of tables in the query. The size of each miniplan is large, in order to hold the above plan and EXPLAIN tables information. Because each miniplan is unique, no attempt is made to generate miniplan prototypes, there is no saving of partial results and there is no Cost structure reuse.
In the two-pass Dynamic Programming Algorithm 110 of the present invention the only information needed to be saved during the first pass is information which supports the determination of the optimum join sequence. In the first pass there is no need to save any of the supporting data used in the prior art for the EXPLAIN tables or most of the information detailing which indexes are used. In the preferred embodiments of the present invention, by breaking the algorithm into two passes significant reductions in CPU time and storage use have been achieved. For example, the storage space used for one 15-table query dropped from approximately 94 MB to approximately 3 MB by implementing this approach.
In the prior art every candidate miniplan was saved as a possible final solution. Each saved miniplan requires in excess of 1000 bytes and in complex queries there can be tens of thousands of these miniplans. In some preferred embodiments of the two-pass algorithm of the present invention, however, only some miniplan prototypes needed to support the first pass algorithm are saved. The storage required for each of these saved miniplan prototypes is 22 bytes, because each miniplan in the present invention does not have to hold the whole miniplan and EXPLAIN table supporting information. Therefore, the information which in the prior art needed to be saved tens of thousands of times is reduced to 8 bytes, 4 bytes of which address the one applicable miniplan prototype.
Further, in the prior art a Cost structure was used for each composite table, and there were thousands of them for a complex query. Because in the two-pass process of the present invention many of these structures are not needed after the first few steps of the algorithm, they are reused which further reduces the amount of storage space required.
Moreover, at each step of the algorithm a cost model is invoked to estimate the cost in CPU and I/O resources required to add a new table to a given composite table. For each given table there are many calculations in the cost model which are repetitive. The two-pass algorithm allows only partial results of these calculations to be saved for a given table and index during the first pass, and they are used in subsequent calculations. This results in significant savings in CPU time and I/O resources.
The foregoing description of the preferred embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.

Claims (18)

What is claimed is:
1. A computer-based method for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system, the method comprising the steps of:
(a) a first pass using simulation, miniplans and composite tables for determining an optimum join sequence for joining the plurality of tables from the query; and
(b) a second pass for using the optimum join sequence for creating a lowest cost access path plan for processing the query.
2. The method according to claim 1, wherein the first pass performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step:
creating a set of miniplans for simulating all possible joins of a predetermined subset of the query tables; and
using a cost model calculations for estimating and saving the least expensive join from said set of joins, thereby determining the optimum join sequence.
3. The method according to claim 2, wherein the first pass for each said miniplan storing a used table index, join method, and sorting data, and for each said least expensive join storing names of joined tables, join cost and possible row orderings.
4. The method according to claim 3, wherein the first pass only storing non-redundant miniplan data, and saving partial results of the cost model calculations for future reuse.
5. The method according to claim 1, wherein the second pass performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step being performed in the optimum join sequence.
6. The method according to claim 1, wherein the query being a SQL query.
7. A computer-based processor system for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system, the system comprising:
means for performing a first pass using simulation, miniplans and composite tables for determining an optimum join sequence for joining the plurality of tables from the query; and
means for performing a second pass for using the optimum join sequence for creating a lowest cost access path plan for processing the query.
8. The system according to claim 7, wherein the first pass means performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step:
creating a set of miniplans for simulating all possible joins of a predetermined subset of the query tables; and
using a cost model calculations for estimating and saving the least expensive join from said set of joins, thereby determining the optimum join sequence.
9. The system according to claim 8, wherein the first pass means for each said miniplan storing a used table index, join method, and sorting data, and for each said least expensive join storing names of joined tables, join cost and possible row orderings.
10. The system according to claim 9, wherein the first pass means only storing non-redundant miniplan data, and saving partial results of the cost model calculations for future reuse.
11. The system according to claim 7, wherein the second pass means performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step being performed in the optimum join sequence.
12. The system according to claim 7, wherein the query being a SQL query.
13. A computer usable medium tangibly embodying a program of instructions executable by the computer to perform a computer-based method for determining the optimum join sequence for processing a query having a plurality of tables from a relational database stored in an electronic storage device having a database management system, the method comprising the steps of:
(a) a first pass using simulation, miniplans and composite tables for determining an optimum join sequence for joining the plurality of tables from the query; and
(b) a second pass for using the optimum join sequence for creating a lowest cost access path plan for processing the query.
14. The method according to claim 13, wherein the first pass performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step:
creating a set of miniplans for simulating all possible joins of a predetermined subset of the query tables; and
using a cost model calculations for estimating and saving the least expensive join from said set of joins, thereby determining the optimum join sequence.
15. The method according to claim 14, wherein the first pass for each said miniplan storing a used table index, join method, and sorting data, and for each said least expensive join storing names of joined tables, join cost and possible row orderings.
16. The method according to claim 15, wherein the first pass only storing non-redundant miniplan data, and saving partial results of the cost model calculations for future reuse.
17. The method according to claim 13, wherein the second pass performing successive steps until creation of a simulated composite table having all tables from the query, wherein each said step being performed in the optimum join sequence.
18. The method according to claim 13, wherein the query being a SQL query.
US10/090,275 2025-08-05 2025-08-05 System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries Expired - Lifetime US7085754B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
US10/090,275 US7085754B2 (en) 2025-08-05 2025-08-05 System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US10/090,275 US7085754B2 (en) 2025-08-05 2025-08-05 System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries

Publications (2)

Publication Number Publication Date
US20030167272A1 US20030167272A1 (en) 2025-08-05
US7085754B2 true US7085754B2 (en) 2025-08-05

Family

ID=27803992

Family Applications (1)

Application Number Title Priority Date Filing Date
US10/090,275 Expired - Lifetime US7085754B2 (en) 2025-08-05 2025-08-05 System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries

Country Status (1)

Country Link
US (1) US7085754B2 (en)

Cited By (7)

* Cited by examiner, ? Cited by third party
Publication number Priority date Publication date Assignee Title
US20090083238A1 (en) * 2025-08-05 2025-08-05 Microsoft Corporation Stop-and-restart style execution for long running decision support queries
US8036908B2 (en) * 2025-08-05 2025-08-05 Sap Aktiengesellschaft System and method for the assembly of programs
US8881139B1 (en) * 2025-08-05 2025-08-05 Infinite Corporation Legacy application rehosting system
US9237063B2 (en) 2025-08-05 2025-08-05 Cisco Technology, Inc. System and method for remote monitoring and control of network devices
US9652498B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Processing queries using hybrid access paths
US10810201B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Technology for join processing
US11914594B1 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Dynamically changing query mini-plan with trustworthy AI

Families Citing this family (8)

* Cited by examiner, ? Cited by third party
Publication number Priority date Publication date Assignee Title
JP4463661B2 (en) * 2025-08-05 2025-08-05 株式会社日立製作所 Computer system, computer, database access method and database system
US7630967B1 (en) * 2025-08-05 2025-08-05 At&T Intellectual Property Ii, L.P. Join paths across multiple databases
US7685098B2 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Estimating the size of a join by generating and combining partial join estimates
CN102262675B (en) * 2025-08-05 2025-08-05 北京握奇数据系统有限公司 Method for querying database and smart card
EP2682878A1 (en) * 2025-08-05 2025-08-05 Software AG Method of processing relational queries in a database system and corresponding database system
US9449098B2 (en) * 2025-08-05 2025-08-05 Macy's West Stores, Inc. System and method for performing a multiple pass search
US11461319B2 (en) 2025-08-05 2025-08-05 Business Objects Software, Ltd. Dynamic database query efficiency improvement
US11847120B2 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Performance of SQL execution sequence in production database instance

Citations (10)

* Cited by examiner, ? Cited by third party
Publication number Priority date Publication date Assignee Title
US5345585A (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations
US5600829A (en) * 2025-08-05 2025-08-05 Wisconsin Alumni Research Foundation Computer database matching a user query to queries indicating the contents of individual database tables
US5671403A (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Iterative dynamic programming system for query optimization with bounded complexity
US6138111A (en) * 2025-08-05 2025-08-05 Informix Software, Inc. Cardinality-based join ordering
US6370522B1 (en) * 2025-08-05 2025-08-05 Oracle Corporation Method and mechanism for extending native optimization in a database system
US6377943B1 (en) * 2025-08-05 2025-08-05 Oracle Corp. Initial ordering of tables for database queries
US6397204B1 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method, system, and program for determining the join ordering of tables in a join query
US6421657B1 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method and system for determining the lowest cost permutation for joining relational database tables
US6516310B2 (en) * 2025-08-05 2025-08-05 Sybase, Inc. System and methodology for join enumeration in a memory-constrained environment
US6643636B1 (en) * 2025-08-05 2025-08-05 Ncr Corporation Optimizing a query using a non-covering join index

Patent Citations (10)

* Cited by examiner, ? Cited by third party
Publication number Priority date Publication date Assignee Title
US5345585A (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations
US5600829A (en) * 2025-08-05 2025-08-05 Wisconsin Alumni Research Foundation Computer database matching a user query to queries indicating the contents of individual database tables
US5671403A (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Iterative dynamic programming system for query optimization with bounded complexity
US6138111A (en) * 2025-08-05 2025-08-05 Informix Software, Inc. Cardinality-based join ordering
US6377943B1 (en) * 2025-08-05 2025-08-05 Oracle Corp. Initial ordering of tables for database queries
US6370522B1 (en) * 2025-08-05 2025-08-05 Oracle Corporation Method and mechanism for extending native optimization in a database system
US6421657B1 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method and system for determining the lowest cost permutation for joining relational database tables
US6397204B1 (en) * 2025-08-05 2025-08-05 International Business Machines Corporation Method, system, and program for determining the join ordering of tables in a join query
US6516310B2 (en) * 2025-08-05 2025-08-05 Sybase, Inc. System and methodology for join enumeration in a memory-constrained environment
US6643636B1 (en) * 2025-08-05 2025-08-05 Ncr Corporation Optimizing a query using a non-covering join index

Non-Patent Citations (2)

* Cited by examiner, ? Cited by third party
Title
Arun Swami et al , Optimization of Large Join Queries, ACM 1988, pp. 8-17. *
Microsoft press computer dictionary, 1997, p. 437. *

Cited By (9)

* Cited by examiner, ? Cited by third party
Publication number Priority date Publication date Assignee Title
US8036908B2 (en) * 2025-08-05 2025-08-05 Sap Aktiengesellschaft System and method for the assembly of programs
US9237063B2 (en) 2025-08-05 2025-08-05 Cisco Technology, Inc. System and method for remote monitoring and control of network devices
US20090083238A1 (en) * 2025-08-05 2025-08-05 Microsoft Corporation Stop-and-restart style execution for long running decision support queries
US8881139B1 (en) * 2025-08-05 2025-08-05 Infinite Corporation Legacy application rehosting system
US9652498B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Processing queries using hybrid access paths
US9652497B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Processing queries using hybrid access paths
US10810201B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Technology for join processing
US10810200B2 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Technology for join processing
US11914594B1 (en) 2025-08-05 2025-08-05 International Business Machines Corporation Dynamically changing query mini-plan with trustworthy AI

Also Published As

Publication number Publication date
US20030167272A1 (en) 2025-08-05

Similar Documents

Publication Publication Date Title
US7499917B2 (en) Processing cross-table non-Boolean term conditions in database queries
US7085754B2 (en) System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries
US7734615B2 (en) Performance data for query optimization of database partitions
US7831620B2 (en) Managing execution of a query against a partitioned database
US8099725B2 (en) Method and apparatus for generating code for an extract, transform, and load (ETL) data flow
US7698253B2 (en) Method and system for reducing host variable impact on access path selection
US8412700B2 (en) Database query optimization using index carryover to subset an index
US7613701B2 (en) Matching of complex nested objects by multilevel hashing
US6289355B1 (en) Fast log apply
US6343286B1 (en) Efficient technique to defer large object access with intermediate results
US7113951B2 (en) Method and system for detecting tables to be modified
US7080072B1 (en) Row hash match scan in a partitioned database system
US6944633B1 (en) Performing a join in a partitioned database system
US7783625B2 (en) Using data in materialized query tables as a source for query optimization statistics
US5926809A (en) Two-tier query methodology for a database
US6999967B1 (en) Semantically reducing the number of partitions involved in a join
US7020647B1 (en) Utilize encoded vector indexing for database grouping
CN108549666A (en) A kind of sort method of tables of data, device, equipment and storage medium
US6272486B1 (en) Determining the optimal number of tasks for building a database index
US7383270B1 (en) Compressing data stored in an intermediate or result table of a database
US20060085464A1 (en) Method and system for providing referential integrity constraints
US8005820B2 (en) Optimizing the processing of in-list rows
US20070005612A1 (en) Methods and systems for optimizing searches within relational databases having hierarchical data
US7487140B2 (en) Method for executing a query having multiple distinct key columns
US20020138464A1 (en) Method and apparatus to index a historical database for efficient multiattribute SQL queries

Legal Events

Date Code Title Description
AS Assignment 百度 我们学校以前只有科技特长生名额,因为今年市教育局政策支持,我们正在申报招收化学学科特长生,一是学校化学学科实力很强,有化学特级教师以及名师工作站,不少学生获得过国家级化学竞赛奖项;二是给对化学有特长的学生提供一个专业发展平台。

Owner name: INTERNATIONAL BUSINESS MACHINES CORPORATION, NEW Y

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SINNOTT, JOSEPH F., JR.;REEL/FRAME:012673/0498

Effective date: 20020301

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

STCF Information on status: patent grant

Free format text: PATENTED CASE

FPAY Fee payment

Year of fee payment: 4

REMI Maintenance fee reminder mailed
FPAY Fee payment

Year of fee payment: 8

SULP Surcharge for late payment

Year of fee payment: 7

FEPP Fee payment procedure

Free format text: 11.5 YR SURCHARGE- LATE PMT W/IN 6 MO, LARGE ENTITY (ORIGINAL EVENT CODE: M1556)

MAFP Maintenance fee payment

Free format text: PAYMENT OF MAINTENANCE FEE, 12TH YEAR, LARGE ENTITY (ORIGINAL EVENT CODE: M1553)

Year of fee payment: 12

咽喉炎是什么原因引起的 没有什么 榆木脑袋是什么意思 小孩什么时候换牙 儿童支气管炎吃什么药
敖包是什么意思 包皮手术是什么 598是什么意思 八字华盖是什么意思 内膜厚吃什么掉内膜
减肥为什么不让吃茄子 fizz是什么意思 巧克力囊肿是什么意思 gin什么意思 射精什么感觉
输卵管发炎有什么症状表现 什么的英语单词 zoom什么意思 利多卡因是什么药 全日制专科是什么意思
脾胃不和吃什么药hcv8jop2ns0r.cn 脂肪疝是什么病cj623037.com 扁桃体结石是什么原因引起的hcv9jop4ns2r.cn 鼻梁歪的男人说明什么hcv7jop5ns5r.cn 荟萃是什么意思hcv8jop5ns5r.cn
隐翅虫怕什么hcv9jop4ns8r.cn 澳门什么时候回归祖国hcv9jop5ns8r.cn 红细胞低吃什么补得快qingzhougame.com wing什么意思hcv8jop8ns5r.cn 一个至一个秦是什么字hcv8jop1ns9r.cn
为什么叫印度阿三hcv8jop5ns0r.cn 扁豆长什么样子图片hcv9jop3ns1r.cn 什么水果吃了对皮肤好youbangsi.com 爱打扮的女人说明什么hcv7jop5ns3r.cn 阿苯达唑片是什么药hcv8jop8ns5r.cn
1978年什么命hcv8jop2ns1r.cn 弯弯的什么creativexi.com 浙江属于什么方向hcv9jop6ns1r.cn 钾低了会出现什么症状hcv8jop7ns9r.cn 24k是什么意思hcv8jop2ns0r.cn
百度