Source: http://www.google.com/patents/US7058783?dq=5083039
Timestamp: 2016-05-02 02:30:23
Document Index: 57571879

Matched Legal Cases: ['art 1', 'art1', 'art 2', 'art2', 'art 3', 'art3']

Patent US7058783 - Method and mechanism for on-line data compression and in-place updates - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA method and mechanism is disclosed for implementing storage and compression in a computer system. Each granular portion of a file can be individually stored in either a compressed storage unit or an uncompressed storage unit. The storage units can be allocated apriori or on an as-needed basis....http://www.google.com/patents/US7058783?utm_source=gb-gplus-sharePatent US7058783 - Method and mechanism for on-line data compression and in-place updatesAdvanced Patent SearchPublication numberUS7058783 B2Publication typeGrantApplication numberUS 10/246,964Publication dateJun 6, 2006Filing dateSep 18, 2002Priority dateSep 18, 2002Fee statusPaidAlso published asUS7451290, US20040054858, US20060212672Publication number10246964, 246964, US 7058783 B2, US 7058783B2, US-B2-7058783, US7058783 B2, US7058783B2InventorsSashikanth Chandrasekaran, Angelo PruscinoOriginal AssigneeOracle International CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (29), Non-Patent Citations (32), Referenced by (36), Classifications (17), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetMethod and mechanism for on-line data compression and in-place updates
US 7058783 B2Abstract
A method and mechanism is disclosed for implementing storage and compression in a computer system. Each granular portion of a file can be individually stored in either a compressed storage unit or an uncompressed storage unit. The storage units can be allocated apriori or on an as-needed basis.
The invention relates to computer systems, and more particularly to a method and mechanism for implementing compression in a computer system.
Another approach is to employ content-specific or language-specific granularities when compressing data. In a database context, this approach allows compression and decompression at the level of a tuple or level of individual fields/columns of a database object. In implementation, the “language” layer of a computer system (e.g., the computing layer that processes Structured Query Language or SQL commands in a database system) can be modified to perform compression or decompression based upon the known structure or schema of the data. An advantage with this approach is that smaller granularities of data can be decompressed when accessing data, rather than requiring an entire file of data to be decompressed to access a small portion of the desired data records. However, this approach requires the compression scheme to be directly influenced and possibly specific to a particular data schema used to organize the data. This can significantly affect the maintainability of that data, since the compression scheme may necessarily require updating when a change occurs to the corresponding data schema, e.g., the compression scheme changes if modifications are made to the type, number or order of fields in a database table. The query operators may also need to change if there is a change to the compression scheme or if the data is changed from a compressed state to an uncompressed state, or vice-versa.
The present invention provides a method and mechanism for compressing and decompressing data in a computing system. Examples of benefits of utilizing the present compression approach include (a) reducing storage/disk space and (b) reducing the runtime I/O demands on the disk subsystem. For purposes of illustration only, the following description will be made with respect to the compression/decompression of data files in database files using blocks. It is noted, however, that the present invention is applicable to managing other types and granularities of data in a computing system, and thus is not to be limited to compression of just database data or granularities of just files/blocks.
FIG. 1 is an overview diagram showing an embodiment of the present invention in which a file 2 comprises data portions 2 a–f. It is noted that data within a file is not always uniformly compressed. The achievable compression ratio for pieces of data within a file depends upon both the specific compression algorithm being used as well as the type/content of the data being compressed. Despite the non-uniform nature of compression, two or more uniform sizes are selected for the storage units into which the data portions are stored, according to an embodiment of the invention. In the example of FIG. 1, a first set 4 of storage units are configured with a relatively larger size to store uncompressed data portions. A second set 6 of storage units are configured with a relatively smaller size to store compressed data portions.
According to an embodiment, each granular portion of a file can be quantified as a logical block, which can be considered a granularity at which the computing system uses or splits up a file. In an embodiment, a database logical block is 4 k–8 K bytes. The logical block may or may not be the same size as a physical disk block, and in many cases, a physical disk block could be smaller than a logical block, e.g., 512 bytes. In one embodiment, contiguous logical database blocks will not be considered together for compression although they may result in a higher compression ratio. The data returned from a read operation will be presented transparently in the uncompressed logical database block format. Similarly the data supplied by the generic RDBMS code will also be in the form of uncompressed blocks, which will be transparently compressed before writing to the appropriate location on disk. The database file compression will hence be at the granularity of a logical block.
In an embodiment, each compressed and uncompressed storage unit comprises one or more physical disk blocks. The term “compressed blocks” will be used herein to refer to a compressed storage unit and the term “uncompressed block” will refer to an uncompressed storage unit. A compressed block size could be configured to be a multiple of the physical disk block size (e.g. a 8K logical database block, a 2K compressed block and a 512 byte physical disk block).
In the example of FIG. 2, it can be seen that each allocated slot in uncompressed set 100 a includes an equivalent allocated slot in compressed set 100 b. Thus, allocated slot 102 a in set 100 a is matched with slot 102 b in set 100 b. Similarly, allocated slots 104 a–118 a in set 100 a are matched with slots 104 b–118 b in set 100 b, respectively. If data is stored in an allocated compressed slot in set 100 b (e.g., slots 104 b, 108 b, 112 b, 114 b, 116 b, and 118 b), then its corresponding slot in set 100 a should not include the uncompressed version of the stored data (e.g., as shown by the value “0” in corresponding slots 104 a, 108 a, 112 a, 114 a, 116 a, and 118 a). If, however, there is no compressed data stored in a given compressed slot in set 100 b (e.g., as shown by the value “0” in slots 102 b, 106 b, and 110 b), then uncompressed data should be stored for each corresponding uncompressed slot in set 100 a (e.g., in slots 102 a, 106 a, and 110 a).
FIG. 4 shows a flowchart of an embodiment of a process for retrieving data from the storage format of FIG. 2. At 402, a request is received to retrieve a given data item from the storage medium. A determination is made whether the requested logical block is stored in a compressed block (404). If so, then the compressed data is retrieved from the respective compressed logical block (406) and decompressed using an appropriate decompression algorithm that matches the original compression scheme used to compress the data (408). In an embodiment, the length of the data in the compressed logical block is stored in the compressed block itself, thereby allowing the system to know how much data to retrieve from a particular offset in the storage system. If the data is not stored in the corresponding compressed block, then the uncompressed data is retrieved from the respective uncompressed block (412). In an embodiment, an identifying symbol or flag is used to indicate that the relevant data portion is too large to fit into the compressed block. For example, a length value of “0” can be stored in the compressed block to indicate that the data is too large to fit into the compressed block, and therefore is stored in the corresponding uncompressed block. Once the data has been suitably identified and retrieved, it is thereafter returned to the requesting entity (410).
The format of FIG. 2 can be particularly advantageous when compression is needed to reduce runtime I/O demands, e.g., in terms of disk arms needed to read and write data or in terms of the latency and throughput needed from the disk system and disk space is not a significant concern. One advantage of this format is its simplicity—directory meta-data is not necessary because only simple calculations are needed to determine the offset of any logical block, since all compressed and uncompressed blocks are pre-allocated to correspond to blocks in the original file. Thus, overhead relating to directory maintenance operations are not needed, e.g., when moving a logical block from a compressed format to uncompressed format or vice versa. This helps the approach to scale well in SMP systems and disk clusters. In the case of disk clusters, well-known serialization mechanisms can be used to prevent concurrent writes to the same logical blocks. The format is hence suitable for OLTP (on-line transaction processing) systems that may have significant write activity.
One possible issue of this format is that it may actually consume more disk space than a purely uncompressed file because each logical block has space allotted for the uncompressed and compressed forms. If the compressed block size is 1/n of the logical block size the total disk space consumed may be increased by 1/n. Given the trend of rapid decreases for the costs of storage in computer systems, this issue may not be a significant factor if I/O speed and performance are of paramount importance. A second possible issue is that two I/O operations may be needed to read a logical block that could not be compressed—first to read the compressed block and determine that it is not compressed and the second to read the logical uncompressed block. This second issue can be addressed by using an in-memory directory to map data locations. An additional optimization that can be applied is to store the uncompressed data on relatively slower parts of the disk.
A second allocated compressed block 606 a is not inhabited with compressed data corresponding to its associated logical block. A flag or indicator may be maintained to show that a compressed block does not hold compressed data for its associated logical block. In FIG. 6, this indicator is shown as the value “0”, which could correspond to the data length of the compressed data stored in a compressed block. Since the compressed form of that data does not fit into the compressed block 606 a, an uncompressed block 606 b is allocated to store that data. In an embodiment, compressed block 606 a may contain or be associated with a pointer 610 or address structure to point to the location of its corresponding uncompressed block 606 b. Similarly, a third compressed block 608 a also includes an indicator showing that it does not hold data. Instead, compressed block 608 a is also associated with a pointer 612 that points to the location of its corresponding uncompressed block 608 b that has been allocated to store its associated data.
A data structure 616 can be maintained to point to the next available location 614 that can be allocated for an uncompressed block. In an embodiment, the file header contains the offset of the file where the next logical uncompressed database block can be stored. When a logical block cannot be compressed within the compressed block size, the file header is first read to determine the offset for writing the uncompressed block. The file header block is locked and updated to reflect the new offset (which is the old offset plus the size of a logical database block), the dummy compressed block is written to “forward” the request to the uncompressed logical block and then the uncompressed block is written. When used with disk clusters, the file header can be pinged to the cluster that needs to write a logical block that was previously stored in the compressed format.
In some cases, the space occupied by the previously uncompressed logical block cannot be easily reclaimed. Depending upon the particular system configuration with which the invention is employed, it may not be feasible to change the “forwarding addresses” of other uncompressed blocks. In this circumstance, the old location of the uncompressed block is stored within the compressed block so that if this block becomes uncompressed again, the old space can be reused. This may happen, for example, if data that was formerly shifted from an uncompressed block into a compressed block is updated or modified such that it again no longer fits into the compressed block. Rather than allocate a new uncompressed block, the old uncompressed block is re-used to store that data. In one embodiment of this approach, several possibilities exist as to the content of a compressed block. In a first possibility, if the compressed data has always fit into the compressed block, then the length value for the compressed data is non-zero (to indicate that there exists compressed data stored in the compressed block) and the pointer/address structure for an associated uncompressed block is empty (to show that the uncompressed block has never been allocated). In a second possibility, if the compressed data presently does not fit into the compressed block, then the length value for the compressed data is zero (to indicate that there does not exist any compressed data in the block) and the pointer/address structure includes a valid location for the uncompressed block that is presently storing the data. In a third possibility, if the compressed data now fits into the compressed block but in the past did not fit, then the length value for the compressed data is non-zero (to indicate that compressed data is presently stored in the compressed block) and the pointer/address structure includes a valid location for the uncompressed block that previously stored the uncompressed data corresponding to the block.
If the data is not stored in the corresponding compressed block, then an identification is made of the location for the corresponding uncompressed block that is associated with the compressed block (810). In an embodiment, the address of the uncompressed block is maintained within the associated compressed block. Thus, the address is followed to uncompressed data from the compressed block (812). In an embodiment, an identifying symbol or flag is used to indicate that the relevant data portion is too large to fit into the compressed block. For example, a length value of “0” can be stored in the compressed block to indicate that the data is too large to fit into the compressed block, and therefore is stored in the corresponding uncompressed block. Once the data has been suitably identified and retrieved, it is thereafter returned to the requesting entity (816).
If space is not committed to uncompressed blocks apriori (as in the directory format of FIG. 6), a persistent directory can be implemented in an embodiment in the form of two-level hash table that performs lookup for the byte offset in the file for a given logical block. A miss in the hash table would indicate that the block is stored in compressed format. The first level of the hash would narrow the directory search for a logical block to a few directory structures (referred to herein as directory blocks, although the unit of storage for this information does not necessarily have to be in individual “blocks”) and a binary search can be used within a directory block. For large files, this directory may need to be paged in (similar to a page fault in reading the page table entry). For file sizes that are sufficiently small, it may be feasible to cache the directory in memory. The file header itself may contain the offset of the next uncompressed block that is available for use. Thus, this approach allows a determination of whether a given logical block is compressed or not without performing disk I/O, thereby reducing the latency of reads.
This is the approach illustrated by directory block 922. It is noted that the contiguous portion of file 900 that includes logical blocks 910, 912, and 914 is assigned to directory block 922. In the set 903 of compressed blocks, it can be seen that compressed data has been stored in compressed blocks 912 a and 914 a, which correspond to logical blocks 912 and 914 respectively. Note that since uncompressed blocks have not been allocated for logical blocks 912 and 914, entries are not maintained in directory block 922 for these logical blocks. However, in this example, an indicator value (the value “0”) appears in compressed block 910 a indicating the compressed data for associated logical block 910 does not fit within the size constraints of compressed block 910 a. Thus, an uncompressed block 910 b has been allocated to store the data within logical block 910. A directory entry 910 d is maintained in directory block 922 that identifies the logical block, whether the logical block is maintained in compressed form, the compressed block number, and the address of the uncompressed block associated with the logical block. In an embodiment, the compressed block number is not stored.
Alternatively, the directory block can be configured to maintain information about logical blocks even if their contents are not presently stored in an uncompressed block. This is illustrated by directory block 920. Recall that the contiguous portion of file 900 that includes logical blocks 902, 904, and 906 is assigned to directory block 920. In the set 903 of compressed blocks, it can be seen that compressed data has been stored in compressed blocks 902 a and 904 a, which correspond to logical blocks 902 and 904 respectively. Even though an uncompressed block has not been allocated for logical block 902, an entry 902 d is maintained in directory block 920 for this logical block, which identifies this logical block as presently being stored in compressed form in compressed block 902 a. The address field for an allocated uncompressed block contains an indicator (e.g., the value “0”) that indicates that no uncompressed block has been allocated for the logical block corresponding to entry 902 d. Entries can also be maintained for logical blocks which may have been associated with an uncompressed block in the past, but which at present are stored in a compressed block. This may occur, for example, if the data within the logical block has been updated or modified such that the compressed form of that data can fit within the size of a compressed block and the system is configured not to reallocate the uncompressed block to be used by another logical block. Under this circumstance, it is advantageous to continue to track the address of the uncompressed block to be re-used in case the logical block is again updated or modified such that its data no longer fits in compressed form within the compressed block.
The execution of the sequences of instructions required to practice the invention may be performed in embodiments of the invention by a computer system 1400 as shown in FIG. 10. In an embodiment of the invention, execution of the sequences of instructions required to practice the invention is performed by a single computer system 1400. According to other embodiments of the invention, two or more computer systems 1400 coupled by a communication link 1415 may perform the sequence of instructions required to practice the invention in coordination with one another. In order to avoid needlessly obscuring the invention, a description of only one computer system 1400 will be presented below; however, it should be understood that any number of computer systems 1400 may be employed to practice the invention.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4862167 *Feb 24, 1987Aug 29, 1989Hayes Microcomputer Products, Inc.Adaptive data compression method and apparatusUS5237460 *Sep 4, 1992Aug 17, 1993Ceram, Inc.Storage of compressed data on random access storage devicesUS5357431Jan 25, 1993Oct 18, 1994Fujitsu LimitedCharacter string retrieval system using index and unit for making the indexUS5414834Dec 7, 1990May 9, 1995International Business Machines CorporationMethod and apparatus for data storage and interchange using a relational database table, and a data record for use in connection therewithUS5426426Aug 16, 1993Jun 20, 1995Motorola, Inc.Tokens for use in data communications systemsUS5627995 *Jun 1, 1994May 6, 1997Alfred P. GnadingerData compression and decompression using memory spaces of more than one sizeUS5787415Oct 30, 1996Jul 28, 1998International Business Machines CorporationLow maintenance data delivery and refresh system for decision support system databaseUS5918225Mar 20, 1997Jun 29, 1999Sybase, Inc.SQL-based database system with improved indexing methodologyUS5936560 *Jul 18, 1997Aug 10, 1999Fujitsu LimitedData compression method and apparatus performing high-speed comparison between data stored in a dictionary window and data to be compressedUS6006232Oct 21, 1997Dec 21, 1999At&T Corp.System and method for multirecord compression in a relational databaseUS6112209Jun 17, 1998Aug 29, 2000Gusack; Mark DavidAssociative database model for electronic-based informational assembliesUS6199070Jun 18, 1998Mar 6, 2001International Business Machines CorporationUsing a database for program logsUS6205453Mar 13, 1998Mar 20, 2001Oracle CorporationSystem and method for implementing selectively index enabled multi-column lists in a computer systemUS6208273 *Oct 20, 1999Mar 27, 2001Interactive Silicon, Inc.System and method for performing scalable embedded parallel data compressionUS6360300 *Aug 31, 1999Mar 19, 2002International Business Machines CorporationSystem and method for storing compressed and uncompressed data on a hard disk driveUS6374266 *Jul 24, 1999Apr 16, 2002Ralph ShnelvarMethod and apparatus for storing information in a data processing systemUS6427145Mar 1, 2000Jul 30, 2002Hitachi, Ltd.Database processing method, apparatus for carrying out the same and medium storing processing programUS6721751May 30, 2000Apr 13, 2004Turbo Data Laboratories Inc.Method of concatenating table-format data, and method of presenting concatenated table-format dataUS6760907 *Jun 30, 1998Jul 6, 2004Sun Microsystems, Inc.Code generation for a bytecode compilerUS6823329Apr 2, 2002Nov 23, 2004Sybase, Inc.Database system providing methodology for acceleration of queries involving functional expressions against columns having enumerated storageUS20020073298 *Jul 26, 2001Jun 13, 2002Peter GeigerSystem and method for managing compression and decompression of system memory in a computer systemUS20020107988 *Feb 5, 2001Aug 8, 2002James JordanIn-line compression system for low-bandwidth client-server data linkUS20030009595Jul 9, 2001Jan 9, 2003Roger CollinsSystem and method for compressing data using field-based code word generationUS20030023536Jul 25, 2001Jan 30, 2003Chicago Board Options ExchangeSystem and method for displaying option market informationUS20030028509Aug 6, 2001Feb 6, 2003Adam SahStorage of row-column dataUS20030065662Aug 12, 2002Apr 3, 2003Jasmin CosicUniversal data management interfaceUS20030212694Apr 29, 2003Nov 13, 2003Oracle International CorporationMethod and mechanism of improving performance of database query language statementsUS20040034616Apr 25, 2003Feb 19, 2004Andrew WitkowskiUsing relational structures to create and support a cube within a relational database systemEP0079465A2Oct 14, 1982May 25, 1983International Business Machines CorporationMethod for storing and accessing a relational data base* Cited by examinerNon-Patent CitationsReference1 *Adaptive compressed caching: design and implementation□□de Castro, R.S.; Lago, A.P.D.; da Silva, D.; Computer Architecture and High Performance Computing, 2003. Proceedings. 15th Symposium on , Nov. 10-12, 2003; pp.: 10-18.2Bassiouni, M.A., "Data Compression in Scientific and Statistical Databases," IEEE Transactions on Software Engineering, (1985), vol. SE-11, No. 10, pp. 1047-1058.3Bayer, R. et al., "Organization and Maintenance of Large Ordered Indexes," Acta Informat., (1972) vol. 1, pp. 173-189.4Beckmann, N. et al., "The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles," ACM SIGMOD (1992) pp. 322-331.5Berchtold, S. et al., "The X-Tree: An Index Structure for High-Dimensional Data," VLDB (1996), pp. 28-39.6 *Cache-memory interfaces in compressed memory systems□□Benveniste, C.D.; Franaszek, P.A.; Robinson, J.T.; Computers, IEEE Transactions on , vol.: 50 , Issue: 11 , Nov. 2001 □□pp.: 1106-1116.7Chen, W. T. et al. "Counter for Full Table Scan Control in Data Redistribution", IBM Technical Disclosure Bulletin (Sep. 1992), vol. 35, No. 4B, pp. 3-4.8Chen, Z. and P. Seshadri "An Algebraic Compression Framework for Query Results" Data Engineering 2000, Proceedings of the 16<SUP>th </SUP>International Conference on San Diego, CA, USA, Feb. 29-Mar. 3, 2000, IEEE Comp. Soc. (Feb. 29, 2000) pp. 177-188.9Cockshott, W.P. et al. "Data Compression in Database Systems" Database and Expert Systems Applications 1998, Proceedings of the 9<SUP>th </SUP>International Workshop on Vienna, AT, Aug. 26-28, 1998 IEEE Comp. Soc. (Aug. 26, 1998) pp. 981-990.10comp.compression Frequently Asked Questions (part 1/3), http://www.faqs.org/faqs/compression-faq/part1/, Last-modified: Sep. 5, 1999, pp. 1-65.11comp.compression Frequently Asked Questions (part 2.3), http://www.faqs.org/faqs/compression-faq/part2/, Last-modified: Sep. 5, 1999, pp. 1-37.12comp.compression Frequently Asked Questions (part 3/3), http://www.faqs.org/faqs/compression-faq/part3/, Last-modified Feb. 7<SUP>th</SUP>, 1996, pp. 1-13.13Couchman, J.S. Oracle Certified Professional(TM) DBA Certification Exam Guide Osborne McGraw-Hill, Berkeley, CA (1998) Title page, Copyright page, Table of Contents and pp. 54, 59, 69, 109-111, 125-131, 133, 185, 233, 271, 416, 460, and 503-512 provided.14Eggers, S. J. et al., "A Compression Technique for Large Statistical Databases," VLDB (1981), pp. 424-434.15Goldstein, J. et al. "Compressing Relations and Indexes" Data Engineering 1998, Proceedings of the 14<SUP>th </SUP>International Conference on Orlando, FL, USA, Feb. 23-27, 1998, IEEE Comput. Soc. (Feb. 23, 1998) pp. 370-379.16Goldstein, J. et al., "Compressing Relations and Indexes," Technical report No. 1355, CS Dept., University of Wisconsin-Madison (1997) pp. 1-23.17Graefe, G. and L.D. Shapiro "Data Compression and Database Performance" Applied Computing 1991, Proceedings of the 1991 Symposium on Kansas City, MO, USA, Apr. 3-5, 1991 IEEE Comp. Soc. (Apr. 3, 1991) pp. 22-27.18Guttman, Antonin, "R-Trees: A Dynamic Index Structure for Spatial Searching," ACM SIGMOD (1984), pp. 47-57.19Haerder, T. et al. "Speicherungsstrukturen" Datenbanksysteme: Konzepte und Techniken der Implementierung (1999), Book excerpt, pp. 143-175.20Leutenegger, S.T. et al., "STR: A Simple and Efficient Algorithm for R-Tree Packing," Tech. Report, Mathematics and Computer Science Dept., University of Denver (1996) No. 96-02, pp. 1-29.21Lin, K.I. et al., The TV-Tree: An Index Structure for High-Dimensional Data, VLDB journal (1994), vol. 3, No. 4, pp. 517-542.22Ng, W. K. et al., "Relational Database Compression Using Augmented Vector Quantization," IEEE 11<SUP>th </SUP>International Conference on Data Engineering (1995), pp. 540-549.23Ng, W.K. and C.V. Ravishankar "Relational Database Compression Using Augmented Vector Quantization" Data Engineering 1995, Proceedings of the 11<SUP>th </SUP>International Conference on Taipei, TW, Mar. 6-10, 1995, IEEE Comp. Soc. (Mar. 6, 1995), pp. 540-549.24Nievergelt, J. et al, "The Grid File: An Adaptable, Symmetric Multikey File Structure," Readings in Database Systems, (1988) Morgan Kaufmann, 582-598.25Olken, F. and D. Rotem "Rearranging Data to Maximize the Efficiency of Compression" J. Comp. Sys. Sci. (Apr. 1989) 38(2):405-430.26O'Neil, P. et al., "Improved Query Performance with Variant Indexes," ACM SIGMOD (1977), pp. 38-49.27Roth, M.A. et al., "Database Compression," SIGMOD Record, (1993) vol. 22, No. 3, pp. 31-39.28Seeger, B. et al., "The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems," VLDB (1990), pp. 590-601.29Segev, A. and A. Chatterjee "Supporting Statistics in Extensible Database: A Case Study" Scientific and Statistical Database Management 1994, Proceedings of the 7<SUP>th </SUP>International Working Conference on Charlottesville, VA, USA, Sep. 28-30, 1994, IEEE Comput. Soc. (Sep. 28, 1994), pp. 54-63.30Shannon, C.E., "A Mathematical Theory of Communication", The Bell System Technical Journal, vol. 27, pp. 379-423, 623,656, Jul., Oct., 1948, Reprint pp. 1-55.31Westmann, Till et al., "The Implementation and Performance of Compressed Databases", Reihe Informatik, Mar. 1998.32Ziv, J., et al, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, (1977) vol. 31, No. 3, pp. 337-343.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7451290May 11, 2006Nov 11, 2008Oracle International CorporationMethod and mechanism for on-line data compression and in-place updatesUS7454403Apr 29, 2003Nov 18, 2008Oracle International CorporationMethod and mechanism of improving performance of database query language statements using data duplication informationUS7457940 *Nov 16, 2004Nov 25, 2008International Business Machines CorporationSystem and method for managing dataUS7536398 *Mar 29, 2005May 19, 2009Is Technologies, LlcOn-line organization of data setsUS7683811 *May 15, 2008Mar 23, 2010Narayanan Sarukkai RStorage and retrieval of compressed data in mixed modeUS7743140 *Dec 8, 2006Jun 22, 2010International Business Machines CorporationBinding processes in a non-uniform memory access systemUS7747585 *Aug 7, 2007Jun 29, 2010International Business Machines CorporationParallel uncompression of a partially compressed database table determines a count of uncompression tasks that satisfies the queryUS7917737Oct 22, 2008Mar 29, 2011International Business Machines CorporationSystem and method for managing dataUS8005844Feb 3, 2009Aug 23, 2011Is Technologies, LlcOn-line organization of data setsUS8203733May 3, 2007Jun 19, 2012Fuji Xerox Co., Ltd.Image processing apparatus, storage medium in which image processing program is stored, and image processing methodUS8392382 *Mar 5, 2013Oracle International CorporationOn-line transaction processing (OLTP) compression and re-compression of database dataUS8433823 *Sep 2, 2011Apr 30, 2013Tibco Software Inc.Random access data compressionUS8572054Aug 31, 2010Oct 29, 2013Estsoft Corp.Forward compatibility guaranteed data compression and decompression method and apparatus thereofUS8593312 *Aug 25, 2010Nov 26, 2013Estsoft Corp.Method and apparatus for compressing and decompressing block unit dataUS8645338Oct 28, 2010Feb 4, 2014International Business Machines CorporationActive memory expansion and RDBMS meta data and toolingUS8799241Mar 8, 2013Aug 5, 2014International Business Machines CorporationDynamic partial uncompression of a database tableUS8805799Aug 7, 2007Aug 12, 2014International Business Machines CorporationDynamic partial uncompression of a database tableUS8805802Mar 8, 2013Aug 12, 2014International Business Machines CorporationDynamic partial uncompression of a database tableUS8943029Feb 9, 2013Jan 27, 2015Oracle International CorporationOn-line transaction processing (OLTP) compression and re-compression of database dataUS20030212694 *Apr 29, 2003Nov 13, 2003Oracle International CorporationMethod and mechanism of improving performance of database query language statementsUS20060106986 *Nov 16, 2004May 18, 2006International Business Machines CorporationSystem and method for managing dataUS20060212672 *May 11, 2006Sep 21, 2006Sashikanth ChandrasekaranMethod and mechanism for on-line data compression and in-place updatesUS20060230054 *Mar 29, 2005Oct 12, 2006Jon MoogOn-line organization of data setsUS20070247466 *Feb 16, 2007Oct 25, 2007Fuji Xerox Co., LtdImage processing apparatus and programUS20070248288 *Feb 16, 2007Oct 25, 2007Fuji Xerox Co., Ltd.Image processing device, and recording mediumUS20080001953 *Dec 13, 2006Jan 3, 2008Fuji Xerox Co., Ltd.Image processing device and method and storage medium storing programUS20080013862 *May 3, 2007Jan 17, 2008Fuji Xerox Co., Ltd.Image processing apparatus, storage medium in which image processing program is stored, and image processing methodUS20080141251 *Dec 8, 2006Jun 12, 2008Barry Bradley ArndtBinding processes in a non-uniform memory access systemUS20080294668 *May 15, 2008Nov 27, 2008Narayanan Sarukkai RStorage and Retrieval of Compressed Data in Mixed ModeUS20090043734 *Aug 7, 2007Feb 12, 2009Eric Lawrence BarsnessDynamic Partial Uncompression of a Database TableUS20090043792 *Aug 7, 2007Feb 12, 2009Eric Lawrence BarsnessPartial Compression of a Database Table Based on Historical InformationUS20090043793 *Aug 7, 2007Feb 12, 2009Eric Lawrence BarsnessParallel Uncompression of a Partially Compressed Database TableUS20090106281 *Oct 19, 2007Apr 23, 2009Oracle International CorporationOn-line transaction processing (oltp) compression and re-compression of database dataUS20090138451 *Feb 3, 2009May 28, 2009Is Technologies, LlcOn-line organization of data setsUS20120109909 *Sep 2, 2011May 3, 2012Jean-Christophe Roger HuglyRandom Access Data CompressionUS20150331724 *May 16, 2014Nov 19, 2015Teradata Us, Inc.Workload balancing to handle skews for big data analytics* Cited by examinerClassifications U.S. Classification711/171, 707/E17.005, 709/247, 707/E17.01, 707/999.101International ClassificationG06F12/00, G06F17/30, G06F3/06Cooperative ClassificationY10S707/99942, G06F17/30067, G06F3/0676, G06F3/064, G06F3/0608European ClassificationG06F3/06A6L2D2, G06F3/06A4F2, G06F3/06A2C, G06F17/30FLegal EventsDateCodeEventDescriptionSep 18, 2002ASAssignmentOwner name: ORACLE CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CHANDRASEKARAN, SASHIKANTH;PRUSCINO, ANGELO;REEL/FRAME:013324/0265;SIGNING DATES FROM 20020827 TO 20020912Mar 11, 2003ASAssignmentOwner name: ORACLE INTERNATIONAL CORPORATION (OIC), CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ORACLE CORPORATION;REEL/FRAME:013797/0613Effective date: 20030221Oct 23, 2009FPAYFee paymentYear of fee payment: 4Nov 6, 2013FPAYFee paymentYear of fee payment: 8RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services