Efficient sampling of a relational database

US 20040128290A1
Filed: 12/26/2002
Published: 07/01/2004
Est. Priority Date: 12/26/2002
Status: Active Grant

First Claim

Patent Images

1. A method for sampling data from a relational database, comprising:

choosing rows from a relational database for sampling, wherein rows are arranged into pages and include column values, pages are arranged into tables and tables comprise rows and columns;

wherein pages are chosen for sampling according to a probability P and rows on each selected page are chosen for sampling according to a probability R, so that an overall probability of choosing a row for sampling is Q=PR; and

wherein P and R are based on desired processing speed and desired precision.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A system, method and computer readable medium for sampling data from a relational database are disclosed, where an information processing system chooses rows from a table in a relational database for sampling, wherein data values are arranged into rows, rows are arranged into pages, and pages are arranged into tables. Pages are chosen for sampling according to a probability P and rows in a selected page are chosen for sampling according to a probability R, so that the overall probability of choosing a row for sampling is Q=PR. The probabilities P and R are based on the desired precision of estimates computed from a sample, as well as processing speed. The probabilities P and R are further based on either catalog statistics of the relational database or a pilot sample of rows from the relational database.

51 Citations

View as Search Results

21 Claims

1. A method for sampling data from a relational database, comprising:
- choosing rows from a relational database for sampling, wherein rows are arranged into pages and include column values, pages are arranged into tables and tables comprise rows and columns;
  
  wherein pages are chosen for sampling according to a probability P and rows on each selected page are chosen for sampling according to a probability R, so that an overall probability of choosing a row for sampling is Q=PR; and
  
  wherein P and R are based on desired processing speed and desired precision.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
- - 2. The method of claim 1, wherein R is further based on catalog statistics of the relational database.
  - 3. The method of claim 2, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      and P and R are further defined as;
      
      R=max(R₀,Q) and P=Q/R, R₀=1−
      
      (1−
      
      f(v,d))^d/m, $f (v, d) = 1 + (\frac{1}{1 + v}) (\frac{1}{d} - 1),$ where for each value of d, f(v,d) is a function that is non-decreasing in v and takes on values ranging from 1/d to 1, and where d is an average number of distinct column values per page, m is an average number of rows per page, v=average(v₁, . . . , v_n)/variance(a₁, . . . , a_n), n is a number of pages in the relational database, v_kis a variance of column values on the kth page, and a_kis a average of column values on the kth page.
  - 4. The method of claim 3, wherein P and R are further defined as:
    - R=max(R₀,nQ/M) and P=Q/R where M is a maximum desired number of I/O operations.
  - 5. The method of claim 2, wherein a SELECT clause involves u>
    - 1 columns, as in a query of the form;
      
      SELECT SUM(col1*col3), COUNT(col2/col1), COUNT(col4) FROM t WHERE <
      
      predicate>
      
      , and P and R are further defined as any one of;
      
      R=(R₁R₂. . . R_u)^1/uand P=(P₁P₂. . . P_u)^1/uand R=max(R₁, . . . , R_u) and P=Q/R, where R₁, . . . , R_uare row sampling probabilities and P₁, . . . , P_uare page sampling probabilities computed for individual columns.
  - 6. The method of claim 1, wherein P and R are further based on a pilot sample of rows from the relational database.
  - 7. The method of claim 6, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      and further comprising a step before the choosing step of;
      
      calculating a pilot sample of the column values in the relational database such that pages are chosen for sampling according to a probability P′
      
      , rows are chosen for sampling according to a probability R′
      
      , and then computing the quantities P and R according to $P = {\begin{matrix} D^{*} & if A > B \\ Q & if A \leq B \end{matrix} and R = {\begin{matrix} Q / D^{*} & if A > B \\ 1 & if A \leq B \end{matrix},$ where D* is selected from one of;
      
      D* is equal to a largest real number between 0 and 1 such that a number of I/O operations associated with sampling nD* pages is less than or equal to M if a most precise estimate possible is desired while not exceeding M I/O operations, and $D^{*} = \max (Q, \frac{A - B}{S^{2} + A - (B / Q)})$ if minimal processing time is desired while ensuring that a standard error of an estimated answer to the query does not exceed a value S, and A and B are computed as one of the following;
      
      A=A and B=B₁, and A=A₂and B=B₂, and $A = {(\frac{P^{'} R^{'}}{n_{1} + \dots + n_{k}})}^{2} (A_{2} - 2 u A_{3} + u^{2} A_{1}) and B = {(\frac{P^{'} R^{'}}{n_{1} + \dots + n_{k}})}^{2} (B_{2} - 2 u B_{3} + u^{2} B_{1})$ if <
      
      agg>
      
      is equal to COUNT, SUM, or AVERAGE, respectively, where $A_{1} = \frac{1}{P^{'}} (z_{1} + \dots + z_{k}) and B_{1} = \frac{1}{P^{'} R^{'}} (n_{1} + \dots + n_{k}), z_{j} = {(\frac{n_{j}}{R^{'}})}^{2} - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) n_{j}, A_{2} = \frac{1}{P^{'}} (y_{1} + \dots + y_{k}) and B_{2} = \frac{1}{P^{'} R^{'}} (h_{1} + \dots + h_{k}), y_{j} = {(\frac{g_{j}}{R^{'}})}^{2} - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) h_{j}, A_{3} = \frac{1}{P^{'}} (x_{1} + \dots + x_{k}) and B_{3} = \frac{1}{P^{'} R^{'}} (g_{1} + \dots + g_{k}), x_{j} = (\frac{g_{j}}{R^{'}}) (\frac{n_{j}}{R^{'}}) - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) g_{j}, u = \frac{g_{1} + \dots + g_{k}}{n_{1} + \dots + n_{k}},$ k is a number of pages sampled in the pilot sample, n_jis a number of rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      , g_jis a sum of the column values from those rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      , and h_jis a sum of the squared column values from those rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      .
  - 8. The method of claim 6, wherein the SELECT clause of the query contains u>
    - 1 aggregate expressions and P and R are defined as any one of;
  - 9. The method of claim 6, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      ;
      
      there is no desired overall row sampling probability Q;
      
      P and R are defined as any one of;
      
      P=D* and R=1, if a most precise sampling is desired while not exceeding M I/O operations; and
      
      $P = \frac{A}{S^{2} + A}$ and R=1, if minimal processing time is desired while ensuring that a standard error of an estimated answer to the query does not exceed a value S, wherein D* is equal to a largest real number between 0 and 1 such that a number of I/O operations associated with sampling nD* pages is less than or equal to M.

10. A computer readable medium including computer instructions for sampling data from a relational database, the computer instructions including instructions for:
- choosing rows from a relational database for sampling, wherein rows are arranged into pages and include column values, pages are arranged into tables and tables comprise rows and columns;
  
  wherein pages are chosen for sampling according to a probability P and rows on each selected page are chosen for sampling according to a probability R, so that an overall probability of choosing a row for sampling is Q=PR; and
  
  wherein P and R are based on desired processing speed and desired precision.
- View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
- - 11. The computer readable medium of claim 10, wherein R is further based on catalog statistics of the relational database.
  - 12. The computer readable medium of claim 11, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      and P and R are further defined as;
      
      R=max(R₀,Q) and P=Q/R, R₀=1−
      
      (1−
      
      f(v,d))^d/m, $f (v, d) = 1 + (\frac{1}{1 + v}) (\frac{1}{d} - 1),$ where for each value of d, f(v,d) is a function that is non-decreasing in v and takes on values ranging from 1/d to 1, and where d is an average number of distinct column values per page, m is an average number of rows per page, v=average(v₁, . . . , v_n)/variance(a₁, . . . , a_n), n is a number of pages in the relational database, v_kis a variance of column values on the kth page, and a_kis a average of column values on the kth page.
  - 13. The computer readable medium of claim 12, wherein P and R are further defined as:
    - R=max(R₀,nQ/M) and P=Q/R where M is a maximum desired number of I/O operations.
  - 14. The computer readable medium of claim 11, wherein a SELECT clause involves u>
    - 1 columns, as in a query of the form;
      
      SELECT SUM(col1*col3), COUNT(col2/col1), COUNT(col4) FROM t WHERE <
      
      predicate>
      
      , and P and R are further defined as any one of;
      
      R=(R₁R₂. . . R_u)^1/uand P=(P₁P₂. . . P_u)^1/uand R=max(R₁, . . . , R_u) and P=Q/R, where R₁, . . . , R_uare row sampling probabilities and P₁, . . . , P_uare page sampling probabilities computed for individual columns.
  - 15. The computer readable medium of claim 10, wherein P and R are further based on a pilot sample of rows from the relational database.
  - 16. The computer readable medium of claim 15, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      and further comprising computer instructions for;
      
      calculating a pilot sample of the column values in the relational database such that pages are chosen for sampling according to a probability P′
      
      , rows are chosen for sampling according to a probability R′
      
      , and then computing the quantities P and R according to $P = {\begin{matrix} D^{*} & if A > B \\ Q & if A \leq B \end{matrix} and R = {\begin{matrix} Q / D^{*} & if A > B \\ 1 & if A \leq B^{'} \end{matrix}$ where D* is computed according to one of the following;
      
      D* is equal to a largest real number between 0 and 1 such that a number of I/O operations associated with sampling nD pages is less than or equal to M if a most precise estimate possible is desired while not exceeding M I/O operations, and $D^{*} = \max (Q, \frac{A - B}{S^{2} + A - (B / Q)})$ if minimal processing time is desired while ensuring that a standard error of an estimated answer to the query does not exceed a value S, and A and B are computed as A=A₁and B=B₁, orA =A₂and B=B₂, or $A = {(\frac{P^{'} R^{'}}{n_{1} + \dots + n_{k}})}^{2} (A_{2} - 2 u A_{3} + u^{2} A_{1}) and$ $B = {(\frac{P^{'} R^{'}}{n_{1} + \dots + n_{k}})}^{2} (B_{2} - 2 u B_{3} + u^{2} B_{1})$ if <
      
      agg>
      
      is equal to COUNT, SUM, or AVERAGE, respectively, where $A_{1} = \frac{1}{P^{'}} (z_{1} + \dots + z_{k}) and B_{1} = \frac{1}{P^{'} R^{'}} (n_{1} + \dots + n_{k}), z_{j} = {(\frac{n_{j}}{R^{'}})}^{2} - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) n_{j}, A_{2} = \frac{1}{P^{'}} (y_{1} + \dots + y_{k}) and B_{2} = \frac{1}{P^{'} R^{'}} (h_{1} + \dots + h_{k}), y_{j} = {(\frac{g_{j}}{R^{'}})}^{2} - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) h_{j}, A_{3} = \frac{1}{P^{'}} (x_{1} + \dots + x_{k}) and B_{3} = \frac{1}{P^{'} R^{'}} (g_{1} + \dots + g_{k}), x_{j} = (\frac{g_{j}}{R^{'}}) (\frac{n_{j}}{R^{'}}) - \frac{1}{R^{'}} (\frac{1}{R^{'}} - 1) g_{j}, u = \frac{g_{1} + \dots + g_{k}}{n_{1} + \dots + n_{k}},$ k is a number of pages sampled in the pilot sample, n_jis a number of rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      , g_jis a sum of the column values from those rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      , and h_jis a sum of the squared column values from those rows sampled from the jth page of the pilot sample that satisfy <
      
      predicate>
      
      .
  - 17. The computer readable medium of claim 15, wherein the SELECT clause of the query contains u>
    - 1 aggregate expressions and P and R are defined as any one of;
  - 18. The computer readable medium of claim 15, wherein a query for sampling is of the form:
    - SELECT <
      
      agg>
      
      (col) FROM t WHERE <
      
      predicate>
      
      ;
      
      there is no desired overall row sampling probability Q;
      
      P and R are defined as any one of;
      
      P=D* and R=1 if a most precise sampling is desired while not exceeding M I/O operations; and
      
      $P = \frac{A}{S^{2} + A}$ and R=1 if minimal processing time is desired while ensuring that a standard error of an estimated answer to the query does not exceed a value S, wherein D* is equal to a largest real number between 0 and 1 such that a number of I/O operations associated with sampling nD* pages is less than or equal toM.

19. A computer system for sampling data from a relational database, comprising:
- a relational database including tables comprising rows and columns, wherein rows are arranged into pages and include column values, and pages are arranged into tables; and
  
  a processor for choosing rows from a relational database for sampling, wherein rows are arranged into pages and include data values, pages are arranged into tables and tables comprise rows and columns;
  
  wherein pages are chosen for sampling according to a probability P and rows on each selected page are chosen for sampling according to a probability R, so that an overall probability of choosing a row for sampling is Q=PR; and
  
  wherein P and R are based on desired processing speed and desired precision.
- View Dependent Claims (20, 21)
- - 20. The computer system of claim 19, wherein R is further based on catalog statistics of the relational database.
  - 21. The computer system of claim 19, wherein P and R are further based on a pilot sample of rows from the relational database.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
International Business Machines Corporation
Original Assignee
International Business Machines Corporation
Inventors
Lohman, Guy Maring, Pirahesh, Mir Hamid, Simmen, David Everett, Haas, Peter Jay, Winer, Michael Jeffrey, Zaharioudakis, Markos, Singh, Ashutosh Vir Vikram

Granted Patent

US 6,993,516 B2
Time in Patent Office

Days
Field of Search
US Class Current

707/5
CPC Class Codes

G06F 16/24556   Aggregation; Duplicate elim...

G06F 16/2462   Approximate or statistical ...

Y10S 707/99932   Access augmentation or opti...

Y10S 707/99936   Pattern matching access

Efficient sampling of a relational database

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

51 Citations

21 Claims

Specification

Solutions

Use Cases

Quick Links

Efficient sampling of a relational database

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

51 Citations

21 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links