United States Patent
`French et al.
`
`[19]
`
`[111 Patent Number:
`
`5,794,229
`
`[451 Date of Patent:
`
`Aug. 11, 1998
`
`USD(JS794229A
`
`[54] DATABASE SYSTEM WITH
`METHODOLOGY FOR STORING A
`DATABASE TABLE BY VERTICALLY
`PARTITIONING ALL COLUMNS OF THE
`TABLE
`
`[75]
`
`Inventors: Clark French. Pepperell; Peter White.
`Andover. both of Mass.
`
`[73] Assignee: Sybase, Inc.. Emeryvillc. Calif.
`
`[21] Appl. No; 570,183
`
`[22] Filed:
`
`Dec. II, 1995
`
`Related US. Application Data
`
`[63] Continuation-tn-part of sa. No. 43.537, Apr. 16. 1993,
`alrandotzted.
`
`[52] US. Cl.
`
`70132; 70’lJ3: "£07110:
`'"";'r'J'r':"r'205; 7111100; 71rm1;7osi35
`[58] Field orsearda
`395:'60l—6I2.
`393603: 70712. 3. 10. 205: 70555: 7'11! W0.
`W1
`
`[56]
`
`References Cited
`
`U.S. PKI'ENT DOCUMENTS
`
`811986
`4.606.002
`61198?
`4,6'l'}',5S0
`1031988
`431-'6.026
`1011992
`5.15359]
`311994
`5293.616
`5.33‘?-‘,3-t-8 D1199-I
`5,404,310
`-‘W995
`5.495.608
`2/1996
`5,649.18]
`7!l9'97 Frenchet al.
`
`
`
`.
`........................... 395K603
`
`OTHER PUBLICATIONS
`
`"A ‘1lransa.cl:iol:l—BlIscd Approach to Vertical Partitioning fcr
`Relational Database Systems“. Chu er al.. IEEE. v19. n8.
`IEEE Transaction of Software Engineering. Aug. 1993.
`“RDBMS Mattu'ity". Philip A. Naeclrcr. DEC Professional
`vlD,nl2. p. 44-(6) [Available—Onliae; Dialog File 2'75 1. Nov.
`1991.
`
`“Ingres Table Sructurcs“. David Snellen. DBMS. V5. n8. p.
`60(3) |Available: On—Line‘. Dialog File 2'?5J. Jul. 1992.
`Reinartz. l(.. “Aspects of vertical mode in multiprocessor
`systems, urtcortverrtional computation on oonut'mr’ortal_pro-
`cesrorr." Second International Spccalist Seminar on the
`Design and Application of Parallel Digital Processors. IEEE.
`1994. pp. 48-54.
`Brodie. M. and Manola. F.. "Database Management: A
`Survey" 1987. pp. 1-24.
`I-Ianson—Sm.ith. L1d.. “Adwmtage Series System Overview:
`I/en 2.0." 1990. pp. 1-132.
`
`Prr'mor_v Erantirrer-—T'lI0ma5 G. Black
`Assistant .Examirrer——HI:I6aJ'J'1 '1'‘. Alma
`Anomey, Agent. or Firm—-John A. Smart
`
`[57]
`
`AB-Sl'R.AC"l‘
`
`A Clienllsewer Database System with improved methods
`for performing database queries. particularly DSS-type
`qtreries. is described. The system includes one or more
`Clients (e.g.. Terminals or PCs) connected via a Network to
`a Server. In general operation. Clients store data in and
`retrieve data from one or more database tables resident on
`the Server by submitting SQL commands. some of which
`specify “querics“—crlteria for selecting partictllar records
`of a table. The system implements methods 1‘or storing data
`vertica.lly (i.e.. by column}. instead of horizontally (i.e.. by
`row) as is traditionally done. Each column corrtprises a
`plurality of "cells" {i.e.. column value for it record). which
`are arranged on a data page in a contiguous fashion. By
`storing data in a column-wise basis. the system can process
`a DSS query by Izringirrg in only these columns of data
`which are of interest. Instead of retrieving row-based data
`pages consisting of information which is largely not of
`interest to a query. column-based pages can be retrieved
`consisting of information which is mostly. if not oornpletcly.
`of interest to the query. The retrieval itself am he done using
`rntre»e:ll:icient large block U0 transfers. The system includes
`data compression which is provided at the level of Cache or
`Bufia Managers. thus providing on-the-fly data compres-
`sion in a manner which is transparent to each object. Since
`vertical storage of data leads to high repetition on a given
`data page.
`the system provides improved compression!
`decompression.
`
`24 Claims, 11 Drawing Sheets
`
`CUE runs Matt
`rrornou mm
`
`
`
`lZCl.la|0hB-ASED
`mus
`
`R7101.)
`IGE
`
`
`
`Oracle 1111
`
`Oracle 1 1 1 1
`
`

`
`U.S. Patent
`
`Aug. .11, 1993
`
`Sheet 1 of 11
`
`5,794,229
`
`19!
`
`104
`
`KEYBOARD
`
`
`
`105
`
`107
`
`103
`
`SCREEN
`WSPLAY
`
`MASS
`STORAGE
`
`OUTPUT
`DEWCE
`
`‘°2
`
`MAM
`MEMORY
`
`101
`
`CENTRAL
`PROCESSOR
`
`CACHE
`MEMORY
`
`109
`
`
`
`no
`CONTROLLER
`
`no
`
`FIG. 1A
`
`

`
`P5U
`
`uA
`
`9M,
`
`2
`
`5
`
`0;2J,4
`
`m|mE
`
`wezo_Eo:._n.<
`
`@:§__ooE
`
`admzmemo<“_mEz_mm58Imzoozi
`
`mmm:
`
`9.J,3mm
`
`0mi.
`
`..u.s_m5>moz:$m_n_o9:
`
`
`
`
`
`
`

`
`5U
`
`M
`
`9
`
`9
`
`P%
`
`AzmaaHHmm>mm_m
`
`
`..m.mmsmmmxmefimzatzmno
`mm<m<:5WW3WWemuWamWSm
`
`
`
` I
`4",NGE
`
`
`
`7",__5WW
`
`
`
`mumWW3Eoéé‘WWmE..$xmoz_E~:<s_¢oz‘mmWW
`
`~_w.__n__2oo.
`
` mmm8<EuWMmmaIim-:2:zo_Sumxm_mmMfimwmmmWBWH_m8” mmmo¢z<_2Eta‘«RW8o:ms_33%mofimmzmomaoo‘mmWW_‘__W@._<z_.$_m»‘_.MOn_
`
`
`
`
`
`

`
`US. Patent
`
`Aug. 11, 1993
`
`Sheet 4 of 11
`
`922.,497’5
`
`can
`
`L;
`
`onE
`
`Egflnmaaggaaag
`
`
`
`Ezmo::295.xEHEMEEzm._._<.5222as
`
`
`
`m_:_>§msmz$m<m.a_.._.mzmHaEuflEfluEEm:_>mmm
`
`
`
`
`
`a9m:
`
`am2:30memo.
`
`3..GE
`
` an
`
`
`
`Em
`
`En.
`
`On.
`
`
`
`M55.mERG8mzszoumox8.m<m.§o~_
`
`
`
`Emammm_....Em.8
`
`SE3$63
`
`~BE
`
`
`
`n_3$2952zaotcéoz__,§oaE.32.
`
`mm.._.m2.522:E5.032.
`
`re.83..
`
`dom_...__>.Ems_.u.
`
`
`z._mm.._m>mF._._m=._mHmmzzmo:._._.295.x
`
`.z._.._._.mO..<..N>.Eus..1
`
`89.
`
`32.
`
`39
`
`_...mam:mac...2.525Egg.mmEm5%35.“.
`
`
`
`
`
`
`
`

`
`..lHB4...aD13U
`
`Aug. ll, 1998
`
`Sheet 5 of 11
`
`922.,497.,5
`
`8m
`
`
`moqO....m.E<Q
`
`3.02%;8m<m.zs.3oo
`
`Em:
`
`dom._.__>Ems_m
`
`.z.__.FmO_.Smm>._u_0.2mz._mm<m»m_.._.m_zm.._.
`
`anT|.1||JI2&6mgm
`
`
`
`mmGE
`
`:8
`
`on...
`
`On.E
`
`~um;,lg823259%_._on_
`
`miE08
`
`
`
`Emammm:Em8
`
`$63#960.:
`
`
`
`
`
`_...mama$023Egfiggn__53mama
`
`zm._._<85222.5.;z<
`.52:58.9%.0
`
`m._.__>m_m_m
`
`
`
`
`
`mmE,m_o_._.:.20.5.x
`
`
`
`
`
`
`

`
`US. Patent
`
`Aug. 11, 1993
`
`Sheet 6 of 11
`
`5,794,229
`
`
`
`moq03.5.3gm3<o...Em>..,m.m<m.z_._s§
`
`
`
`Ems$m.:9a.8
`
`
`
`§ms$960....
`
`
`
`IE;23.5mj_>mm_mmmnzmo::zo>.__x82H.8.5z_<s_cm.Exec82
`
`
`
`H.3<22.502,:oz_z;on_252
`
`_...mBmEE023EamirmggE42958“mam:
`
`
`
`.25.3Eco;anEo:.n_8.:m85m.:_>._,$s_m2._mm<m>w_jwzmH32
`
`_mmrum
`
`lgggg
`
`E
`
`onNam;
`
`omE
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 7 of 11
`
`922,497..5
`
`IEEE
`
`..95
`
`0:.
`
`S‘GE
`
`222:E889:888.2.88_
`\8:2:£889:883.288.
`as2::_.m.B_Eo.oP8B8.8......_
`:2E:E8888.E:58888"
`
`
`
`ommnzaname
`
`9%.\\\\\.
`
`8:.9.:28:3:.:.
`
`3322
`
`zononammE3
`
`
`
`mmomts:m.%
`
`Sum9E8
`
`
`
`sm_§#563.
`
`
`
`
`
`

`
`9
`
`fl.4.,ma.em93%
`
`U
`
`P.
`
`8m
`
`.m
`
`m8
`
`.3
`
`7.,
`
`
`
`
`
`%~zoammmazoo..S_§.aw:
`
`;..o_mmmE:.oumg:
`
`m_2o_mmmE:ou3:ma2..
`
`amzoammmuzouEs.
`
` .chm;m;.o.a§s§..sE..§§ImlEEu—__EEEH§;=:.
`
`mean.
`
`
`

`
`m34|.3PSU
`
`Aug. 11, 1998
`
`Sheet 9 of 11
`
`92J,MJ,5
`
`
`
`
`
`E2.38.--8.8.888.8.88_..wt
`
`2528880So8::588_
`
`2.885889:5888:588_
`8:2888889._._:888089
`:8:8:.:88888888:5.“
`
`8.GE
`
`.~<m:.:..2
`
`zocoaommE10.
`
`T
`
`
`
`mmoflz.L:m.8
`
`Sm:mom
`
`
`
`Ems8§oo.:
`
`
`
`

`
`mt...§.,_am<o
`
`m
`
`3.5
`
`9
`
`amuzqxzm
`
`zoammmmzoo
`
` bM,9.GE
`
`
`
`
`
`mSoozsm25$gg182mm.»33%xx?kc?_LozamzandH%_._Akc;
`
`
`
`temu:amm20:uaamm.355m..$.5.:_.2
`S__xi»xx;H-3.3.3393.9.33§..-,.a.
`
`tcc,_-..oB89.9888%.8.e..m._
`
`
`
`U.
`
`4|-mm
`
`EM
`
`
`
`Pmm:.33moS.ozaflmzd
`
`
`.|.|.|11l|,.Ems#960,:
`
`
`
`
`
`._.<O.EtméQqmim.0..mn._
`
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 11 of 11
`
`5,794,229
`
`PER PAGE
`COMPRESSJON
`
`PAGE HEADER:
`BTYPE: BiTMAP
`CTYPE: RLE
`
`\
`
` 521
`II E E l CTYPE:LZRW1
`
`511
`
`501
`
`PAGE HEADER:
`BTYPE: DATA
`
`PAGE HEADER:
`
`503
`
`1/
`
`
`
`1
`1
`1
`BUD
`D D DD
`
`FIG. 5
`
`

`
`5394.229
`
`1
`DATABASE SYSTEM WITH
`METHODOLOGY FOR STORING A
`DATABASE TABLE BY VERTICALLY
`PARTITIONING ALL COLUDINS OF THE
`TABLE
`
`The present application is a conlinuation—io—part appli-
`cation of comrnonly—owned application Ser. No. 08/048.637.
`filed Apr. 16. 1993. now abandoned. the disclosure of which
`is hereby incorporated by reference.
`
`COPYRIGHT NOTICE
`
`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 docttlnent or the patent
`disclostue as it appears in the Patent and Trademark Ofice
`patent file or records. but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates generally to information
`processing environments and. more particularly. to process-
`ing of queries against information stored in a data processing
`system. such as an SQL Relational Database Management
`System (RDBMS).
`Computers are very powerful tools for storing and pro-
`viding 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
`tnforroation stored as "records" having “fields” of i.nforIna-
`tion. As an example. a database of employees may have a
`record for each employee. Herc. each record contains fields
`designating specifics about the employee. such as name.
`home address. salary. and the like.
`the
`Between the actual physical database itself (i.e..
`records contained in data pages stcred on a storage device)
`and the users of the system. a database management system
`or DBMS is typically provided as a software cushion or
`layer. In essence. the DBMS shields the database user from
`knowing or even caring about underlying hardware-rlevel
`details. ‘Typically. 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 underlying system i.mplcrnent.a-
`tion.
`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 a
`database management system is known in the art. See e.g..
`Date. (3.. An introduction to Database Systems. Volume I
`and II. Addison Wesley. 1990; the disclosure of which is
`hereby incorporated by reference.
`DBMS systems have long since moved lirom a centralized
`mainframe environment to a dc-ocnnalized or distributed
`environment. One or more PC "client" systems. for instance.
`may be connected via a network to one or more server-based
`database systems (SQL database server). Commercial
`examples of these “client!server" systems include Power-
`soflT|-‘ clients connected to one or more Sybase SQL
`Scrver“‘ database servers. Both Powersoffi" and Sybase
`SQL Server?“ are available from Sybase. Inc. of Erneryville.
`Calif. As the migration to clienttlserver continues. each day
`more and more businesses are run from mission-critical
`systems which store information on server-based SQL data-
`
`25
`
`‘SD
`
`45
`
`55
`
`2
`base systems. such as Sybase SQL Server‘'“. As a result
`increasingly higher demands are beig placed on server-
`based SQL database systems to provide enterprise-wide
`decision support—~providing timely on-line access to critical
`business infonnation (e..g.. through "queries“J. Accordingly.
`there is much interest in improving the perforrnance of such
`systems. particularly in the area of database query perfor-
`rnanoe.
`
`the
`'1l'ad.it.ionally. database managernent systems {e.g..
`above-described clientlserver database systems) have been
`employed for on—Line
`transaction processing (0I..'l"P)—
`posting data (from transactions) to a database table. As part
`ofthis process of putting data “in” a database. OLTP systems
`typically process queries which find a single record. or just
`a few records. A typical quay in an OLTP system. for
`instance. might be to retrieve data records for a particular
`customer. such as retrieving records in an airline reservation
`system for Account No. 35. Thus. use of OLTP systems for
`retrieving data has been largely limited to moment-to-
`mornent operational needs. where the queries are relatively
`simple and the number of rows retrieved (relative to table
`size) is few. In other words. OLTP systems have been
`optimized for this task of finding a "needle in a haystacl-:"—
`that is. finding one or few records which meet a given query
`condition.
`More recently. however. there has been great interest in
`“data warehousing." For these Decision Support Systems
`(DSS) applications. database systems are designed not so
`much for putting information “in” {i.e..
`transaction
`processing} but more for getting information “out." The
`general approach to providing DSS has been to take an
`SQ1.-based. OLTP database engine (e.g.. Syhase or Oracle)
`which was really architocted for the OLTP environment {and
`the model that it represents] and attempt to extend that
`engine to handle DSS applications. As a result of the etfort
`to build DSS functionality on top of OLTP database engines.
`the performance of present-day DSS products is generally
`poor. Quite simply. OLTP database engines have been archi-
`tected and optimized for transaction processing to such an
`extent that they are not well-suited for analytical processing.
`Alternatively. some vendors have implemented non-SQL-
`based systems providing DSS capability. These systems
`exist today. in large part. due to the failure of SQI.-based
`database systems at processing DSS tasks. Examples of
`these non-SQI. or "on-line analytical processing" (OLAP)
`systems include Pilot” and Comsharel“. These systems
`employ a non-relational model. one which generally allows
`the user to view the data in a ctlbe-lilo: form. Typically. data
`records are imported from SQL databases and then stored. in
`various proprietary formats. Once transposed from SQL
`format into a particular proprietary format. the information
`is usually maintained on one or more servers for access by
`clients. through a proprietary interface. These systems typi-
`cally employ proprietary clients or front ends as well.
`This approach also entails significant disadvantages. how-
`ever. Users prefer to not have to import andlor transpose
`infcnnalion into various proprietary for-roats. Instead. user
`would rather simply keep the information in SQL database
`tables. There are at least two reasons for this. First.
`the
`information is generally “already dune." having been accu-
`mulated by the posting of transactions over a period of tirne.
`Second. users are already familiar with working with one of
`the main SQL database providas. such as Sybase or Oracle.
`Even if a separate tool is required to implement DSS. users
`prefer to work with tools which are in the same family as the
`tools which they are already using on a day-to-day basis.
`Expectedly. the non-SQI. approach has met with Limited
`success.
`
`

`
`5.794
`
`-4-...
`999
`
`3
`What is needed are system and methods with better DSS
`performance. yet within the traditional SQIJrelational
`rnodel—a model which users demand. From the perspective
`of users. such a system should appear to be essentially an-
`SQL-based relational system. At the same time. however.
`such a system should yield rrtuch-improved DSS perfor-
`mance. The present invention fulfills this and other needs.
`
`SUMMARY OF THE INVENTION
`
`1(2-
`
`The present invention comprises a Clienb’Server Database
`System with improved methods for performing database
`queries. particularly DSS-type queries. In an exemplary
`embodiment. the system includes one or more Clients (e.g..
`Terminals or PCs} connected via a Network to a Server. The
`Server. operati ng under a server operating system (e.g..
`UNIX).
`includes a Database Server System. In general
`operation. Clients store data in and retrieve data from one or
`more database tables resident on the Server by submitting
`SQL cornmands. some of which specify "queries"—critcria
`for selecting particular records of a table.
`According to the present invention. data is not stored in a
`row or a horizontal orientation. as is traditionally done. but
`is instead stored vertically (in. by column). By storing data
`in a column-wise basis. the system of the present invention
`can process a DSS query by bringing in only those columns
`of data which are of interest. A DSS query typically entails
`looking at 50% or greater of the data and often includes
`GROUP BY clauses (e.g.. on State or Gendu) and includes
`SUM. COUNT. and AVG clauses (e.g.. average on
`Revenue). Processing such a query using traditional storage
`methodology is highly inefiiciont. as row-based (horizontal)
`data pages bring in from disk all columns of data. whether
`or not particular columns are of interest to the query. Thus
`for DSS queries. storing data on a column basis by cell is far
`more preferable than storing data in the traditional row or
`record format.
`
`Since the vast majority of information in real-world DSS
`applications is typically low cardinality data (e.g.. State field
`has only 30 unique values. the majority of the columns of a
`typical DSS table will store low cardinality data on each
`vertical data page. As a result. repetition within a particular
`column is quite high. thus leading to far better compression
`of data pages than can be realized than with row-based
`stcnge. The nature of the data encountered.
`therefore.
`fimhcr enhances the advantages of colun1n—wise storage or
`vertical partitioning.
`In a typical DSS quay. a database system needs to bring
`in large amounts of inforrnalionz these queries typically look
`at a large percentage of the database. If the data pages
`actually brought in for the DSS query are populated largely
`or completely with information necessary for the query. then
`H0 block size may be increased to a level which is optimal
`for the envirorunentlplatforrn. such as to a level of 64K data
`pages. More particularly. by storing information in a
`coIurn.n—based format.
`in accordance with the present
`invention. a high saturation level of iltforrnation [such as
`required by a DSS query) can be etliciently met. Instead of
`retrieving row-based data pages consisting of information
`which is largely not of interest to a query. column-based
`pages can be retrieved consisting of information which is
`mostly.
`if not completely. of interest to the query. The
`retrieval itself can be done using more-efficient large block
`HO transfers.
`
`In the system of the present invention. from an SQL
`system catalog. the system can detennine a chain of columns
`which represent a particular table. Specifically. from the
`
`45
`
`55
`
`65
`
`4
`chain of columns. the system can represent a logical table to
`the user. Here. the concept of a "table" in the system of the
`present
`invention is purely a catalog logical entry. as
`opposed to a physical entity in which it traditionally exists.
`The columns are “tied together" logically to represent a
`table. From the perspective of the user. however. the vertical
`partitioning is transparent.
`Each column comprises a plurality of “cells” (i.e.. column
`value for a record). which are arranged on a data page in a
`contiguous fashion. For fixed-length fields {e.g.. two char-
`acter Slatc field). the ofiset of any particular cell on a page
`can be quickly computed as a modulus of that cell (adjusted
`for any header information to the page). Between the indi-
`vidual cells. there is no overhead information. in contrast to
`sevaal row—based implementations. Since the cells.
`in
`essence. exist as a solid stream of data. column scans are
`particularly enicient.
`The pages are further optimized for compression by
`storing in the page header‘ 3. status flag indicating whether the
`data page is a candidate for oolznprcssion and (optionally)
`what type of compression is best suited for the data on that
`page. Since this is senable on a page-by-page basis. one
`particular compression technique can be applied on one
`column yet at the same time another compression technique
`applied on another’ column (or a d.ifl’erent part of the same
`column}. all within the same (logical) table.
`Data compression is added to the system at the level ofdte
`Cache or Bufier Managers. It is preferable to isolate com-
`pression here so that each object need not be concerned
`about compressing itself (or even being aware that compres-
`sion is occurring]. As a resulL compression is tranwenlly
`added to all data objects managed by Bu:fi'er Managers. The
`data pages of an object are compressed when sent out to disk
`and decompressed when retrieved Erorn disk. yet the object
`itself is unaware of this action.
`
`Most objects within the system. such as tables. indexes.
`logs. and die like. exist as pages. As these objects are
`streamed to disk. each simply requests its Buffer Manager to
`store the object on disk. The Manager in turn stores the
`object on disk using the best cornpresnon methodology
`lcnown to it. for the given object. In this manner. data
`compression is transparent to the data objects above the
`level of the Buficr Manager.
`To address the potential problem of a modified block no
`longer compressing back down to its original size. a “block
`map" is employed in the system of the present invention.
`Wiflain a Bufier Manager. there can be as many instances of
`a block map as needed. Typically. one exists per object (or
`portion thereof}. For instance. one block map can exist pa
`B—'ll'ce. or one per portion of a B-Tree (e.g.. non-leaf level
`pages). Each block map. in turn. may be thought of as a
`logical-to-physical translator for the object (or subnbject}
`which is its focus. In this manner. the system can concentrate
`on bringing in the object (or portion of the object) which is
`needed. Each page number providedto a client serves as an
`index into the corresponding block map for determining the
`actual physical page number. For implcmentalzions without
`compression. this translator may be eliminated.
`BRIEF DESCRIPTION OF Tl-IE DRAWINGS
`
`FIG. IA is a bloclrdiagraun of a computer system in which
`the present invention may be embodied.
`FIG. 1B is a block diagram of a software subsystem for
`controlling the operation of the computer system of FIG- 1A.
`FIG. 2 is a block diagram of II. clientfservcr system in
`which the present invention is preferably embodied.
`
`

`
`5 .79-1.229
`
`5
`FIGS. SA-C are diagrams illustrating column-based data
`storage or “vertical partitioning." which is employed for
`storing data tables in the system of the present invention.
`FIGS. -t|A—D are diagram illustrating "natural data reduc-
`tion” compression of data types which would otherwise
`include unused bits: natural data reduction may be combined
`with other compression methodologies. as shown particu-
`larly in FIG. 415.
`FIG. 5 is a diagram illustrating per page compression
`rnethodology of die present invention. which allows di.lfer-
`ent compression methodology to be applied to diiferent data
`pages {of either dillerent page chains or even within the
`same page chain].
`DE"l"AIl..ED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`The following description will focus on the presently
`pueferred embodiment of the present invention. which is
`operative in a network environment executing clientfserver
`database applications. The present invention. however. is not
`limited to any particular application or environment Instead.
`those skilled in the art will find that the present invention
`may be advantageously applied to any application or envi-
`ronment where optimization of query performance is
`desirable. including non-SQL database management sys-
`tems and the like. The description of the exemplary embodi-
`ments which follows is. therefore. for the purpose of illus-
`tration and not limitation.
`Standalone System Hardware
`The invention may be embodied on a computer system
`such as the system l00 of FIG. 1A. which comprises a
`central processor 101. a main memory 102. an inputfoutput
`controller 103. a keyboard 104. a pointing device 105 (e.g..
`mouse. naclt ball. pen device. or the like). a screen display
`device 106. and a mass storage 107 te.g.. hard or fixed disk.
`removable disk. optical disk. magneto-optical disk. cr flash
`memory). Processor 101 includes or is coupled to a cache
`memory 109 for storing frequently accessed information:
`memory 109 may be an on-chip cache or external cache (as
`shown]. Additional output devicetsl 103. such as a. printing
`device. may be included in the system 100 as desired. As
`shown. the various components of the system 100 commu-
`nicate through a system bus 110 or similar architecture. In a
`lxeferred embodiment. the system 100 includes an IBM-
`cornpatible personal computer system. available from It
`variety of vendors (including IBM ofArmonlr.. N.Y.).
`Standalone System Software
`Illustrated in FIG. LB. a computer software system 150 is
`provided for directing the operation of the computer system
`100. Software system 150. which is stored in system
`memory 102 and on mass storage or disk memory 107.
`includes a kernel or operating system (05) 140 and a
`windows shell 145. One or more application programs. such
`as application software programs 155. may be "loaded" {i.e..
`transferred frorn storage 107 into memory 102) for execu-
`tion by the system I00. The system also Includes a user
`interface 160 for receiving user commands and data as input
`and displaying result data as output.
`Also shown. the software system 150 includes a Rela-
`tional Database Man-agernent System (RDBMS) front-end
`or "client" 170. The RDB-MS client 17!} may be any one of
`a number" of database front-ends. including Powerfluilderfl‘.
`dBA.SE®. Paradox®. Mic1'osoft® Access. or the like. In an
`exemplary embodiment. the front-end will include SQL
`access drivers {e.g.. Borland SQL Links. Microsoft ODBC
`drivers. Intersolv ODBC drivers. and the like) for accessing
`database tables from an SQL database server operating in a
`Client}Server environment.
`
`25
`
`35
`
`55
`
`65
`
`6
`Client!'Server Database Management System
`While the present invention may operate within a single
`{standalone} computer (e.g.. system Hill of FIG. 1A). the
`present invention is preferably embodied in a multi-user
`computer system. such as a Clientfserver system. FIG. 2
`illustrates the general structure of a Clienttserver Database
`System 200 suitable for implementing the present invention.
`As shown. the system 200 comprises one or more Client-(s)
`210 connected to a Server 230 via a Network 220.
`Specifically. the Client(s) 210 comprise one or more stan-
`dalone ‘Terminals 211 connected to a Database Server Sys-
`tem 240 using a conventional network. In an exemplary
`embodiment. the Terminals 2.11 may themselves comprise a
`plurality of standalone workstations. dumb tennina.ls. or the
`like. or comprise personal computers (PCs) such as the
`above-described system 1041. Typically. such units would
`operate under a client operating system. such as Microsoft
`vruidowsIMS-D-OS for PC clients.
`The Database Server System 240. which comprises
`Sybase SQI. Server" (available from Sybase. Inc. of
`Erneryville. Calif.) in an exemplary embodiment. generally
`operates as an independent process (is... independently or
`the Clients). waning under a server operating system such as
`Microsoft Windows NT (Microsoft Corp. of Redmond.
`Wash). Netware {Novell of Provo. UT). UNIX {Nove.ll). or
`OS.?2 (IBM). The Network 220 may be any one of a number
`of conventional network systems. including a Local Area
`Network (LAN,1 or Wide Area Network (WAN,1. as is known
`in the an te.g.. using Ethernet. IBM Token Ring. or the like).
`The Network includes functionality for packaging client
`calls in the well-known SQL {Structured Query Language)
`together with any parameter information into a format (of
`one or more packets) suitable for n-ansmission across a cable
`or wire. for delivery to the Database Server System 240.
`Clienuserver environments. database servers. and net-
`works are well documented in the technical. trade. and
`patent literature. For a discussion of database servers and
`clientlserver environments generally. and SQL Server"
`particularly. see. e.g.. Nadi. A.. The Guide to SQL Server.
`Second Edition. Addison-Wesley Publishing Company.
`1995. Additional documentation of SQL Server“-| is avail-
`able from Sybase. Inc. as SQL Server Documentation Set
`(Catalog No. 49600). For a discussion of a computer net-
`work employing Microsoft Networksl0penN-et File Sharing
`Protocol. see METHOD AND SY5'l'EM FDR O1IPon'nn~ns11c
`Locrcmo us A NEIWORKED Counrrnn SYSTEM. Intl. Appli-
`cation No. PCl'R.IS90!ll-$570.
`lntl. Publication No. W0
`9l!03ll24. Inll. Publication Date Mar. 7. I991. For a general
`introduction to a Local Area Nctwcrk operating under
`Netware. see Freed. L. et al.. PC Magazine Guide to Using
`Nerlihre. Zifl-Davis Press. 1991. A more detailed discussion
`is available in Neiware 3.x and 4.x and accompanying
`documentation. which is available from Novcll of Provo.
`UT. The disclosures of each of the foregoing are hereby
`incorporated by reference.
`In operation. the Client{s) 210 store data in or retrieve
`data from one or more database tables 30. shown in FIG.
`2. Typically resident on the Servo: 230. each table itself
`comprises one or more horizontal rows or “records” (triples)
`together with vertical columns or "fields.“ Adatabase record
`includes information which is most conveniently repre-
`sented as a single unit. A reccrd for an employee. for
`example. may include information about the employee's ID
`Number. Last Name and First initial. Position. Date Hired.
`Social Security Ntunber. and Salary. Thus. a typical record
`includes several categories of information about an indi-
`vidual person. place. or thing. Each of these categories. in
`
`

`
`5.794.229
`
`7
`turn. represents a database field. In the foregoing employee
`table. for example. Position is one field. Date Hired is
`another. and so on. With this format. tables are easy for users
`to understand and use. Moreover. the flexibility of tables
`permits a user to define relationships between various items
`of data. as needed.
`In operation. the Clientts) issue one or more SQL com-
`mands to the Server. SQI. commands may specify. for
`instance a query for retrieving particular data (i.e.. data
`records meeting the query condition) from the table 250. The
`syntax of SQL (Structured Query Language) is well docu»
`mentcd; see. c.g.. the ahovomentioned An Introduction to
`Database Systems. In addition to retrieving the data from
`Database. Server tables. the Clicnt(s) also include the ability
`to insert new rows of data records into the table: Clientts)
`can also modify andlor delete existing records in the table.
`For enhancing the speed in which the Database Server
`stores. retrieves. and presents particular data records. the
`Server maintnins one or more database indexes 271 on the
`table. under control of an Index Manager. Actatahase index.
`typimlly maintained as a B-Tree data st:ructI.IIc.. allows the
`records of a table to be organized in many dilfereut ways.
`depending on a particular user's needs. An index may be
`constructed as a single disk file stcring index key values
`together with unique record numbers. The former is a data
`quantity composed of one or more fields from a record: the
`values are used to arrange (logically) the database file
`records by some desired order (index expression)- The latter
`are unique pointers or identifiers to the actual storage
`location oi each record in the database tile. Both arereferred
`to internally by the system for locating and displaying
`records in a database file. Alternatively. instead of storing
`unique record numbers. a “clustercd" index may be
`employed. This is an index which stores the data pages ofthe
`records themselves on til: terminal or leaf-level nodes of the
`index.
`In operation. the SQL statements received from the one or
`more Clients 210 (via Network 220) are processed by
`Engine 260 of the Database Server System 2910. The Engine
`260 itself comprises a Parser 261. Nornalizer 263. Compiler
`265. Execution Unit 269. Access Methods 270. and Bufier
`Manager(s) 272. Specifically. the SQL statements are passed
`to the Pwser 261 which converts the statements into a query
`trce—a binary tree data strI.tct1u'c which represents the
`components of the query in a format selected for the
`convenience of the system. In this regard. the Parser 261
`employs conventional parsing methodology (e.g.. recursive
`descent parsing).
`The query tree is ncnnalized by the Normalize: 263.
`Nonualizatlon includes. for example. the elimination of
`redundant data. Additionally. the Normalize: 266 performs
`error checking. such as confirming that table names and
`column names which appear in the query are valid (e.g.. are
`available and belong together). Finally. the Nornalizcr can
`also look up any referential integrity constraints which exist
`and add those to the query.
`After normalization.
`the query tree is passed to the
`Compiler 265. which includes an Optimizer 2156 and a Code
`Generator 267. The Optimizer is responsible for optimizing
`the query tree. The Optimizer performs a cost-based analysis
`for formulating a query execution plan. The Optimizer will.
`for instance. select the join order of tables (e.g.. when
`working with more than one table): it will select relevant
`indexes {e.g.. when indexes are available}. The Optimizer.
`therefore. performs an analysis of the query and picks the
`best execution plan. which in mm results in particular ones
`of the Access Methods 210 being invoked during query
`execution.
`
`I6
`
`20
`
`35
`
`45
`
`SD
`
`65
`
`8
`The Code Generator 2.67. on the other hand. converts the
`quay tree into a set of instructions suitable for satisfying the
`query. These instructions are passed to the Execution Unit
`269. Operating undo" the control of these instructions. the
`Execution Unit 269 generates calls into lower-level routines.
`such as the Access Methods 2'30. for retrieving relevant
`information (e.g.. row 255) from the database table 250. The
`Acc