Accessing data in column store database based on hardware compatible data structures
US9378231B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 13, 2011 |
| Grant date | Jun 28, 2016 |
| Priority date | — |
| Expiry date | Aug 1, 2033 |
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.