Accessing data in a column store database based on hardware compatible data structures
US7966343B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 7, 2008 |
| Grant date | Jun 21, 2011 |
| Priority date | — |
| Expiry date | Jan 20, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/221
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.