A computer system comprising one or more processing units and memory, wherein the computer system implements a database system comprising: a data store configured to store dictionary-compressed values at positions of a column using structures that include: a dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value identifiers, wherein the position of each unique value in the dictionary structure represents its value identifier, which is unique within the dictionary structure; and an inverted index structure configured to store, for each of the corresponding value identifiers mapped to the distinct values in the dictionary structure, a list of those of the positions of the column that contain that distinct value for the value identifier; and an execution engine configured to process a request to sort values at an input set of the positions of the column and identify an output set (730, 732) of the positions of the column for at least some of the sorted values, by performing operations that include iterating through the positions stored in the lists of the inverted index structure; and, for each given position among the positions stored in the lists of the inverted index structure: checking if the given position is one of the input set including checking a value of a bit vector that indicates whether the positions of the column, respectively, are in the input set; and if so, adding the given position to the output set (730, 732), and wherein the operations further include: using the bit vector to calculate the index of the matching position among the positions of the input set; or using a count vector to calculate the index of the matching position among the positions of the input set, wherein the count vector maps the positions of the column to indices of the positions in the input set. a data store configured to store dictionary-compressed values at positions of a column using structures that include: a dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value identifiers, wherein the position of each unique value in the dictionary structure represents its value identifier, which is unique within the dictionary structure; and an inverted index structure configured to store, for each of the corresponding value identifiers mapped to the distinct values in the dictionary structure, a list of those of the positions of the column that contain that distinct value for the value identifier; and a dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value identifiers, wherein the position of each unique value in the dictionary structure represents its value identifier, which is unique within the dictionary structure; and an inverted index structure configured to store, for each of the corresponding value identifiers mapped to the distinct values in the dictionary structure, a list of those of the positions of the column that contain that distinct value for the value identifier; and an execution engine configured to process a request to sort values at an input set of the positions of the column and identify an output set (730, 732) of the positions of the column for at least some of the sorted values, by performing operations that include iterating through the positions stored in the lists of the inverted index structure; and, for each given position among the positions stored in the lists of the inverted index structure: checking if the given position is one of the input set including checking a value of a bit vector that indicates whether the positions of the column, respectively, are in the input set; and if so, adding the given position to the output set (730, 732), and checking if the given position is one of the input set including checking a value of a bit vector that indicates whether the positions of the column, respectively, are in the input set; and if so, adding the given position to the output set (730, 732), and wherein the operations further include: using the bit vector to calculate the index of the matching position among the positions of the input set; or using a count vector to calculate the index of the matching position among the positions of the input set, wherein the count vector maps the positions of the column to indices of the positions in the input set. using the bit vector to calculate the index of the matching position among the positions of the input set; or using a count vector to calculate the index of the matching position among the positions of the input set, wherein the count vector maps the positions of the column to indices of the positions in the input set.