United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,794,229
`
`French et a1.
`
`[45] Date of Patent:
`
`Aug. 11, 1998
`
`USOOS794229A
`
`[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.. Emeryville. Calif.
`
`[21] Appl. No.: 570,183
`
`[22] Filed:
`
`Dec. 11, 1995
`
`Related US. Application Data
`
`[63] Continuation-impart of Ser, No. 48,637, Apr. 16, 1993,
`abandoned.
`
`Int. CL" ...................................................... G06F 17/30
`[51]
`[52] US. Cl. ..................................... 707/2; 707/3; 707/10;
`707/205; 711/100; 711/171; 705/35
`[58] Field of Search ..................................... 395/601—612.
`395/603; 707/2. 3. 10. 205; 705/35; 711/100.
`171
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,606,002
`4,677,550
`4,776,026
`5,153,591
`5,293,616
`5,377,348
`5,404,510
`5,495,608
`5,649,181
`
`....................... 395/603
`8/1986 Waisman et a1.
`395/600
`6/1987 Ferguson
`10/1988 Ueyama ............ 382/46
`10/1992 Clark ................. 341/51
`3/1994 Flint ................ 395/601
`12/1994 Lau et a1,
`395/603
`4/1995 Smith et a1.
`395/601
`2/1996 Antoshenkov .
`395/601
`7/1997 French et a].
`........................... 395/603
`
`
`
`OTHER PUBLICATIONS
`
`“A Transaction—Based Approach to Vertical Partitioning for
`Relational Database Systems”. Chu et al.. IEEE. v19. n8.
`IEEE Transaction of Software Engineering. Aug. 1993.
`“RDBMS Maturity”. Philip A. Naecker. DEC Professional.
`v10. n12. p. 44(6) [Available—Online; Dialog File 275]. Nov.
`1991.
`
`“Ingres Table Sructures”. David Snellen. DBMS. v5. n8. p.
`60(3) IAvailable: On—Line; Dialog File 275l. Jul. 1992.
`Reinartz. K.. “Aspects of vertical mode in multiprocessor
`systems, unconventional computation on conventional pro-
`cessors,” Second International Specalist 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.
`Hanson—Smith. Ltd.. “Advantage Series System Overview,
`Ver. 2.0.” 1990. pp. 1—132.
`
`Primary Examiner—Thomas G. Black
`Assistant Examiner—Hosain T. Alam
`
`Attorney, Agent, or Firm—lohn A. Smart
`
`[57]
`
`ABSTRACT
`
`A Client/Server Database System with improved methods
`for performing database queries. particularly DSS-type
`queries.
`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 “queries”—criteria for selecting particular records
`of a table. The system implements methods for storing data
`vertically (i.e.. by column). instead of horizontally (i.e.. by
`row) as is traditionally done. 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. By
`storing data in a column-wise basis. the system can process
`a DSS query by bringing in only those 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 completely.
`of interest to the query. The retrieval itself can be done using
`more-efficient large block I/O transfers. The system includes
`data compression which is provided at the level of Cache or
`Buffer 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
`
`FIELDS:
`
`CUSTOMERS TABLE
`(LOG/CAL VtEW)
`-———--——ni
`1UDOMING ANYTOWN
`MA
`J. FISH
`
`
`ALLEN
`0, BER!)
`130 MAIN ST.
`
`BEEV1LLE
`X. LVON
`1111 CENTER
`
`
`
`ENERYVlLLE CA
`I SNELL 1 SYBASE LN
`
`KENT
`F MC FLY 22 WORTH LN.
`
`
`
`COLUMNVBASED ERTICAL)
`DATAST AGE
`
`
`
`
`360
`
`PG
`
`-‘w 10.95-
`1’35]
`PG
`1 370
`—.______ PAGE CHAIN
`355
`
`
`
`380
`
`Commvault Ex. 1030
`Commvault v. Realtime
`
`US Patent No. 9,054,728
`
`Page 1
`
`Page 1
`
`Commvault Ex. 1030
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 1 of 11
`
`5,794,229
`
`E
`
`104
`
`KEYBOARD
`
`
`
`POINTING
`DEVICE
`
`105
`
`106
`
`SCREEN
`DISPLAY
`
`
`
`107
`
`103
`
`MASS
`STORAGE
`
`OUTPUT
`DEVICE
`
`"’2
`
`103
`
`MAIN
`MEMORY
`
`IIO
`CONTROLLER
`
`
`
`no
`
`FIG. 1A
`
`101
`
`CENTRAL
`PROCESSOR
`
`CACHE
`MEMORY
`
`lllllllllll
`
`109
`
`Page 2
`
`Page 2
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 2 of 11
`
`5,794,229
`
`a
`
`mum:
`
`wo<u_mm.r2_
`
`Alllll'
`
`m>>ooz_>>
`
`.jmzm
`
`mm?o:
`
`zo_.2o_._n_n_<
`
`avzémomm
`
`mzmnm
`
`._.2m=._o
`
`mum:
`
`
`
`m3.zwhm>wOz:.<mm_n_o
`
`o3.
`
`
`
`mfi.GE
`
`Page 3
`
`Page 3
`
`
`
`
`

`

`US. Patent
`
`g
`
`m03whS
`
`5,794,229
`
`N S
`
`2-
`LL
`
`Page 4
`
`omm
`
`mmmI
`
`
`
`magmamag/ED
`
`
`
`80sz382EN
`
`$55.50.8“
`E4528.mg
`
`IL
`
`Ema
`
`aEammm
`
`.__._.___—..._._..._._.__._____
`
`SN
`
`”Emma
`
`8N
`
`mum
`
`meEmz
`
`omw
`
`@520
`
`on
`
`
`%mmo<z<zmEamxmoz$53502am
`M556com
`u.am
` wmmo<z<21&quNR
`
`-:2:20.50memm
`
`age:mokémzmw38gm
`mo6on
`
`All]
`855am
`
`_______..__............._..__.
`
`E.N
`
`aj<z_2mE
`
`Page 4
`
`

`

`US. Patent
`
`uA
`
`g
`
`8w
`
`n04
`
`9
`
`
`
`was$3058
`
`SE#9on
`
`
`
`022282._mam:macs.caaggggégg“mew:
`
`<2226572
`
`
`
`Acom.855mEan3528on83m.38
`
`wagilflallla&$58::EIfl-EIIIE
`EEG-Hglllllg
`
`
`
`8m2m
`
`SEmismmmE55:2.
`
`.5222o:.
`
`<0mjséwgm3mafia.323
`
`E?.24SmogmmE02.n_
`
`n.4,Eat98m7922:0me5an
`
`
`
`on.
`
`Page 5
`
`Page 5
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 5 of 11
`
`5,794,229
`
` SE:#98a39:mEEEm8
`
`
`
`....memEmoEgEagggéga8mm
`
`
`
`2>>Oh>z<022500or
`
`com355%amm<m§38
`
`m0<Ohm.«53
`
`Em
`
`owncum
`
`onNat;
`
`Igaggag
`
`on.
`
`mmm
`
`m2310wail
`
`
`mm.QE
`
`Page 6
`
`
`
`m...=>mmmmmhzwo2,:
`
`
`
`
`
`..sz.24FED;mmin05.m<0m._.__>>mms_m2..mm<m>mvjmzmH
`
`Hm22.2o?
`
`Page 6
`
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 6 of 11
`
`5,794,229
`
`HESmumsokmso
`
`#053
`
` SE:
`
`
`
`_._.mewfimozoaEgggggggmam:
`
`
`
`Z>>O._.>z<Oz_2>>ooE
`
`Hm22—2om?
`
`oom
`
`
`mg05SE
`
`355%32m.2238
`
`<0m:.=>>mms_mz._mw<m>mF.3waHm3.=>mmm
`mwhzmoS:.
`
`
`
`hzmx.2._I._.m_0>>mmXE0.2.n.
`
`3m
`
`A2310mega
`
`
`Km
`
`Em5m
`
`2RE;
`
`Iaagagg
`
`0m
`
`0mGE
`
`Page 7
`
`Page 7
`
`
`
`
`
`

`

`US. Patent
`
`m
`
`4<mbs<2
`
`
`
`ZOEQDQmm«EB
`
`
`
`«8.8858«ammvfiokmwmy
`
`5,0:.
`
`7
`
`9n
`
`Mn,3‘at
`
`
`85:8:E.......%88.8888....3.m8:8::888:888:888.
`1,:88::88880.:.88888.
`1..988::8o8.:888....88.Tilllll
`
`”mIEEEEE222::7828:zwm5\en”\8828meme
`
`
`505m.“00:.or:SnTilllllls:22::
`
`5:8::
`
`Page 8
`
`Page 8
`
`
`

`

`US. Patent
`
`009w
`
`1f08ae
`
`nomv
`
`
`
`9”SeammEzoo:53»S:
`
`10.3EQmmExoo3:Mmom.qo2.
`
`NzoammEsooEmmiEx$255:
`
`zo‘mmmmlécoK36
`
`I:2a::229:z322::
`
`3E;
`
`7.,5
`
`1as.
`
`
`
`Nzoxmmmmmsoo.35
`
`w
`
`498%
`
`2,mvat
`
`Page 9
`
`E
`
`Page 9
`
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 9 of 11
`
`5,794,229
`
`4<m3k<2
`
`20:0qu1«55
`
`
`
`mmwmtshm-mm
`
`3mmmm;
`
`
`
`Sm:$28.:
`
`
`
`
`
`oSoEco.88o33Boo.oooooooooooococo.7.._
`
`
`Soc85.cocoo.2.08So....o88.
`8:Soc.8880082..:50800oooo.
`
`:8$00....oooococo88008..2.
`
`
`
`0».GE
`
`Page 10
`
`Page 10
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 10 of 11
`
`5,794,229
`
`803:5
`
`2058:8580
`
`
`Kitxx;mHmmmnfiwfiw»xxxxXE,.8888a28888809
`OZEMHmeOxx>>>>>>oo:«.5oooooo::8Coco“
`E;E;.88888888o8.3:"
`
`v9;xx;........................
`
`Eézaxqo
`
`$085205:SESE
`
`3882
`
`_II||.|I|||IIIIJ_
`
`azimtwbqo
`
`mm:.~<>m0
`
`55¢29%
`
`8mmmoan
`
`8m:35%
`
`Page 11
`
`Page 11
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1993
`
`Sheet 11 of 11
`
`5,794,229
`
`PER PAGE
`COMPRESSION
`
`PAGE HEADER:
`BTYPE: BITMAP
`CTYPE: RLE
`
`\
`
`E
`
`511
`
`PAGE HEADER:
`BTYPE: DATA
`CTYPE: LZRW1
`
`i
`
`
`
`521
`
`501
`
`503
`
`PAGE HEADER:
`
`BTYPE: DATA
`
`CTYPE: sz
`
`-~/
`
`
`
`iiiim
`mama
`
`FIG. 5
`
`Page 12
`
`Page 12
`
`

`

`1794229
`
`1
`DATABASE SYSTEM WITH
`METHODOLOGY FOR STORING A
`DATABASE TABLE BY VERTICALLY
`PARTITIONING ALL COLUMNS OF THE
`TABLE
`
`The present application is a continuation-in-part appli—
`cation of commonly—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 document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records. but otherwise reserves all copyright
`rights whatsoever.
`
`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
`information stored as “recor
`” having “fields” of informa-
`tion. As an example. a database of employees may have a
`record for each employee. Here. 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 stored 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-level
`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 implementa-
`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. C.. 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 from a centralized
`mainframe environment to a de-centralized 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-
`softTM clients connected to one or more Sybase SQL
`ServerTM database servers. Both PowersoftTM and Sybase
`SQL ServerTM are available from Sybase. Inc. of Emeryville.
`Calif. As the migration to client/server continues. each day
`more and more businesses are run from mission-critical
`systems which store information on server-based SQL data-
`
`2
`base systems. such as Sybase SQL Server”. As a result.
`increasingly higher demands are being placed on server-
`based SQL database systems to provide enterprise-wide
`decision support—providing timely on-line access to critical
`business information (e.g.. through “queries”). Accordingly.
`there is much interest in improving the performance of such
`systems. particularly in the area of database query perfor-
`mance.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`the
`Traditionally. database management systems (e. g..
`above-described client/server database systems) have been
`employed for on-line transaction processing (OLTP)—
`posting data (from transactions) to a database table. As part
`of this process of putting data “in” a database. OLTP systems
`typically process queries which find a single record. or just
`a few records. A typical query 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-
`moment 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 haystack”—
`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
`SQL-based. OLTP database engine (e.g.. Sybase or Oracle)
`which was really architected 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 effort
`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 SQL-based
`database systems at processing DSS tasks. Examples of
`these non-SQL or “on—line analytical processing” (OLAP)
`systems include PilotTM and Comsharem. These systems
`employ a non-relational model. one which generally allows
`the user to view the data in a cube-like 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
`cheats. 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 and/or transpose
`information into various proprietary formats. 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 there.” having been accu-
`mulated by the posting of transactions over a period of time.
`Second. users are already familiar with working with one of
`the main SQL database providers. 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-SQL approach has met with limited
`success.
`
`Page 13
`
`Page 13
`
`

`

`3
`
`4
`
`5.794.229
`
`What is needed are system and methods with better DSS
`performance. yet within the traditional SQL/relational
`model-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 much—improved DSS perfor-
`mance. The present invention fulfills this and other needs.
`
`SUMMARY OF THE INVENTION
`
`The present invention comprises a Client/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. operating 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 commands. some of which specify “queries”—criteria
`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 (i.e.. 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 Gender) and includes
`SUM. COUNT. and AVG clauses (e.g.. average on
`Revenue). Processing such a query using traditional storage
`methodology is highly inefficient. 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 50 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
`storage. The nature of the data encountered.
`therefore.
`further enhances the advantages of column-wise storage or
`vertical partitioning.
`In a typical DSS query. a database system needs to bring
`in large amounts of information; 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
`110 block size may be increased to a level which is optimal
`for the environment/platform. such as to a level of 64K data
`pages. More particularly. by storing information in a
`column—based format.
`in accordance with the present
`invention. a high saturation level of information (such as
`required by a DSS query) can be efficiently 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
`I/O transfers.
`
`In the system of the present invention. from an SQL
`system catalog. the system can determine a chain of columns
`which represent a particular table. Specifically. from the
`
`10
`
`15
`
`20
`
`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 State field). the offset 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
`several row-based implementations. Since the cells.
`in
`essence. exist as a solid stream of data. column scans are
`particularly efficient.
`The pages are further optimized for compression by
`storing in the page header a status flag indicating whether the
`data page is a candidate for compression and (optionally)
`what type of compression is best suited for the data on that
`, page. Since this is settable 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 difierent part of the same
`column). all within the same (logical) table.
`Data compression is added to the system at the level of the
`Cache or Buffer 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 result. compression is transparently
`added to all data objects managed by Buifer Managers. The
`data pages of an object are compressed when sent out to disk
`and decompressed when retrieved from disk. yet the object
`itself is unaware of this action.
`
`25
`
`30
`
`35
`
`Most objects within the system. such as tables. indexes.
`logs. and the 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 compression methodology
`known to it. for the given object. In this manner. data
`compression is transparent to the data objects above the
`level of the Buffer 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.
`Within a Buffer 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 per
`B-Tree. 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 subobject)
`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 provided to a client serves as an
`index into the corresponding block map for determining the
`actual physical page number. For implementations without
`compression. this translator may be eliminated.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A is a block diagram 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 a client/server system in
`which the present invention is preferably embodied.
`
`45
`
`55
`
`65
`
`Page 14
`
`Page 14
`
`

`

`5.794.229
`
`5
`FIGS. 3A—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. 4A—D are diagrams 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. 4B.
`FIG. 5 is a diagram illustrating per page compression
`methodology of the present invention. which allows differ-
`ent compression methodology to be applied to different data
`pages (of either different page chains or even within the
`same page chain).
`DETAJLED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`The following description will focus on the presently
`preferred embodiment of the present invention. which is
`operative in a network environment executing client/server
`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 100 of FIG. 1A. which comprises a
`central processor 101. a main memory 102. an input/output
`controller 103. a keyboard 104. a pointing device 105 (e.g..
`mouse. track ball. pen device. or the like). a screen display
`device 106. and a mass storage 107 (e.g.. hard or fixed disk.
`removable disk. optical disk. magneto-optical disk. or 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 device(s) 108. 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
`preferred embodiment. the system 100 includes an IBM-
`compatible personal computer system. available from a
`variety of vendors (including IBM of Armonk. N.Y.).
`Standalone System Software
`Illustrated in FIG. 1B. 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 (OS) 140 and a
`windows shell 145. One or more application programs. such
`as application software programs 155. may be “loaded” (i.e..
`transferred from storage 107 into memory 102) for execu-
`tion by the system 100. 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 Management System (RDBMS) front-end
`or “client” 170. The RDBMS client 170 may be any one of
`a number of database front-ends. including PowerBuilderm.
`dBASE®. Paradox®. Microsoft® 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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`6
`Client/Server Database Management System
`While the present invention may operate within a single
`(standalone) computer (e.g.. system 100 of FIG. 1A). the
`present invention is preferably embodied in a multi-user
`computer system. such as a Client/Server system. FIG. 2
`illustrates the general structure of a Client/Server 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 211 may themselves comprise a
`plurality of standalone workstations. dumb terminals. or the
`like. or comprise personal computers (PCs) such as the
`above—described system 100. Typically. such units would
`operate under a client operating system. such as Microsoft
`Windows/MS-DOS for PC clients.
`The Database Server System 240. which comprises
`Sybase SQL Serverm (available from Sybase. Inc. of
`Emeryville. Calif.) in an exemplary embodiment. generally
`operates as an independent process (i.e.. independently of
`the Clients). running under a server operating system such as
`Microsoft Windows NT (Microsoft Corp. of Redmond.
`Wash). NetWare (Novell of Provo. UT). UNIX (Novell). or
`OS/2 (IBM). The Network 220 may be any one of a number
`of conventional network systems. including a Local Area
`Network (LAN) or Wide Area Network (WAN). as is known
`in the art (e.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 transmission across a cable
`or wire. for delivery to the Database Server System 240.
`Client/server environments. database servers. and net-
`works are well documented in the technical. trade. and
`patent literature. For a discussion of database servers and
`client/server environments generally. and SQL Serverm
`particularly. see. e.g.. Nath. A.. The Guide to SQL Server.
`Second Edition. Addison-Wesley Publishing Company.
`1995. Additional documentation of SQL ServerTM is avail-
`able from Sybase. Inc. as SQL Server Documentation Set
`(Catalog No. 49600). For a discussion of a computer net-
`work employing Microsoft Networks/OpenNet File Sharing
`Protocol. see METHOD AND SYSTEM FOR OPPORTUNISTIC
`LOCKING IN A NEI'WORKED COMPUTER SYSTEM. Intl. Appli—
`cation No. PCT/US90/04570. Intl. Publication No. WO
`91/03024. Int]. Publication Date Mar. 7. 1991. For a general
`introduction to a Local Area Network operating under
`NetWare. see Freed. L. et al.. PC Magazine Guide to Using
`NetWare. Ziff-Davis Press. 1991. A more detailed discussion
`is available in NetWare 3.x and 4.x and accompanying
`documentation. which is available from Novel] 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 250. shown in FIG.
`2. Typically resident on the Server 230. each table itself
`comprises one or more horizontal rows or “records” (tuples)
`together with vertical columns or “fields.” A database record
`includes information which is most conveniently repre-
`sented as a single unit. A record for an employee. for
`example. may include information about the employee’s ID
`Number. Last Name and First Initial. Position. Date Hired.
`Social Security Number. and Salary. Thus. a typical record
`includes several categories of information about an indi—
`vidual person. place. or thing. Each of these categories. in
`
`Page 15
`
`Page 15
`
`

`

`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 Client(s) issue one or more SQL com—
`mands to the Server. SQL 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~
`merited; see. e.g.. the above-mentioned An Introduction to
`Database Systems. In addition to retrieving the data from
`Database Server tables. the Client(s) also include the ability
`to insert new rows of data records into the table; Client(s)
`can also modify and/or delete existing records in the table.
`For enhancing the speed in which the Database Server
`stores. retrieves. and presents particular data records. the
`Server maintains one or more database indexes 271 on the
`table. under control of an Index Manager. A database index.
`typically maintained as a B-Tree data structure. allows the
`records of a table to be organized in many different ways.
`depending on a particular user’s needs. An index may be
`constructed as a single disk file storing 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 of each record in the database file. Both are referred
`
`to internally by the system for locating and displaying
`records in a database file. Alternatively. instead of storing
`unique record numbers. a “clustered” index may be
`employed. This is an index which stores the data pages of the
`records themselves on the 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 240. The Engine
`260 itself comprises a Parser 261. Nornalizer 263. Compiler
`265. Execution Unit 269. Access Methods 270. and Buffer
`Manager(s) 272. Specifically. the SQL statements are passed
`to the Parser 261 which converts the statements into a query
`tree—a binary tree data structure 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 normalized by the Normalizer 263.
`Normalization includes. for example.
`the elimination of
`redundant data. Additionally. the Normalizer 263 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 Nornalizer 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 266 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