Storage Efficient Multimaps For Processing Database Queries

A computer readable storage medium storing instructions that when processed by a computer processor cause the computer processor to perform steps for executing database queries using a multimap, the steps comprising:

• receiving, by a database system, a database query for processing data stored in one or more database tables;
• receiving a first set of records based on the one or more database tables;
• repeating for each record of the first set of records:
• determining a key and a data value corresponding to the record,
• storing the data value in a vector mapped to a key, the vector storing an element representing a size value based on a number of data values mapped to the key, and
• storing in the multimap a pointer to the vector in association with the key;
• receiving a second set of records based on the one or more database tables;
• repeating for each record of the second set of records:
• determining a key corresponding to the record,
• accessing a pointer corresponding to the key from the multimap,
• accessing data values stored in a vector pointed at by the pointer, and
• determining one or more result values based on the data values accessed;
• and
• sending a result of processing the database query based on result values determined using the multimap.

A computer system comprising:

• a computer processor;
• and
• a computer readable storage medium storing instructions that when processed by a computer processor cause the computer processor to perform steps for executing database queries using a multimap, the steps comprising:
• receiving, by a database system, a database query for processing data stored in one or more database tables;
• receiving a first set of records based on the one or more database tables;
• repeating for each record of the first set of records:
• determining a key and a data value corresponding to the record,
• storing the data value in a vector mapped to a key, the vector storing an element representing a size value based on a number of data values mapped to the key, and
• storing in the multimap a pointer to the vector in association with the key;
• receiving a second set of records based on the one or more database tables;
• repeating for each record of the second set of records:
• determining a key corresponding to the record,
• accessing a pointer corresponding to the key from the multimap,
• accessing data values stored in a vector pointed at by the pointer, and
• determining one or more result values based on the data values accessed;
• and
• sending a result of processing the database query based on result values determined using the multimap.