Faster main memory scans in unsorted dictionary-encoded vectors

US10275399B2 · kind B2 · utility

Assignee

• SAP SE · DE

Inventors

• Peter Steinemann · Mannheim, DE
• Thomas Legler · Walldorf, DE

Key dates

• Filing date: Nov 17, 2015
• Grant date: Apr 30, 2019
• Expiry date: Apr 27, 2037

Classification

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

Abstract

A ValueID corresponding to a value to be searched for in a database column can be determined by finding a match in a dictionary for the database column. A row of an index vector for the database column at which to begin a scan for the ValueID can be identified by reading a ValueID lookup table that maps each unique ValueID to a starting position in the index vector for the database column. The ValueID can not occur in the index vector prior to the starting position. The index vector can be scanned beginning at the starting position to find at least one occurrence of the ValueID corresponding to the value being searched, and a result that includes one or more row locations in the database column corresponding to the at least one occurrence in the index vector of the ValueID corresponding to the value being searched can be returned.