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

Patent metadata

Field	Value
Publication number	US-9779142-B2
Application number	US-201414266335-A
Country	US
Kind code	B2
Filing date	Apr 30, 2014
Priority date	Dec 12, 2008
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

Methods and systems for estimate derivation are described. In one embodiment, a query may be received with a predicate for sets over a collection of items. Associated samples associated with the query may be accessed. Items of an associated sample may be accessed from the collection of items. A determination of whether the predicate is an attribute-based selection from a union of at least some sets may be made. Available items of the particular associated sample may be selected from the items. Identified items may be identified among the available items in the associated sample that satisfy the predicate. An adjusted weight may be assigned to an item based on a weight of the item and a distribution of the associated samples. An estimate may be generated based on the adjusted weight of the identified items of the associated samples that satisfy the predicate. Additional methods and systems are disclosed.

First claim

What is claimed is:

1. A method to process database queries, the method comprising:
accessing, by executing an instruction 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, by executing an instruction with the processor, a combination sketch based on a combination of the plurality of bottom-k sketches, the combination sketch 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, the combination sketch including more items than are included in any one of the plurality of bottom-k sketches; and
determining, by executing an instruction with the processor, a query result based on the combination sketch, the query result being responsive to the query.

2. The method as defined in claim 1 , wherein each one of the plurality of bottom-k sketches includes a respective first number of items, and the combination sketch includes more than the first number of items.

3. The method as defined in claim 1 , wherein determining the query result includes:
determining adjusted weights for the items in the combination sketch; and
combining a subset of the adjusted weights for a respective subset of the items in the combination sketch that satisfy the query.

4. The method as defined in claim 3 , wherein determining the adjusted weights includes adjusting a first weight associated with a first item in the combination sketch by a probability value based on the limiting rank.

5. The method as defined in claim 4 , wherein adjusting the first weight includes dividing the first weight by the probability value.

6. The method as defined in claim 3 , wherein combining the subset of the adjusted weights includes adding the subset of the adjusted weights.

7. A machine readable storage device including 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 based on a combination of the plurality of bottom-k sketches, the combination sketch 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, the combination sketch including more items than are included in any one of the plurality of bottom-k sketches; and
determining a query result based on the combination sketch, the query result being responsive to the query.

8. The machine readable storage device as defined in claim 7 , wherein the plurality of bottom-k sketches include respective first numbers of items, and the combination sketch includes more than the first number of items.

9. The machine readable storage device as defined in claim 7 , wherein the operations further include:
determining adjusted weights for the items in the combination sketch; and
combining a subset of the adjusted weights for a respective subset of the items in the combination sketch that satisfy the query.

10. The machine readable storage device as defined in claim 9 , wherein determining the adjusted weights includes adjusting a first weight associated with a first item in the combination sketch by a probability value based on the limiting rank.

11. The machine readable storage device as defined in claim 10 , wherein adjusting the first weight includes dividing the first weight by the probability value.

12. The machine readable storage device as defined in claim 9 , wherein combining the subset of the adjusted weights includes adding the subset of the adjusted weights.

13. An apparatus to process database queries, the apparatus comprising:
memory having machine readable instructions stored thereon; and
a processor to execute the instructions to perform operations including:
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 based on a combination of the plurality of bottom-k sketches, the combination sketch 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, the combination sketch including more items than are included in any one of the plurality of bottom-k sketches; and
determining a query result based on the combination sketch, the query result being responsive to the query.

14. The apparatus as defined in claim 13 , wherein each one of the plurality of bottom-k sketches includes a respective first number of items, and the combination sketch includes more than the first number of items.

15. The apparatus as defined in claim 13 , wherein the operations further include:
determining adjusted weights for the items in the combination sketch; and
combining a subset of the adjusted weights for a respective subset of the items in the combination sketch that satisfy the query.

16. The apparatus as defined in claim 15 , wherein determining the adjusted weights includes adjusting a first weight associated with a first item in the combination sketch by a probability value based on the limiting rank.

17. The apparatus as defined in claim 16 , wherein adjusting the first weight includes dividing the first weight by the probability value.

18. The apparatus as defined in claim 15 , wherein combining the subset of the adjusted weights includes adding the subset of the adjusted weights.

Assignees

• At & T Ip I Lp

Inventors

• Cohen Edith
• Kaplan Haim

Classifications

• G06F17/30979

  Physics · mapped topic

• G06F17/3053 Primary

  Physics · mapped topic

• G06F16/90335 Primary

  Query processing · CPC title

• G06F16/24578 Primary

  using ranking · CPC title