Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2011-06-21
2011-06-21
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S792000
Reexamination Certificate
active
07966343
ABSTRACT:
Embodiments of the present invention provide one or more hardware-friendly data structures that enable efficient hardware acceleration of database operations. In particular, the present invention employs a column-store format for the database. In the database, column-groups are stored with implicit row ids (RIDs) and a RID-to-primary key column having both column-store and row-store benefits via column hopping and a heap structure for adding new data. Fixed-width column compression allow for easy hardware database processing directly on the compressed data. A global database virtual address space is utilized that allows for arithmetic derivation of any physical address of the data regardless of its location. A word compression dictionary with token compare and sort index is also provided to allow for efficient hardware-based searching of text. A tuple reconstruction process is provided as well that allows hardware to reconstruct a row by stitching together data from multiple column groups.
REFERENCES:
patent: 5265260 (1993-11-01), Hendricks
patent: 5386583 (1995-01-01), Hendricks
patent: 5414812 (1995-05-01), Filip et al.
patent: 5537592 (1996-07-01), King et al.
patent: 5544357 (1996-08-01), Huei
patent: 5649181 (1997-07-01), French et al.
patent: 5664172 (1997-09-01), Antoshenkov
patent: 5666524 (1997-09-01), Kunkel et al.
patent: 5794228 (1998-08-01), French et al.
patent: 5794229 (1998-08-01), French et al.
patent: 5852821 (1998-12-01), Chen et al.
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5974411 (1999-10-01), McCool et al.
patent: 6122627 (2000-09-01), Carey et al.
patent: 6269390 (2001-07-01), Boland
patent: 6311265 (2001-10-01), Beckerie et al.
patent: 6539396 (2003-03-01), Bowman-Amuah
patent: 6549996 (2003-04-01), Manry et al.
patent: 6622144 (2003-09-01), Rush, Jr.
patent: 6629095 (2003-09-01), Wagstaff et al.
patent: 6778977 (2004-08-01), Avadhanam et al.
patent: 6785684 (2004-08-01), Adbo
patent: 6931419 (2005-08-01), Lindquist
patent: 7158994 (2007-01-01), Smith et al.
patent: 7219102 (2007-05-01), Zhou et al.
patent: 7246115 (2007-07-01), Zhang et al.
patent: 7337176 (2008-02-01), Cheedella et al.
patent: 7529753 (2009-05-01), Ewing
patent: 2002/0046324 (2002-04-01), Barroso et al.
patent: 2002/0069318 (2002-06-01), Chow et al.
patent: 2002/0078015 (2002-06-01), Ponnekanti
patent: 2003/0118630 (2003-01-01), Indeck et al.
patent: 2003/0086300 (2003-05-01), Noyes et al.
patent: 2003/0191795 (2003-10-01), Bernardin et al.
patent: 2004/0088705 (2004-05-01), Eslick et al.
patent: 2004/0133565 (2004-07-01), Hinshaw et al.
patent: 2004/0143562 (2004-07-01), Chen et al.
patent: 2004/0257370 (2004-12-01), Lippincott et al.
patent: 2005/0234882 (2005-10-01), Bennett et al.
patent: 2006/0026176 (2006-02-01), Dettinger et al.
patent: 2006/0218123 (2006-09-01), Chowdhuri et al.
patent: 2007/0067274 (2007-03-01), Han et al.
patent: 2007/0143311 (2007-06-01), Uppala
patent: 2007/0198998 (2007-08-01), Chen et al.
patent: 2007/0277036 (2007-11-01), Chamberlain et al.
patent: 2008/0059492 (2008-03-01), Tarin
patent: 2009/0248616 (2009-10-01), Molini
patent: 02067145 (2002-08-01), None
“Myriad: Design and Implementation of a Federated Database Prototype,” by Lim et al. IN: Software-Practice and Experience, vol. 25(5), 533-562 (May 1995). Available at: http://www.cs.ubc.ca/local/reading/proceeding/spe91-95/spe/vol25/issue5/spe955el.pdf Last visited:Sep. 18, 2009.
“Implementing Database Operations using SIMD Instructions,” by Zhou and Ross. IN: Proceedings of the 2002 ACM SIGMOD Int'l Conference on Management of Data (2002), pp. 145-156. Available at : ACM.
“Beginning mySQL Tutorial,” by Gilmore (1997-2002). Available at http://www.itmelody.com/download/mysql/intro.pdf
“JFS2DIO Sequential Input/Output Performance on IBM pSeries 690,” by IBM Redbooks Paper (2004). Available at: http://utcc.utoronto.ca/ftp/docs/IBM/AIX/red9122-%20JFS2+DIO%20Sequential%20Input%20Output%20performance%20on%20IBM%20pSeries%20690.pdf Last visited: Jun. 19, 2010.
“Join Processing in Relational Databases,” by Mishra and Eich. IN: ACM Computing Surveys. vol. 24, No. 1 (1992),pp. 63-113. Available at: ACM.
Stonebraker et al., “C-Store: A Column-Oriented DBMS”, VLDB, pp. 553-564, 2005.
“The Vertica Database Data Sheet”, www.vertica.com.
“Building a Multi-terabyte Vertica Database”, www.vertica.com, Feb. 2007.
“The Vertica Database, Technical Overview White Paper”, www.vertica.com, Jul. 2007.
Bandi et al., “Hardware Acceleration of Database Operations Using Content-Addressable Memories”, Proceedings of the First International Workshop on Data Managements on New Hardware (DaMoN 2005); Jun. 12, 2005, Baltimore, Maryland.
Bandi et al., “Hardware Acceleration in Commercial Databases: A Case Study of Spatial Operations”, Proceedings of the 30th VLDB Conference, Toronto, Canada 2004.
Non-Final Office Action dated Sep. 24, 2009 issued in related U.S. Appl. No. 11/895,952, filed Aug. 27, 2007.
Non-Final Office Action dated Nov. 17, 2009 issued in related U.S. Appl. No. 11/895,998, filed Aug. 27, 2007.
Non-Final Office Action dated Sep. 4, 2009 issued in related U.S. Appl. No. 12/098,988, filed Apr. 7, 2008.
Branscome Jeremy
Chamdani Joseph I.
Corwin Michael
Krishnamurthy Ravi
Meiyyappan Krishnan
Monument IP Law Group
Nguyen Kim T
Teradata , US Inc.
Wong Don
LandOfFree
Accessing data in a column store database based on hardware... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accessing data in a column store database based on hardware..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accessing data in a column store database based on hardware... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2640582