Methods and systems to estimate query responses based on data set sketches

A method to process database queries, the method comprising:

• accessing, with a processor, a plurality of bottom-k sketches summarizing a plurality of data sets in response to receiving a query, a first one of the bottom-k sketches including pairs of ranks and weights for a first number of items from a first one of the data sets, the first number of items having smallest ranks among a set of items included in the first one of the data sets, the first one of the bottom-k sketches also identifying a next largest rank corresponding to a smallest remaining rank among the remaining items included in the first one of the data sets but not included in the first one of the bottom-k sketches;
• determining, with the processor, a combination sketch comprising a combination of the plurality of bottom-k sketches containing items from the plurality of bottom-k sketches having respective ranks less than a limiting rank, the limiting rank being a minimum of a plurality of next largest ranks corresponding respectively to the plurality of bottom-k sketches;
• and
• determining, with the processor, a query result based on the combination sketch, the query result being responsive to the query.

A machine readable storage device comprising machine readable instructions which, when executed, cause a machine to perform operations comprising:

• accessing a plurality of bottom-k sketches summarizing a plurality of data sets in response to receiving a query, a first one of the bottom-k sketches including pairs of ranks and weights for a first number of items from a first one of the data sets, the first number of items having smallest ranks among a set of items included in the first one of the data sets, the first one of the bottom-k sketches also identifying a next largest rank corresponding to a smallest remaining rank among the remaining items included in the first one of the data sets but not included in the first one of the bottom-k sketches;
• determining a combination sketch comprising a combination of the plurality of bottom-k sketches containing items from the plurality of bottom-k sketches having respective ranks less than a limiting rank, the limiting rank being a minimum of a plurality of next largest ranks corresponding respectively to the plurality of bottom-k sketches;
• and
• determining a query result based on the combination sketch, the query result being responsive to the query.

An apparatus to process database queries, the apparatus comprising:

• a memory having machine readable instructions stored thereon;
• and
• a processor to execute the instructions to perform operations comprising:
• accessing a plurality of bottom-k sketches summarizing a plurality of data sets in response to receiving a query, a first one of the bottom-k sketches including pairs of ranks and weights for a first number of items from a first one of the data sets, the first number of items having smallest ranks among a set of items included in the first one of the data sets, the first one of the bottom-k sketches also identifying a next largest rank corresponding to a smallest remaining rank among the remaining items included in the first one of the data sets but not included in the first one of the bottom-k sketches;
• determining a combination sketch comprising a combination of the plurality of bottom-k sketches containing items from the plurality of bottom-k sketches having respective ranks less than a limiting rank, the limiting rank being a minimum of a plurality of next largest ranks corresponding respectively to the plurality of bottom-k sketches;
• and
• determining a query result based on the combination sketch, the query result being responsive to the query.