Using shared dictionaries on join columns to improve performance of joins in relational databases

A method comprising:

• maintaining, by a database server, a first table that has a first column and a second table that has a second column;
• maintaining a particular dictionary that contains dictionary values;
• wherein each value in the first column matches a corresponding dictionary value in the particular dictionary;
• wherein each value in the second column matches a corresponding dictionary value in the particular dictionary;
• in response to the database server receiving a request to execute a query that joins the first table with the second table based on the first column and the second column, the database server, wherein the query has a predicate that specifies filter criteria for rows of the second table, building a dictionary-based filter to identify rows, of the second table, that satisfy the filter criteria, using, as a hash value for each row of the second table, the position of the dictionary value, within the particular dictionary, that matches the value in the second column of the row.

A method comprising:

• using a particular dictionary, a database server creating a first dictionary-encoded column vector for a first column of a first table;
• using the particular dictionary, the database server creating a second dictionary-encoded column vector for a second column of a second table;
• in response to the database server receiving a request to execute a query that joins the first table with the second table based on the first column and the second column, the database server performing:
• building a bit vector that includes a plurality of bits;
• wherein each bit of the plurality of bits is at a position within the bit vector that corresponds to a dictionary value within the particular dictionary;
• setting, within the bit vector, bits that correspond to dictionary values that are represented in the second dictionary-encoded column vector;
• performing the following for a plurality of rows in the first table:
• reading a dictionary index, for the row, from the first dictionary-encoded column vector;
• locating a target bit, in the bit vector, that corresponds to the dictionary index;
• and
• based on whether the bit is set, determining whether any rows of the second table that join with the row;
• wherein the database server is executing on one or more computing devices.

One or more non-transitory computer readable media storing instructions which, when executed by one or more computing devices, cause:

• maintaining, by a database server, a first table that has a first column and a second table that has a second column;
• maintaining a particular dictionary that contains dictionary values;
• wherein each value in the first column matches a corresponding dictionary value in the particular dictionary;
• wherein each value in the second column matches a corresponding dictionary value in the particular dictionary;
• in response to the database server receiving a request to execute a query that joins the first table with the second table based on the first column and the second column, the database server performing:
• building a pointer array that includes a plurality of entries;
• wherein each entry of the plurality of entries is at a position within the pointer array that corresponds to a position of a dictionary value within the particular dictionary;
• storing, within one or more of the plurality of entries, information for identifying which rows of the second table have values, in the second column, that match the dictionary value that corresponds to the entry;
• after building the pointer array, performing the following for a plurality of rows in the first table:
• determining a dictionary index for the row, wherein the dictionary index for the row is the position, within the particular dictionary, of the dictionary value that matches the value in the second column of the row;
• locating a target entry, in the pointer array, that corresponds to the dictionary index;
• and
• based on information contained in the target entry, determining zero or more rows of the second table that join with the row.

One or more non-transitory computer readable media comprising instructions which, when executed by one or more computing devices, cause:

• maintaining, by a database server, a first table that has a first column and a second table that has a second column;
• maintaining a particular dictionary that contains dictionary values;
• wherein each value in the first column matches a corresponding dictionary value in the particular dictionary;
• wherein each value in the second column matches a corresponding dictionary value in the particular dictionary;
• in response to the database server receiving a request to execute a query that joins the first table with the second table based on the first column and the second column, the database server, wherein the query has a predicate that specifies filter criteria for rows of the second table, building a dictionary-based filter to identify rows, of the second table, that satisfy the filter criteria, using, as a hash value for each row of the second table, the position of the dictionary value, within the particular dictionary, that matches the value in the second column of the row.

One or more non-transitory computer readable media comprising instructions which, when executed by one or more computing devices, cause:

• using a particular dictionary, a database server creating a first dictionary-encoded column vector for a first column of a first table;
• using the particular dictionary, the database server creating a second dictionary-encoded column vector for a second column of a second table;
• in response to the database server receiving a request to execute a query that joins the first table with the second table based on the first column and the second column, the database server performing:
• building a bit vector that includes a plurality of bits;
• wherein each bit of the plurality of bits is at a position within the bit vector that corresponds to a dictionary value within the particular dictionary;
• setting, within the bit vector, bits that correspond to dictionary values that are represented in the second dictionary-encoded column vector;
• performing the following for a plurality of rows in the first table:
• reading a dictionary index, for the row, from the first dictionary-encoded column vector;
• locating a target bit, in the bit vector, that corresponds to the dictionary index;
• and
• based on whether the bit is set, determining whether any rows of the second table that join with the row.