Value-ID-based sorting in column-store databases

US10762071B2 · kind B2 · utility

Assignee

• SAP SE · DE

Inventors

• Robert Schulze · Walldorf, DE
• Thomas Peh · Bukit Mertajam, MY

Key dates

• Filing date: Nov 29, 2016
• Grant date: Sep 1, 2020
• Expiry date: Dec 27, 2037

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/2228
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Innovations in performing sort operations for dictionary-compressed values of columns in a column-store database using value identifiers (“IDs”) are described. For example, a database system includes a data store and an execution engine. The data store stores values at positions of a column A dictionary maps distinct values to corresponding value IDs. An inverted index stores, for each of the corresponding value IDs, a list of those of the positions that contain the associated distinct value. The execution engine processes a request to sort values at an input set of the positions and identify an output set of the positions for sorted values. In particular, the execution engine iterates through positions stored in the lists of the inverted index. For a given position, the execution engine checks if the given position is one of the input set and, if so, adds the given position to the output set.