Sampling for database systems

• US 20030018615A1
• Filed: 09/10/2002
• Published: 01/23/2003
• Est. Priority Date: 03/15/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Narasayya, Vivek, Motwani, Rajeev
• Granted Patent: US 7,567,949 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A database server supports weighted and unweighted sampling of records or tuples in accordance with desired sampling semantics such as with replacement (WR), without replacement (WoR), or independent coin flips (CF) semantics, for example. The database server may perform such sampling sequentially not only to sample non-materialized records, such as those produced as a stream by a pipeline in a query tree for example, but also to sample records, whether materialized or not, in a single pass. The database server also supports sampling over a join of two relations of records or tuples without requiring the computation of the full join and without requiring the materialization of both relations and/or indexes on the join attribute values of both relations.

Claims

1. A sample operator for obtaining a sample of a plurality of records in a database system, the sample operator having the plurality of records and sampling semantics as parameters.

2. The sample operator of claim 1, wherein the sampling semantics may be with replacement, without replacement, or coin flip sampling semantics.

3. The sample operator of claim 1 having a size of the sample as a parameter.

4. The sample operator of claim 1 having a weight function as a parameter to specify a sampling weight for each record.

5. The sample operator of claim 1 for obtaining the sample of the plurality of records in one pass by:

(a) obtaining one record from the plurality of records;

(b) selectively outputting the one record obtained in step (a) one or more times based on a probability; and

(c) repeating steps (a) and (b) for one or more other records of the plurality of records to form the sample of the plurality of records.

6. The sample operator of claim 1 for obtaining the sample of the plurality of records in one pass by:

(a) obtaining one record from the plurality of records;

(b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and

(c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form the sample of the plurality of records.

7. A sample operator for obtaining a sample of a plurality of records in a database system, the sample operator having the plurality of records as a parameter and having a weight function as a parameter to specify a sampling weight for each record.

8. The sample operator of claim 7 having a size of the sample as a parameter.

9. The sample operator of claim 7 for obtaining the sample of the plurality of records in one pass by:

(a) obtaining one record from the plurality of records and the weight specified for the one record;

(b) selectively outputting the one record obtained in step (a) one or more times based on the weight specified for the one record; and

(c) repeating steps (a) and (b) for one or more other records of the plurality of records to form the sample of the plurality of records.

10. The sample operator of claim 7 for obtaining the sample of the plurality of records in one pass by:

(a) obtaining one record from the plurality of records and the weight specified for the one record;

(b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on the weight specified for the one record; and

(c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form the sample of the plurality of records.

11. A method for obtaining a sample from a plurality of records in a database system, the method comprising the steps of:

(a) identifying the plurality of records and sampling semantics from parameters of a sample operator; and

(b) obtaining a sample from the identified plurality of records using the identified sampling semantics.

12. The method of claim 11, wherein the identified sampling semantics is with replacement, without replacement, or coin flip sampling semantics.

13. The method of claim 11, wherein the identifying step (a) comprises the step of identifying a size of the sample to be obtained from a parameter of the sample operator;

and

wherein the obtaining step (b) comprises the step of obtaining the sample from the identified plurality of records based on the identified sample size.

14. The method of claim 11, wherein the identifying step (a) comprises the step of identifying a weight function from a parameter of the sample operator to specify a weight for each record;

and

wherein the obtaining step (b) comprises the step of obtaining the sample from the identified plurality of records based on the specified weight of each record.

15. The method of claim 11, wherein the obtaining step (b) comprises the steps of:

(i) obtaining one record from the plurality of records,

(ii) selectively outputting the one record obtained in step (b)(i) one or more times based on a probability, and

(iii) repeating steps (b)(i) and (b)(ii) for one or more other records of the plurality of records to obtain the sample.

16. The method of claim 11, wherein the obtaining step (b) comprises the steps of:

(i) obtaining one record from the plurality of records,

(ii) selectively resetting one or more records of a reservoir to be the one record obtained in step (b)(i) based on a probability, and

(iii) repeating steps (b)(i) and (b)(ii) for other records of the plurality of records such that the records of the reservoir form the sample.

17. A computer readable medium having computer-executable instructions for performing the steps of claim 11.

19. The method of claim 18, wherein the identifying step (a) comprises the step of identifying a size of the sample to be obtained from a parameter of the sample operator;

and

wherein the obtaining step (b) comprises the step of obtaining the sample from the identified plurality of records based on the identified sample size.

20. The method of claim 18, wherein the obtaining step (b) comprises the steps of:

(i) obtaining one record from the plurality of records and the weight specified for the one record,

(ii) selectively outputting the one record obtained in step (b)(i) one or more times based on the weight specified for the one record, and

(iii) repeating steps (b)(i) and (b)(ii) for one or more other records of the plurality of records to obtain the sample.

21. The method of claim 18, wherein the obtaining step (b) comprises the steps of:

(i) obtaining one record from the plurality of records and the weight specified for the one record,

(ii) selectively resetting one or more records of a reservoir to be the one record obtained in step (b)(i) based on the weight specified for the one record, and

(iii) repeating steps (b)(i) and (b)(ii) for other records of the plurality of records such that the records of the reservoir form the sample.

22. A computer readable medium having computer-executable instructions for performing the steps of claim 18.

24. The method of claim 23, wherein the plurality of records are a relation produced as a stream of records as a result of a query.

25. The method of claim 23, wherein the plurality of records are materialized as a base relation in a database of the database system.

26. The method of claim 23, wherein the selectively outputting step (b) comprises the steps of:

(i) determining a random number based on the probability such that the random number is greater than or equal to zero, and

(ii) outputting the one record the determined random number of times.

27. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number from a binomial distribution based on the probability.

28. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a number of record(s) remaining to be output for the sample.

29. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for step (b).

30. The method of claim 23, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.

31. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for step (b).

32. The method of claim 23, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to the weight of the one record.

33. The method of claim 32, wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for step (b).

34. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a weight of the one record.

35. The method of claim 26, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a fraction of the plurality of records.

36. The method of claim 23, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.

38. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting each record of the reservoir to be the one record obtained in step (a) based on a probability.

39. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a number of record(s) that have been obtained for step (a).

40. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) based on a weight of the one record obtained in step (a).

41. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a weight of the one record obtained in step (a) divided by a sum of weight(s) of record(s) that have been obtained for step (a).

42. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (a).

43. The method of claim 37, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.

44. The method of claim 37, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.

46. The computer readable medium of claim 45, wherein the plurality of records are a relation produced as a stream of records as a result of a query.

47. The computer readable medium of claim 45, wherein the plurality of records are materialized as a base relation in a database of the database system.

48. The computer readable medium of claim 45, wherein the selectively outputting step (b) comprises the steps of:

(i) determining a random number based on the probability such that the random number is greater than or equal to zero, and

(ii) outputting the one record the determined random number of times.

49. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number from a binomial distribution based on the probability.

50. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a number of record(s) remaining to be output for the sample.

51. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for step (b).

52. The computer readable medium of claim 45, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.

53. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for step (b).

54. The computer readable medium of claim 45, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to the weight of the one record.

55. The computer readable medium of claim 54, wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for step (b).

56. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a weight of the one record.

57. The computer readable medium of claim 48, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a fraction of the plurality of records.

58. The computer readable medium of claim 45, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.

60. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting each record of the reservoir to be the one record obtained in step (a) based on a probability.

61. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a number of record(s) that have been obtained for step (a).

62. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) based on a weight of the one record obtained in step (a).

63. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a weight of the one record obtained in step (a) divided by a sum of weight(s) of record(s) that have been obtained for step (a).

64. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (a).

65. The computer readable medium of claim 59, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.

66. The computer readable medium of claim 59, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.

68. The database system of claim 67, wherein the plurality of records are a relation produced as a stream of records as a result of a query.

69. The database system of claim 67, wherein the plurality of records are materialized as a base relation in a database of the database system.

70. The database system of claim 67, wherein the selectively outputting step (b) comprises the steps of:

(i) determining a random number based on the probability such that the random number is greater than or equal to zero, and

(ii) outputting the one record the determined random number of times.

71. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number from a binomial distribution based on the probability.

72. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a number of record(s) remaining to be output for the sample.

73. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a number of record(s) of the plurality of records to be evaluated for output for step (b).

74. The database system of claim 70, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record one or more times based on a weight specified for the one record.

75. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a weight of the one record divided by a sum of weight(s) of record(s) of the plurality of records to be evaluated for output for step (b).

76. The database system of claim 67, wherein the selectively outputting step (b) comprises the step of selectively outputting the one record based on a probability a number of time(s) equal in number to the weight of the one record.

77. The database system of claim 76, wherein the selectively outputting step comprises the step of outputting the one record with a probability based on a number of record(s) remaining to be output for the sample divided by a number of possible record(s) that may be output for step (b).

78. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number such that the random number is less than or equal to a weight of the one record.

79. The database system of claim 70, wherein the determining step (b)(i) comprises the step of determining the random number based on a probability based on a fraction of the plurality of records.

80. The database system of claim 67, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.

18. A method for obtaining a sample from a plurality of records in a database system, the method comprising the steps of:

(a) identifying the plurality of records and a weight function from parameters of a sample operator, wherein the weight function specifies a weight for each record; and

(b) obtaining a sample from the identified plurality of records based on the specified weight of each record.

23. A method for performing a sequential sampling of records in one pass in a database system, the method comprising the steps of:

(a) obtaining one record from a plurality of records;

(b) selectively outputting the one record obtained in step (a) one or more times based on a probability; and

(c) repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).

37. A method for performing a sequential sampling of records in one pass in a database system, the method comprising the steps of:

(a) obtaining one record from a plurality of records;

(b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and

(c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).

45. A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of:

(a) obtaining one record from a plurality of records;

(b) selectively outputting the one record obtained in step (a) one or more times based on a probability; and

(c) repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).

59. A computer readable medium having computer-executable instructions for performing a sequential sampling of records in one pass, the computer-executable instructions for performing the steps of:

(a) obtaining one record from a plurality of records;

(b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and

(c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).

67. A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising:

means for performing the step of (a) obtaining one record from a plurality of records;

means for performing the step of (b) selectively outputting the one record one or more times based on a probability; and

means for repeating steps (a) and (b) for one or more other records of the plurality of records to form a sample of the plurality of records, wherein at least one record obtained in step (a) may be output more than one time for step (b).

81. A database system for performing a sequential sampling of records in one pass in the database system, the database system comprising:

means for performing the step of (a) obtaining one record from a plurality of records;

means for performing the step of (b) selectively resetting one or more records of a reservoir to be the one record obtained in step (a) based on a probability; and

means for performing the step of (c) repeating steps (a) and (b) for other records of the plurality of records such that the records of the reservoir form a sample of the plurality of records, wherein at least one record obtained in step (a) may be used to reset more than one record of the reservoir for step (b).

82. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting each record of the reservoir to be the one record obtained in step (a) based on a probability.

83. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a number of record(s) that have been obtained for step (a).

84. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) based on a weight of the one record obtained in step (a).

85. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting one or more records of the reservoir to be the one record obtained in step (a) with a probability based on a weight of the one record obtained in step (a) divided by a sum of weight(s) of record(s) that have been obtained for step (a).

86. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) based on a probability a number of time(s) equal in number to the weight of the one record obtained in step (a).

87. The database system of claim 81, wherein the selectively resetting step (b) comprises the step of selectively resetting a random record of the reservoir to be the one record obtained in step (a) with a probability based on a number of records in the reservoir divided by a sum of record(s) evaluated for reset in the reservoir.

88. The database system of claim 81, wherein the plurality of records form a relation and wherein the sample is to be joined with records of another relation.