Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 10.4.1.3
    • Fix Version/s: 10.6.1.0
    • Component/s: SQL
    • Labels:
      None

      Description

      Provide an implementation of the ROLLUP form of multi-dimensional grouping according to the SQL standard.

      See http://wiki.apache.org/db-derby/OLAPRollupLists for some more detailed information about this aspect of the SQL standard.

      1. fixWhiteSpace.diff
        14 kB
        Bryan Pendleton
      2. IncludesASimpleTest.diff
        14 kB
        Bryan Pendleton
      3. passesRegressionTests.diff
        62 kB
        Bryan Pendleton
      4. prototypeChangeNoTests.diff
        12 kB
        Bryan Pendleton
      5. rewriteGroupByRS.diff
        53 kB
        Bryan Pendleton
      6. rollupNullability.diff
        16 kB
        Bryan Pendleton
      7. setCurrentRow.diff
        62 kB
        Bryan Pendleton
      8. UpdateToTrunkSep2009.diff
        64 kB
        Bryan Pendleton
      9. useAggregateObserver.diff
        60 kB
        Bryan Pendleton
      10. useLookahead.diff
        14 kB
        Bryan Pendleton
      11. withDagsCastTest.diff
        62 kB
        Bryan Pendleton

        Issue Links

          Activity

          Hide
          Bryan Pendleton added a comment -

          My first idea is to try placing the logic for this feature inside GroupedAggregateResultSet. It seems like it should be fairly straightforward (famous last words!) to compute the aggregates for multiple grouping sets in a single pass through the source records.

          Show
          Bryan Pendleton added a comment - My first idea is to try placing the logic for this feature inside GroupedAggregateResultSet. It seems like it should be fairly straightforward (famous last words!) to compute the aggregates for multiple grouping sets in a single pass through the source records.
          Hide
          Bryan Pendleton added a comment -

          Attached is 'prototypeChangeNoTests.diff', which is not for commit.

          This is an experimental change that I made to investigate a possible
          implementation for GROUP BY ROLLUP(...).

          This change:

          • modifies the parser to accept the new syntax
          • modifies GroupByList to have a boolean "rollup" flag
          • modifies the result set factory to pass the GroupByList's rollup
            setting down to the GroupedAggregateResultSet
          • modifies GroupedAggregateResultSet to implement rollup
            processing by computing N total sorts, one for each level of the rollup.

          I'm posting this work-in-process change in the hopes of getting some
          feedback about whether this is a reasonable strategy for the overall implementation.

          The change seems to work in some trivial tests, although there are
          several bugs that I already know about:

          • it doesn't interact properly with index-driven no-sort-required aggregation
          • i'm not sure it handles DISTINCT aggregation properly
          • it doesn't do the "0th level" aggregation on all the columns in the rollup
            However, it does seem to behave reasonably for the simple case of:
            SELECT c1,c2,c3,sum(c4) FROM t1 GROUP BY ROLLUP(c1,c2,c3)
            so I felt sufficiently encouraged to post this partial patch in order to
            give us some "real code" to discuss.

          A particular issue that I'd like to get feedback on is whether the ROLLUP
          case is worth implementing separately, or whether it would be better
          to investigate the more general case of implementing GROUPING SETS
          and CUBE() groupings as part of a single implementation.

          Show
          Bryan Pendleton added a comment - Attached is 'prototypeChangeNoTests.diff', which is not for commit. This is an experimental change that I made to investigate a possible implementation for GROUP BY ROLLUP(...). This change: modifies the parser to accept the new syntax modifies GroupByList to have a boolean "rollup" flag modifies the result set factory to pass the GroupByList's rollup setting down to the GroupedAggregateResultSet modifies GroupedAggregateResultSet to implement rollup processing by computing N total sorts, one for each level of the rollup. I'm posting this work-in-process change in the hopes of getting some feedback about whether this is a reasonable strategy for the overall implementation. The change seems to work in some trivial tests, although there are several bugs that I already know about: it doesn't interact properly with index-driven no-sort-required aggregation i'm not sure it handles DISTINCT aggregation properly it doesn't do the "0th level" aggregation on all the columns in the rollup However, it does seem to behave reasonably for the simple case of: SELECT c1,c2,c3,sum(c4) FROM t1 GROUP BY ROLLUP(c1,c2,c3) so I felt sufficiently encouraged to post this partial patch in order to give us some "real code" to discuss. A particular issue that I'd like to get feedback on is whether the ROLLUP case is worth implementing separately, or whether it would be better to investigate the more general case of implementing GROUPING SETS and CUBE() groupings as part of a single implementation.
          Hide
          Manish Khettry added a comment -

          If I read the diff correctly, you're sorting the same data multiple times? Is it not possible to compute the rollups with a single sort? The wiki page also suggests that this is possible.

          Show
          Manish Khettry added a comment - If I read the diff correctly, you're sorting the same data multiple times? Is it not possible to compute the rollups with a single sort? The wiki page also suggests that this is possible.
          Hide
          Bryan Pendleton added a comment -

          Hi Manish thanks for reading the diff. You are absolutely right that it is possible to compute the rollups with a single sort, but I haven't made that optimization yet. I shall work on improving the wiki to make this clearer.

          As I see it, there are basically 3 ways to perform grouped aggregation, and numerous ways to combine these three variants.
          1) If the records to be grouped are already in sorted order, perhaps due to a scan of an index, or a previous merge-sort-join operation, or a duplicate-eliminating distinct sort, then the grouping operation can be implemented by comparing each pair of records on the grouping attributes; each time a new value of the grouping attributes is encountered, the computation of the previous group can be finalized and emitted. This is the algorithm discussed in the wiki page, and is currently implemented by Derby for a single set of grouping attributes; I have not yet constructed a patch to extend this logic for a ROLLUP set of groups.
          2) An unsorted set of records can be grouped by feeding them into the sorter, configured for duplicate elimination, with a sort observer which aggregates each row's values into the retained row's columns during duplicate processing. Each such sort groups the records by a specific set of grouping attributes. The patch that I constructed uses N sorts to group the records by N different sets of grouping attributes. The input rows are read only once, but then are added to each of the N sorts. This is dramatically more efficient than the alternate query-rewriting algorithm of constructing N GROUP BY statements and then UNION'ing their results together, since in this implementation the input rows are materialized and read only once.
          3) An unsorted set of records can also be grouped by feeding them into a hash table, whose keys are the grouping attributes, with a hash-collision observer which aggregates each row's values into the retained row's columns during duplicate key elimination. This is fundamentally similar to the sort-based technique, with the important difference that at the end of the processing, the rows will NOT be emitted in sorted order.

          Derby currently implements techniques (1) and (2) for grouped aggregate computation; I am not aware of any code which implements a hash-based technique for grouped aggregates in Derby.

          As Manish notes, techniques (1) and (2) can be combined into an algorithm which computes the N ROLLUP groups using a single sort, by first sorting (and aggregating) the rows on their finest level of grouping detail. Then, as the rows are being retrieved in sorted order, the code could detect when a new value of grouping attributes is being retrieved, and could automatically compute that higher level group at that time. Thus if we are computing the GROUP BY ABCD, ABC, AB, and A, we can:

          • sort (and group and aggregate) the data on ABCD
          • For each row we retrieve, we can propagate it up the pipeline to compute the appropriate ABC group, the appropriate AB group, the appropriate A group, and the appropriate all-rows group.

          This algorithm seems to hold the potential for being quite efficient, but I haven't investigated the actual coding yet, and for the time being as an experiment I investigated the easier-to-code but less efficient multiple-sorts algorithm.

          Show
          Bryan Pendleton added a comment - Hi Manish thanks for reading the diff. You are absolutely right that it is possible to compute the rollups with a single sort, but I haven't made that optimization yet. I shall work on improving the wiki to make this clearer. As I see it, there are basically 3 ways to perform grouped aggregation, and numerous ways to combine these three variants. 1) If the records to be grouped are already in sorted order, perhaps due to a scan of an index, or a previous merge-sort-join operation, or a duplicate-eliminating distinct sort, then the grouping operation can be implemented by comparing each pair of records on the grouping attributes; each time a new value of the grouping attributes is encountered, the computation of the previous group can be finalized and emitted. This is the algorithm discussed in the wiki page, and is currently implemented by Derby for a single set of grouping attributes; I have not yet constructed a patch to extend this logic for a ROLLUP set of groups. 2) An unsorted set of records can be grouped by feeding them into the sorter, configured for duplicate elimination, with a sort observer which aggregates each row's values into the retained row's columns during duplicate processing. Each such sort groups the records by a specific set of grouping attributes. The patch that I constructed uses N sorts to group the records by N different sets of grouping attributes. The input rows are read only once, but then are added to each of the N sorts. This is dramatically more efficient than the alternate query-rewriting algorithm of constructing N GROUP BY statements and then UNION'ing their results together, since in this implementation the input rows are materialized and read only once. 3) An unsorted set of records can also be grouped by feeding them into a hash table, whose keys are the grouping attributes, with a hash-collision observer which aggregates each row's values into the retained row's columns during duplicate key elimination. This is fundamentally similar to the sort-based technique, with the important difference that at the end of the processing, the rows will NOT be emitted in sorted order. Derby currently implements techniques (1) and (2) for grouped aggregate computation; I am not aware of any code which implements a hash-based technique for grouped aggregates in Derby. As Manish notes, techniques (1) and (2) can be combined into an algorithm which computes the N ROLLUP groups using a single sort, by first sorting (and aggregating) the rows on their finest level of grouping detail. Then, as the rows are being retrieved in sorted order, the code could detect when a new value of grouping attributes is being retrieved, and could automatically compute that higher level group at that time. Thus if we are computing the GROUP BY ABCD, ABC, AB, and A, we can: sort (and group and aggregate) the data on ABCD For each row we retrieve, we can propagate it up the pipeline to compute the appropriate ABC group, the appropriate AB group, the appropriate A group, and the appropriate all-rows group. This algorithm seems to hold the potential for being quite efficient, but I haven't investigated the actual coding yet, and for the time being as an experiment I investigated the easier-to-code but less efficient multiple-sorts algorithm.
          Hide
          Bryan Pendleton added a comment -

          Working on this issue will entail adding a number of new GROUP BY tests; I'll open a sub-task of this issue to convert the existing lang/groupBy.sql tests to JUnit so that the new tests can be added as part of a more modern framework. Hopefully the DERBY-2151 tool will produce a reasonable first version of that test.

          Show
          Bryan Pendleton added a comment - Working on this issue will entail adding a number of new GROUP BY tests; I'll open a sub-task of this issue to convert the existing lang/groupBy.sql tests to JUnit so that the new tests can be added as part of a more modern framework. Hopefully the DERBY-2151 tool will produce a reasonable first version of that test.
          Hide
          Bryan Pendleton added a comment -

          I've updated the patch to apply properly with the current head of trunk
          and I've also included the beginnings of a functional test, with a single
          positive test and a handful of error-testing tests.

          For the time being, I intend to concentrate on functionality and
          correctness, and on building up a regression test suite. Later, I
          hope to address the performance aspects of the ROLLUP operator.

          Show
          Bryan Pendleton added a comment - I've updated the patch to apply properly with the current head of trunk and I've also included the beginnings of a functional test, with a single positive test and a handful of error-testing tests. For the time being, I intend to concentrate on functionality and correctness, and on building up a regression test suite. Later, I hope to address the performance aspects of the ROLLUP operator.
          Hide
          Knut Anders Hatlen added a comment -

          This issue has had what looks like a fairly complete patch for quite some time. Should we try to get it committed?

          I haven't studied the details of the patch, but the general approach looks fine to me. I think this is a very useful feature even if the performance is suboptimal.

          My only comments after reading the patch, are

          1) If I read http://wiki.apache.org/db-derby/OLAPRollupLists correctly, the set of expected rows returned by the test case lacks one row:

          {null,null,null,"12"}

          2) The patch appears to have been created with a text editor whose tab size is 8, so the new space-indented lines are too far to the right

          Show
          Knut Anders Hatlen added a comment - This issue has had what looks like a fairly complete patch for quite some time. Should we try to get it committed? I haven't studied the details of the patch, but the general approach looks fine to me. I think this is a very useful feature even if the performance is suboptimal. My only comments after reading the patch, are 1) If I read http://wiki.apache.org/db-derby/OLAPRollupLists correctly, the set of expected rows returned by the test case lacks one row: {null,null,null,"12"} 2) The patch appears to have been created with a text editor whose tab size is 8, so the new space-indented lines are too far to the right
          Hide
          Knut Anders Hatlen added a comment -

          One more comment after testing the patch (yes, it still applies cleanly on trunk!):

          The patch doesn't make ROLLUP a reserved keyword, so we can still have columns with that name (which is good, I think). But we cannot group by a column named ROLLUP without quoting the column name:

          ij> create table t2(rollup int, x int);
          0 rows inserted/updated/deleted
          ij> select rollup, sum from t2 group by rollup;
          ERROR 42X01: Syntax error: Encountered "<EOF>" at line 1, column 45.
          Issue the 'help' command for general information on IJ command syntax.
          Any unrecognized commands are treated as potential SQL commands and executed directly.
          Consult your DBMS server reference documentation for details of the SQL syntax supported by your server.
          ij> select rollup, sum from t2 group by "ROLLUP";
          ROLLUP |2
          -----------------------

          0 rows selected

          I think this small incompatibility could be avoided by adding a lookahead in the grammar so that we only try to parse it as a multi-level grouping clause if ROLLUP is followed by a left parenthesis.

          Show
          Knut Anders Hatlen added a comment - One more comment after testing the patch (yes, it still applies cleanly on trunk!): The patch doesn't make ROLLUP a reserved keyword, so we can still have columns with that name (which is good, I think). But we cannot group by a column named ROLLUP without quoting the column name: ij> create table t2(rollup int, x int); 0 rows inserted/updated/deleted ij> select rollup, sum from t2 group by rollup; ERROR 42X01: Syntax error: Encountered "<EOF>" at line 1, column 45. Issue the 'help' command for general information on IJ command syntax. Any unrecognized commands are treated as potential SQL commands and executed directly. Consult your DBMS server reference documentation for details of the SQL syntax supported by your server. ij> select rollup, sum from t2 group by "ROLLUP"; ROLLUP |2 ----------------------- 0 rows selected I think this small incompatibility could be avoided by adding a lookahead in the grammar so that we only try to parse it as a multi-level grouping clause if ROLLUP is followed by a left parenthesis.
          Hide
          Knut Anders Hatlen added a comment -

          I converted this issue to a top-level issue, since it's not really a sub-task of DERBY-581 (Modify SQL to skip N rows of the result and return the next M rows).

          Show
          Knut Anders Hatlen added a comment - I converted this issue to a top-level issue, since it's not really a sub-task of DERBY-581 (Modify SQL to skip N rows of the result and return the next M rows).
          Hide
          Bryan Pendleton added a comment -

          Hi Knut, thanks for the comments and review! I kind of lost track of this issue, but would
          like to return to it and get it completed. Your suggestions will be most helpful in that effort.

          For the time being, I'm sort of consumed with DERBY-2487, but after that work is complete
          I'll revisit this work and see if I can figure out what's left to do.

          Show
          Bryan Pendleton added a comment - Hi Knut, thanks for the comments and review! I kind of lost track of this issue, but would like to return to it and get it completed. Your suggestions will be most helpful in that effort. For the time being, I'm sort of consumed with DERBY-2487 , but after that work is complete I'll revisit this work and see if I can figure out what's left to do.
          Hide
          Bryan Pendleton added a comment -

          Thanks Knut for the suggestions and encouragement! Attached is
          'useLookahead.diff', which:

          • brings the patch up to date with the current trunk
          • adds a new test as Knut suggested to investigate the behavior when trying
            to GROUP BY a column named ROLLUP
          • adds a LOOKAHEAD instruction to the ROLLUP section of the grammar
            to assist with distinguishing between a ROLLUP grouping and a ROLLUP column.

          I think that the next step is to add a number of additional tests, and also some documentation. It would also be nice to investigate the performance impacts
          of the feature, as well as the opportunities for further performance improvements.

          Show
          Bryan Pendleton added a comment - Thanks Knut for the suggestions and encouragement! Attached is 'useLookahead.diff', which: brings the patch up to date with the current trunk adds a new test as Knut suggested to investigate the behavior when trying to GROUP BY a column named ROLLUP adds a LOOKAHEAD instruction to the ROLLUP section of the grammar to assist with distinguishing between a ROLLUP grouping and a ROLLUP column. I think that the next step is to add a number of additional tests, and also some documentation. It would also be nice to investigate the performance impacts of the feature, as well as the opportunities for further performance improvements.
          Hide
          Bryan Pendleton added a comment -

          Attached 'fixWhiteSpace.diff' patch fixes the tabs-vs-spaces
          whitespace problems in GroupedAggregateResultSet.java,
          and also fixes the off-by-one error that, as Knut noticed, was
          failing to do the all-levels roll up of all the results into a single master.

          Show
          Bryan Pendleton added a comment - Attached 'fixWhiteSpace.diff' patch fixes the tabs-vs-spaces whitespace problems in GroupedAggregateResultSet.java, and also fixes the off-by-one error that, as Knut noticed, was failing to do the all-levels roll up of all the results into a single master.
          Hide
          Knut Anders Hatlen added a comment -

          Hi Bryan,

          fixWhiteSpace.diff looks like a fine first increment. I only have some minor comments:

          a) There are still some whitespace issues (too much indentation) in some of the files. Looking at the patch with "expand -t4 fixWhiteSpace.diff | less" should make them easy to spot.

          b) I haven't checked what the standard says, so my expectation may be wrong, but I'd expect a different result from a query like this (using the RU table from the test case in OLAPTest):

          ij> select a, count from ru where 1<>1 group by rollup(a);
          A |2
          -----------------------

          0 rows selected

          My expectation is that this query should return one row:

          {null, 0}

          .

          c) I think the lookahead needs to check for getToken(1).kind == ROLLUP in addition to the check for getToken(2). The current lookahead breaks some statements.

          Without patch:

          ij> select count from ru group by mod(a,b);
          1
          -----------
          3
          2

          2 rows selected

          With patch:

          ij> select count from ru group by mod(a,b);
          ERROR 42X01: Syntax error: Encountered "mod" at line 1, column 34.

          d) The result set meta-data gets the nullability for the GROUP BY columns wrong. For example, in the query below, the meta-data says that all the columns are non-nullable, but the result does contain nulls:

          ij> select 1,2,3,count(d) from ru group by rollup(1,2,3);
          1 |2 |3 |4
          -----------------------------------------------
          1 |2 |3 |5
          1 |2 |NULL |5
          1 |NULL |NULL |5
          NULL |NULL |NULL |5

          4 rows selected

          Show
          Knut Anders Hatlen added a comment - Hi Bryan, fixWhiteSpace.diff looks like a fine first increment. I only have some minor comments: a) There are still some whitespace issues (too much indentation) in some of the files. Looking at the patch with "expand -t4 fixWhiteSpace.diff | less" should make them easy to spot. b) I haven't checked what the standard says, so my expectation may be wrong, but I'd expect a different result from a query like this (using the RU table from the test case in OLAPTest): ij> select a, count from ru where 1<>1 group by rollup(a); A |2 ----------------------- 0 rows selected My expectation is that this query should return one row: {null, 0} . c) I think the lookahead needs to check for getToken(1).kind == ROLLUP in addition to the check for getToken(2). The current lookahead breaks some statements. Without patch: ij> select count from ru group by mod(a,b); 1 ----------- 3 2 2 rows selected With patch: ij> select count from ru group by mod(a,b); ERROR 42X01: Syntax error: Encountered "mod" at line 1, column 34. d) The result set meta-data gets the nullability for the GROUP BY columns wrong. For example, in the query below, the meta-data says that all the columns are non-nullable, but the result does contain nulls: ij> select 1,2,3,count(d) from ru group by rollup(1,2,3); 1 |2 |3 |4 ----------------------------------------------- 1 |2 |3 |5 1 |2 |NULL |5 1 |NULL |NULL |5 NULL |NULL |NULL |5 4 rows selected
          Hide
          Bryan Pendleton added a comment -

          Hi Knut, thanks again for the notes and observations.

          Your point about the handling of empty result sets is intriguing.

          Consider the short script shown below. I'm confused about why the
          second SELECT statement returns 1 row, but the first and third
          SELECT statements return 0 rows.

          Do you understand why this behavior exists, and whether it's appropriate?

          ij> create table t (a int, b int);
          0 rows inserted/updated/deleted
          ij> select sum(b) from t group by a;
          1
          -----------

          0 rows selected
          ij> select sum(b) from t;
          1
          -----------
          NULL

          1 row selected
          ij> insert into t values (1,1);
          1 row inserted/updated/deleted
          ij> select sum(b) from t where 1 <> 1 group by a;
          1
          -----------

          0 rows selected

          Show
          Bryan Pendleton added a comment - Hi Knut, thanks again for the notes and observations. Your point about the handling of empty result sets is intriguing. Consider the short script shown below. I'm confused about why the second SELECT statement returns 1 row, but the first and third SELECT statements return 0 rows. Do you understand why this behavior exists, and whether it's appropriate? ij> create table t (a int, b int); 0 rows inserted/updated/deleted ij> select sum(b) from t group by a; 1 ----------- 0 rows selected ij> select sum(b) from t; 1 ----------- NULL 1 row selected ij> insert into t values (1,1); 1 row inserted/updated/deleted ij> select sum(b) from t where 1 <> 1 group by a; 1 ----------- 0 rows selected
          Hide
          Bryan Pendleton added a comment -

          Added more tests, many of which were suggested by Knut. Changed GroupByNode
          to set nullability on for ROLLUP group by statements. Fixed some more whitespace.

          I don't understand the behavior on empty result sets. The test includes some test
          cases in that area, but I'm not sure if the results are correct.

          Still need to add test cases in the area of sort-avoidance group by, distinct group by,
          and probably other areas.

          Show
          Bryan Pendleton added a comment - Added more tests, many of which were suggested by Knut. Changed GroupByNode to set nullability on for ROLLUP group by statements. Fixed some more whitespace. I don't understand the behavior on empty result sets. The test includes some test cases in that area, but I'm not sure if the results are correct. Still need to add test cases in the area of sort-avoidance group by, distinct group by, and probably other areas.
          Hide
          Knut Anders Hatlen added a comment -

          I think the results in your examples without rollup are correct. At least I see the same same results when I try the statements in PostgreSQL. When you have GROUP BY and no rows in the table, there are no groups, so the result should be empty.

          The wiki page says that a rollup query is semantically equivalent to a union where the last subquery in the union has no group by. I think this means that this query

          SELECT a, count FROM T GROUP BY ROLLUP(a)

          should be equivalent to

          SELECT a, COUNT FROM T GROUP BY (a)
          UNION
          SELECT NULL, COUNT FROM T

          Since SELECT NULL, COUNT FROM T always returns one row, the union query should always return at least one row.

          Show
          Knut Anders Hatlen added a comment - I think the results in your examples without rollup are correct. At least I see the same same results when I try the statements in PostgreSQL. When you have GROUP BY and no rows in the table, there are no groups, so the result should be empty. The wiki page says that a rollup query is semantically equivalent to a union where the last subquery in the union has no group by. I think this means that this query SELECT a, count FROM T GROUP BY ROLLUP(a) should be equivalent to SELECT a, COUNT FROM T GROUP BY (a) UNION SELECT NULL, COUNT FROM T Since SELECT NULL, COUNT FROM T always returns one row, the union query should always return at least one row.
          Hide
          Bryan Pendleton added a comment -

          I agree with your analysis, and will try to work on such an implementation.

          Note that, as far as I can tell, SELECT NULL, COUNT FROM T is not actually legal in Derby.
          However, the roughly similar queries SELECT CAST(NULL AS INT), COUNT FROM T and
          SELECT 'NULL', COUNT FROM T are legal, and, as you say, return the result set

          {"NULL", 0}

          I'm not sure where I got this "semantically equivalent to a union" terminology from when I wrote
          the wiki page. It's certainly true that the original Jim Gray "Data Cube" paper from 1996 uses the
          technique of defining ROLLUP in terms of an equivalent UNION query, but I don't think that's
          how the actual SQL Standard ended up defining ROLLUP. However, I find the SQL Standard hard to read.

          In the SQL Standard, ROLLUP is defined in terms of an equivalent GROUPING SETS query, and
          GROUPING SETS includes the (new) syntax "GROUP BY ()". NOTE 137 of the SQL 2003 spec, in section 7.9, says:

          The result of the transform is to replace RL with a <grouping sets specification> that contains
          a <grouping set> for every initial sublist of the <ordinary grouping set list> of the <rollup list>,
          obtained by dropping <ordinary grouping set>s from the right, one by one, and concatenating
          each <ordinary grouping set list> so obtained. The <empty grouping set> is regarded as the
          shortest such initial sublist.

          So GROUP BY ROLLUP(a) is (internally) transformed into GROUP BY GROUPING SETS( (a), () )

          Then, elsewhere in 7.9, in the "General Rules" section, it says:

          If there are no grouping columns, then the result of the <group by clause> is the grouped table
          consisting of T as its only group.

          So I think that the SQL Standard says that

          SELECT a, count FROM T GROUP BY ROLLUP(a)

          should be equivalent to:

          SELECT a, COUNT FROM T GROUP BY (a)
          UNION
          SELECT CAST ( NULL AS INT), COUNT FROM T GROUP BY ()

          So, anyway, I think that the wiki page is somewhat inaccurate in this respect, and doesn't truly
          obey the SQL Standard, because as you say the wiki page says that the last subquery in the
          union has no group by, but the SQL Standard says that the last subquery in the union has GROUP BY ().

          I still think that your analysis is correct, and will try to make the implementation comply.

          Show
          Bryan Pendleton added a comment - I agree with your analysis, and will try to work on such an implementation. Note that, as far as I can tell, SELECT NULL, COUNT FROM T is not actually legal in Derby. However, the roughly similar queries SELECT CAST(NULL AS INT), COUNT FROM T and SELECT 'NULL', COUNT FROM T are legal, and, as you say, return the result set {"NULL", 0} I'm not sure where I got this "semantically equivalent to a union" terminology from when I wrote the wiki page. It's certainly true that the original Jim Gray "Data Cube" paper from 1996 uses the technique of defining ROLLUP in terms of an equivalent UNION query, but I don't think that's how the actual SQL Standard ended up defining ROLLUP. However, I find the SQL Standard hard to read. In the SQL Standard, ROLLUP is defined in terms of an equivalent GROUPING SETS query, and GROUPING SETS includes the (new) syntax "GROUP BY ()". NOTE 137 of the SQL 2003 spec, in section 7.9, says: The result of the transform is to replace RL with a <grouping sets specification> that contains a <grouping set> for every initial sublist of the <ordinary grouping set list> of the <rollup list>, obtained by dropping <ordinary grouping set>s from the right, one by one, and concatenating each <ordinary grouping set list> so obtained. The <empty grouping set> is regarded as the shortest such initial sublist. So GROUP BY ROLLUP(a) is (internally) transformed into GROUP BY GROUPING SETS( (a), () ) Then, elsewhere in 7.9, in the "General Rules" section, it says: If there are no grouping columns, then the result of the <group by clause> is the grouped table consisting of T as its only group. So I think that the SQL Standard says that SELECT a, count FROM T GROUP BY ROLLUP(a) should be equivalent to: SELECT a, COUNT FROM T GROUP BY (a) UNION SELECT CAST ( NULL AS INT), COUNT FROM T GROUP BY () So, anyway, I think that the wiki page is somewhat inaccurate in this respect, and doesn't truly obey the SQL Standard, because as you say the wiki page says that the last subquery in the union has no group by, but the SQL Standard says that the last subquery in the union has GROUP BY (). I still think that your analysis is correct, and will try to make the implementation comply.
          Hide
          Bryan Pendleton added a comment -

          I've been spending a lot of time thinking about how to avoid unnecessary
          sorts in the ROLLUP case, about how to handle DISTINCT aggregates,
          and about how to handle the already-in-sorted-order case.

          The result is the attached 'rewriteGroupByRS.diff', which contains an
          almost-completely-rewritten GroupedAggregateResultSet.java, together
          with a lot of new test cases in OLAPTest.java.

          The new code no longer uses the sort-observer style of aggregate
          computation. Instead, the code sorts the input data once, if it isn't already
          in sorted order, then computes all the aggregates, at all the ROLLUP levels,
          in a single pass over the (sorted) input data. DISTINCT aggregates are
          processed using in-memory hash tables of the unique values, which
          means that we can now support multiple DISTINCT aggregates in
          a GROUP BY statement. (However, I'm not sure that DISTINCT aggregates
          are really very useful, so I'm not sure that this is very much of a compelling
          new feature.)

          There are still some bugs in the code, as I have about 6 total failures in
          the regression suites that I have to track down and study.

          But, I think that this is a substantial improvement over the previous patch,
          as it handles the major unresolved issues from the previous reviews:

          • multiple sorts are no longer needed
          • in-order data now works correctly with ROLLUP
          • DISTINCT aggregates now work correctly with ROLLUP

          The patch isn't ready for commit, and probably isn't worth reviewing, at least
          until I get the regression test failures resolved, and take a pass over the patch
          to resolve any FIXME comments that I left in it.

          However, any feedback is most appreciated!

          Show
          Bryan Pendleton added a comment - I've been spending a lot of time thinking about how to avoid unnecessary sorts in the ROLLUP case, about how to handle DISTINCT aggregates, and about how to handle the already-in-sorted-order case. The result is the attached 'rewriteGroupByRS.diff', which contains an almost-completely-rewritten GroupedAggregateResultSet.java, together with a lot of new test cases in OLAPTest.java. The new code no longer uses the sort-observer style of aggregate computation. Instead, the code sorts the input data once, if it isn't already in sorted order, then computes all the aggregates, at all the ROLLUP levels, in a single pass over the (sorted) input data. DISTINCT aggregates are processed using in-memory hash tables of the unique values, which means that we can now support multiple DISTINCT aggregates in a GROUP BY statement. (However, I'm not sure that DISTINCT aggregates are really very useful, so I'm not sure that this is very much of a compelling new feature.) There are still some bugs in the code, as I have about 6 total failures in the regression suites that I have to track down and study. But, I think that this is a substantial improvement over the previous patch, as it handles the major unresolved issues from the previous reviews: multiple sorts are no longer needed in-order data now works correctly with ROLLUP DISTINCT aggregates now work correctly with ROLLUP The patch isn't ready for commit, and probably isn't worth reviewing, at least until I get the regression test failures resolved, and take a pass over the patch to resolve any FIXME comments that I left in it. However, any feedback is most appreciated!
          Hide
          Bryan Pendleton added a comment -

          Attached is 'passesRegressionTests.diff', a fairly full-formed patch
          proposal for this issue.

          The regression tests now pass for me in my environment, including
          the new tests added in this patch.

          I've still got some cleanup to do, in terms of whitespace checking,
          FIXME resolving, and so forth.

          But I'm starting to think I'm getting close to a commit-worthy patch.

          So if anyone has time to take a look at this most recent patch,
          feedback would be very much appreciated.

          Show
          Bryan Pendleton added a comment - Attached is 'passesRegressionTests.diff', a fairly full-formed patch proposal for this issue. The regression tests now pass for me in my environment, including the new tests added in this patch. I've still got some cleanup to do, in terms of whitespace checking, FIXME resolving, and so forth. But I'm starting to think I'm getting close to a commit-worthy patch. So if anyone has time to take a look at this most recent patch, feedback would be very much appreciated.
          Hide
          Knut Anders Hatlen added a comment -

          Hi Bryan,

          Thanks for adding all the test cases. I haven't dived into the details of the latest patch, but I have a couple of questions:

          The patch changes how we compute aggregates for the non-rollup case as well, and a comment in the patch says that the old technique was efficient. Have you planned to run tests to verify that we don't introduce any performance regressions for non-rollup group bys?

          Some of the run-time statistics for existing queries have changed, returning more rows from the sorts. Is that expected?

          What are the memory requirements for the in-memory hash table? Does it hold one copy of every unique value in the table/query? Can it run out of memory if the query accesses a very large table?

          Show
          Knut Anders Hatlen added a comment - Hi Bryan, Thanks for adding all the test cases. I haven't dived into the details of the latest patch, but I have a couple of questions: The patch changes how we compute aggregates for the non-rollup case as well, and a comment in the patch says that the old technique was efficient. Have you planned to run tests to verify that we don't introduce any performance regressions for non-rollup group bys? Some of the run-time statistics for existing queries have changed, returning more rows from the sorts. Is that expected? What are the memory requirements for the in-memory hash table? Does it hold one copy of every unique value in the table/query? Can it run out of memory if the query accesses a very large table?
          Hide
          Bryan Pendleton added a comment -

          Hi Knut, thanks again for having a look at the patch. Your help is much appreciated!

          I think that writing a simple GROUP BY benchmark would be an excellent next step. Is there such a benchmark readily available? If not, I'll put one together.

          The changes to the run-time statistics are precisely because the algorithm has changed: instead of the sort-observer technique, we now always compute aggregates in-line, so the sort step no longer "collapses" groups and the same number of rows are output from the sort as are input, whereas before the sorter would perform the grouping as a side effect, and the number of output rows was equal to the number of groups. So yes the behavior change in the statistics is expected.

          The in-memory hash tables are only used for DISTINCT aggregates, and will hold one copy of every unique value of that particular column in that particular group. They could indeed run out of memory if the distribution of data was just right. I don't have a good intuition for (a) how often DISTINCT aggregates are used, (b) how many distinct values there tend to be per group, and (c) what sort of data types are used for DISTINCT aggregates. In my benchmark, I can try to construct a DISTINCT aggregate which uses an inordinate amount of memory, and we can see how it behaves.

          Show
          Bryan Pendleton added a comment - Hi Knut, thanks again for having a look at the patch. Your help is much appreciated! I think that writing a simple GROUP BY benchmark would be an excellent next step. Is there such a benchmark readily available? If not, I'll put one together. The changes to the run-time statistics are precisely because the algorithm has changed: instead of the sort-observer technique, we now always compute aggregates in-line, so the sort step no longer "collapses" groups and the same number of rows are output from the sort as are input, whereas before the sorter would perform the grouping as a side effect, and the number of output rows was equal to the number of groups. So yes the behavior change in the statistics is expected. The in-memory hash tables are only used for DISTINCT aggregates, and will hold one copy of every unique value of that particular column in that particular group. They could indeed run out of memory if the distribution of data was just right. I don't have a good intuition for (a) how often DISTINCT aggregates are used, (b) how many distinct values there tend to be per group, and (c) what sort of data types are used for DISTINCT aggregates. In my benchmark, I can try to construct a DISTINCT aggregate which uses an inordinate amount of memory, and we can see how it behaves.
          Hide
          Knut Anders Hatlen added a comment -

          Hi Bryan,

          I'm not aware of any GROUP BY benchmarks that we can use, so I guess we'll have to write a simple one ourselves. The reason why I asked was that it wasn't quite clear to me (well, it still isn't... ) whether your comment about aggregate sort observers being an efficient technique meant that you thought the new technique was less efficient.

          As to the hash tables, one alternative is to use a BackingStoreHashTable, which keeps the data in a HashMap up to a certain point, after which it spills data to disk (or at least to the page cache). It'll probably increase the overhead, though.

          Show
          Knut Anders Hatlen added a comment - Hi Bryan, I'm not aware of any GROUP BY benchmarks that we can use, so I guess we'll have to write a simple one ourselves. The reason why I asked was that it wasn't quite clear to me (well, it still isn't... ) whether your comment about aggregate sort observers being an efficient technique meant that you thought the new technique was less efficient. As to the hash tables, one alternative is to use a BackingStoreHashTable, which keeps the data in a HashMap up to a certain point, after which it spills data to disk (or at least to the page cache). It'll probably increase the overhead, though.
          Hide
          Bryan Pendleton added a comment -

          Indeed, I am concerned that there may be some circumstances where the new technique
          is less efficient. An example might be a case where there is a large amount of data to be
          processed, but a very small number of groups; in this case, most of the raw data ends up
          being discarded during the GROUP BY processing, and the sort-observer technique will
          discard the unneeded data sooner, which means it may have a substantial edge over the
          new algorithm. However, other circumstances, such as those in which an index exists, and
          thus the data can be processed in sorted order automatically, and those in which the data
          is relatively small, and thus is not expensive to sort, and those in which there is a lot of data,
          but there are also many different values for the grouping column, may not see much impact at all.

          And, I am just guessing about the performance impacts; I don't know how important
          this distinction will be, given the multitude of other things that occur during query processing.

          Earlier in the project, I intended to support multiple algorithms. However, I then realized:

          • we'd have to have multiple sets of code for the same functionality
          • we'd have to have some way of determining, at runtime, which implementation to choose.

          Both problems seemed quite troubling, the second problem seemed very important,
          because if the selection of the appropriate algorithm is based on information about
          the size and distribution of the data being processed by the query, then the decision ought
          to be made by the optimizer, which appeared like it would dramatically increase the
          complexity of this project.

          So it would be great if the single implementation was "good enough" for the queries we
          expect to run.

          I'll try to put a benchmark together and we can see what the results say, and then we'll
          have a better idea of how big a problem we have here.

          Show
          Bryan Pendleton added a comment - Indeed, I am concerned that there may be some circumstances where the new technique is less efficient. An example might be a case where there is a large amount of data to be processed, but a very small number of groups; in this case, most of the raw data ends up being discarded during the GROUP BY processing, and the sort-observer technique will discard the unneeded data sooner, which means it may have a substantial edge over the new algorithm. However, other circumstances, such as those in which an index exists, and thus the data can be processed in sorted order automatically, and those in which the data is relatively small, and thus is not expensive to sort, and those in which there is a lot of data, but there are also many different values for the grouping column, may not see much impact at all. And, I am just guessing about the performance impacts; I don't know how important this distinction will be, given the multitude of other things that occur during query processing. Earlier in the project, I intended to support multiple algorithms. However, I then realized: we'd have to have multiple sets of code for the same functionality we'd have to have some way of determining, at runtime, which implementation to choose. Both problems seemed quite troubling, the second problem seemed very important, because if the selection of the appropriate algorithm is based on information about the size and distribution of the data being processed by the query, then the decision ought to be made by the optimizer, which appeared like it would dramatically increase the complexity of this project. So it would be great if the single implementation was "good enough" for the queries we expect to run. I'll try to put a benchmark together and we can see what the results say, and then we'll have a better idea of how big a problem we have here.
          Hide
          Bryan Pendleton added a comment -

          Wow I've been busy recently, and haven't had time to work on this much.
          I'm going to open a subtask of this issue to track the contribution of a small
          benchmark to measure GROUP BY performance.

          Show
          Bryan Pendleton added a comment - Wow I've been busy recently, and haven't had time to work on this much. I'm going to open a subtask of this issue to track the contribution of a small benchmark to measure GROUP BY performance.
          Hide
          Dag H. Wanvik added a comment -

          Note: the latest patch is out-of-date, it did not apply cleanly on trunk; two small conflicts
          but I could resolve them easily so I am able to look at the patch.

          Show
          Dag H. Wanvik added a comment - Note: the latest patch is out-of-date, it did not apply cleanly on trunk; two small conflicts but I could resolve them easily so I am able to look at the patch.
          Hide
          Dag H. Wanvik added a comment -

          Playing with the latest patch, I notice something that puzzles me (totally contrived example :

          > describe t;
          COLUMN_NAME |TYPE_NAME|DEC&|NUM&|COLUM&|COLUMN_DEF|CHAR_OCTE&|IS_NULL&
          ------------------------------------------------------------------------------
          C |VARCHAR |NULL|NULL|2 |NULL |4 |NO
          C2 |VARCHAR |NULL|NULL|2 |NULL |4 |YES
          I |INTEGER |0 |10 |10 |NULL |NULL |YES

          with a few columns:

          > select * from t
          C |C2 |I
          -------------------
          aa|NULL|NULL
          bb|NULL|NULL

          Then I try this:

          > select c,c2,sum from t group by rollup (c,c2)

          and I see:

          C |C2 |3
          ---------------------
          aa |NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          aa |NULL|NULL
          NULL|NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          bb |NULL|NULL
          bb |NULL|NULL

          which is I think is as expected. But then I tried:

          ij> select cast(c as varchar(2)),c2,sum from t group by rollup (c,c2)

          but now I see:

          1 |C2 |3
          ---------------------
          aa |NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          aa |NULL|NULL
          bb |NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          bb |NULL|NULL
          bb |NULL|NULL

          Notice that the third row is now different (equal to row four). Is this correct?

          If I embed this group by into a subquery:

          ij> select cast(x as varchar(2)),y,z from (select c,c2,sum from t group by rollup (c,c2)) t(x,y,z)

          I see again the row with null, null, null:

          1 |Y |Z
          -------------------
          aa|NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          aa|NULL|NULL
          N&|NULL|NULL
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          WARNING 01003: Null values were eliminated from the argument of a column function.
          bb|NULL|NULL
          bb|NULL|NULL

          but this time, the nullability of column 1 seems wrong (notice the
          "N&" - ij will use two columns here (VARCHAR(2)) if it thinks column can't contain
          a NULL which, of course, needs 4 columns to print). This could be
          related to the problem Knut is working on under DERBY-4284, though.

          Show
          Dag H. Wanvik added a comment - Playing with the latest patch, I notice something that puzzles me (totally contrived example : > describe t; COLUMN_NAME |TYPE_NAME|DEC&|NUM&|COLUM&|COLUMN_DEF|CHAR_OCTE&|IS_NULL& ------------------------------------------------------------------------------ C |VARCHAR |NULL|NULL|2 |NULL |4 |NO C2 |VARCHAR |NULL|NULL|2 |NULL |4 |YES I |INTEGER |0 |10 |10 |NULL |NULL |YES with a few columns: > select * from t C |C2 |I ------------------- aa|NULL|NULL bb|NULL|NULL Then I try this: > select c,c2,sum from t group by rollup (c,c2) and I see: C |C2 |3 --------------------- aa |NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. aa |NULL|NULL NULL|NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. bb |NULL|NULL bb |NULL|NULL which is I think is as expected. But then I tried: ij> select cast(c as varchar(2)),c2,sum from t group by rollup (c,c2) but now I see: 1 |C2 |3 --------------------- aa |NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. aa |NULL|NULL bb |NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. bb |NULL|NULL bb |NULL|NULL Notice that the third row is now different (equal to row four). Is this correct? If I embed this group by into a subquery: ij> select cast(x as varchar(2)),y,z from (select c,c2,sum from t group by rollup (c,c2)) t(x,y,z) I see again the row with null, null, null: 1 |Y |Z ------------------- aa|NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. aa|NULL|NULL N&|NULL|NULL WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. WARNING 01003: Null values were eliminated from the argument of a column function. bb|NULL|NULL bb|NULL|NULL but this time, the nullability of column 1 seems wrong (notice the "N&" - ij will use two columns here (VARCHAR(2)) if it thinks column can't contain a NULL which, of course, needs 4 columns to print). This could be related to the problem Knut is working on under DERBY-4284 , though.
          Hide
          Bryan Pendleton added a comment -

          Thanks for the review and comments, Dag!

          I'm not sure what's going on with the queries you posted, but they are quite
          interesting, and I'll try to investigate them in more detail.

          I'll also try to post an updated patch with the merge conflicts resolved.

          Show
          Bryan Pendleton added a comment - Thanks for the review and comments, Dag! I'm not sure what's going on with the queries you posted, but they are quite interesting, and I'll try to investigate them in more detail. I'll also try to post an updated patch with the merge conflicts resolved.
          Hide
          Dag H. Wanvik added a comment -

          I found the patch accessible, easy to follow, thanks Bryan!
          Interesting! Nice extension to Derby I think.

          On a first pass thru I noticed little beyond missing javadocs, some
          segments with 8 wide tabs, some debug printing left, which is all fine at
          this stage. The approach look solid to me. I can see the uncertainty
          about the performance in the pure group by case, but I suspect that
          since you do sort avoidance when possible, it is still ok, but your
          performance tests should cast light on that.

          I would be nice to define N in the initial comment in "then there are
          N+1 entries in resultRows" in GroupedAggregateResultSet.

          Did you and Knut resolve the discussion about whether the statement
          "select b, sum(a) from ru where 1<>1 group by rollup(b)" should have
          zero result row or one? It wasn't quite clear from reading the threads
          here. The test makes an empty rs the canon in this case.

          I'll dig in further into the patch logic next.

          Show
          Dag H. Wanvik added a comment - I found the patch accessible, easy to follow, thanks Bryan! Interesting! Nice extension to Derby I think. On a first pass thru I noticed little beyond missing javadocs, some segments with 8 wide tabs, some debug printing left, which is all fine at this stage. The approach look solid to me. I can see the uncertainty about the performance in the pure group by case, but I suspect that since you do sort avoidance when possible, it is still ok, but your performance tests should cast light on that. I would be nice to define N in the initial comment in "then there are N+1 entries in resultRows" in GroupedAggregateResultSet. Did you and Knut resolve the discussion about whether the statement "select b, sum(a) from ru where 1<>1 group by rollup(b)" should have zero result row or one? It wasn't quite clear from reading the threads here. The test makes an empty rs the canon in this case. I'll dig in further into the patch logic next.
          Hide
          Bryan Pendleton added a comment -

          Given the performance results I noticed in DERBY-4363, I think that the next step is to prepare
          a patch which uses the old-style aggregation-in-the-sort-observer technique for non-ROLLUP
          queries, but which uses the new sort-it-once-and-aggregate-at-multiple-levels-in-one-pass
          technique for ROLLUP queries.

          At the same time, I'll also need to resolve the merge conflicts and attend to the other review comments.

          Show
          Bryan Pendleton added a comment - Given the performance results I noticed in DERBY-4363 , I think that the next step is to prepare a patch which uses the old-style aggregation-in-the-sort-observer technique for non-ROLLUP queries, but which uses the new sort-it-once-and-aggregate-at-multiple-levels-in-one-pass technique for ROLLUP queries. At the same time, I'll also need to resolve the merge conflicts and attend to the other review comments.
          Hide
          Bryan Pendleton added a comment -

          Attached 'UpdateToTrunkSep2009.diff' patch does two things:
          1) Updates the patch to the current trunk, and resolves some merge conflicts.
          2) Restores the use of AggregateSortObserver for the common case of:

          • GROUP BY
          • no ROLLUP
          • input data is NOT already in sorted order
          • no DISTINCT aggregates.

          However, I've got some test failures to investigate.

          And, I still haven't investigated the review comments from Dag and Knut

          And, I haven't yet re-run the performance tests to see if the performance is improved

          But here's the patch anyway, for safekeeping and to record where the work is going.

          Show
          Bryan Pendleton added a comment - Attached 'UpdateToTrunkSep2009.diff' patch does two things: 1) Updates the patch to the current trunk, and resolves some merge conflicts. 2) Restores the use of AggregateSortObserver for the common case of: GROUP BY no ROLLUP input data is NOT already in sorted order no DISTINCT aggregates. However, I've got some test failures to investigate. And, I still haven't investigated the review comments from Dag and Knut And, I haven't yet re-run the performance tests to see if the performance is improved But here's the patch anyway, for safekeeping and to record where the work is going.
          Hide
          Bryan Pendleton added a comment -

          Attached 'useAggregateObserver.diff' has one major change from the
          previous patch proposal: it restores the use of the AggregateSortObserver
          for the following common and important special case:

          • the input data is not already in sorted order
          • the GROUP BY does not use ROLLUP
          • the GROUP BY does not use distinct aggregates

          The patch is also up to date with current trunk, and resolves some merge conflicts.

          This revised patch passes all the regression tests, including the new ROLLUP tests.

          More importantly, this revised patch matches the current trunk in performance
          on the DERBY-4363 benchmark of GROUP BY performance.

          I still have to investigate the other issues raised during the previous round of code
          review, but this patch seemed to be at a state worth posting so here it is.

          Show
          Bryan Pendleton added a comment - Attached 'useAggregateObserver.diff' has one major change from the previous patch proposal: it restores the use of the AggregateSortObserver for the following common and important special case: the input data is not already in sorted order the GROUP BY does not use ROLLUP the GROUP BY does not use distinct aggregates The patch is also up to date with current trunk, and resolves some merge conflicts. This revised patch passes all the regression tests, including the new ROLLUP tests. More importantly, this revised patch matches the current trunk in performance on the DERBY-4363 benchmark of GROUP BY performance. I still have to investigate the other issues raised during the previous round of code review, but this patch seemed to be at a state worth posting so here it is.
          Hide
          Knut Anders Hatlen added a comment -

          I haven't had time to look at the patch yet, but I finally found some
          time to check what the SQL:2003 standard says about ROLLUP. What I
          noticed was that the syntax was somewhat more complex than what the
          patch implements. A <rollup list> is a <grouping element>, and a
          <group by clause> takes a a <grouping element list> which may contain
          many <grouping element>s. So if I understand the syntax correctly,
          these GROUP BY clauses should be allowed:

          GROUP BY ROLLUP(a,b), ROLLUP(c,d)

          GROUP BY a, ROLLUP(c,d)

          I haven't checked what these clauses actually mean, though.

          There's also an example in the syntax rules with another variation
          that's not accepted by the current patch:

          > NOTE 137 — (...) For example, "ROLLUP ( (A, B), (C, D) )" is
          > equivalent to "GROUPING SETS ( (A, B, C, D), (A, B), () )".

          I think it is OK to support just a subset of what the standard allows,
          but we should probably try to find out what the non-supported syntax
          means and if it is possible to fit it into the current approach
          somehow.

          (Plain non-rollup group bys are also more restrictive in Derby than in
          the standard. For instance, the standard allows constructs like GROUP
          BY (a, b), and GROUP BY a, (b, c), and even GROUP BY (), which are not
          accepted by Derby.)

          Show
          Knut Anders Hatlen added a comment - I haven't had time to look at the patch yet, but I finally found some time to check what the SQL:2003 standard says about ROLLUP. What I noticed was that the syntax was somewhat more complex than what the patch implements. A <rollup list> is a <grouping element>, and a <group by clause> takes a a <grouping element list> which may contain many <grouping element>s. So if I understand the syntax correctly, these GROUP BY clauses should be allowed: GROUP BY ROLLUP(a,b), ROLLUP(c,d) GROUP BY a, ROLLUP(c,d) I haven't checked what these clauses actually mean, though. There's also an example in the syntax rules with another variation that's not accepted by the current patch: > NOTE 137 — (...) For example, "ROLLUP ( (A, B), (C, D) )" is > equivalent to "GROUPING SETS ( (A, B, C, D), (A, B), () )". I think it is OK to support just a subset of what the standard allows, but we should probably try to find out what the non-supported syntax means and if it is possible to fit it into the current approach somehow. (Plain non-rollup group bys are also more restrictive in Derby than in the standard. For instance, the standard allows constructs like GROUP BY (a, b), and GROUP BY a, (b, c), and even GROUP BY (), which are not accepted by Derby.)
          Hide
          Bryan Pendleton added a comment -

          Attached patch "withDagsCastTest.diff' includes the test suggested by Dag on 1-sep-2009. I don't understand why the CAST operator has this strange effect on the code, so for the time being this test fails while I research the behavior.

          Show
          Bryan Pendleton added a comment - Attached patch "withDagsCastTest.diff' includes the test suggested by Dag on 1-sep-2009. I don't understand why the CAST operator has this strange effect on the code, so for the time being this test fails while I research the behavior.
          Hide
          Bryan Pendleton added a comment -

          On 1-sep-2009, Dag made two observations (paraphrased, and shortened):

          1) When a CAST node is used in a certain query, the wrong results are returned
          2) When a sub-query is used, the nullability handling of rolled-up columns is confused

          I believe that I have figured out the first problem: in my patch, there are certain
          situations where, during the processing of a row of data, we complete the
          processing of multiple rolled-up groups. For example, if you are rolling up
          sales data by DIVISION, QUARTER, and MONTH, and you get a row for a new DIVISION,
          the accumulated data for the previous MONTH, QUARTER, and DIVISION are now
          complete. Internally, I am holding these completed-and-not-yet-returned rows in
          the "finishedResults" array, and returning them one-row-at-a-time when requested.

          However, I was not correctly calling setCurrentRow() when returning a saved row from
          the finishedResults array, which meant that operations at the next level, such as
          projection processing, was accessing the wrong data when it referred to the current row.

          I've modified the patch to call setCurrentRow appropriately, and the wrong results are
          no longer returned.

          Dag's other question remains open to me, and I'm not sure what's going on. It seems
          to me that the ROLLUP feature can cause NULL values to be returned in non-NULL-able
          columns, which is a troubling behavior. I believe this behavior is mentioned in Jim Gray's
          original DataCube research paper, where he proposed a different handling of the placeholder
          values other than NULL.

          I will need to spend some time with the SQL Standard to understand how the standard
          deals with this ability of the ROLLUP feature to produce NULL values where they might
          otherwise not be expected.

          I'll try to post an updated patch with the setCurrentRow fix soon.

          Meanwhile, Knut, I haven't forgotten about your feedback regarding the fact that this
          patch implements only a subset of the ROLLUP feature as described in the standard.
          I was definitely aware that I was implementing only part of the feature, but I agree with
          you that we need to have a good awareness of what parts of the overall standard we did
          and did not implement, and make sure that is clear in both the code and the documentation.

          Thanks again to everybody for their continued feedback and support.

          Show
          Bryan Pendleton added a comment - On 1-sep-2009, Dag made two observations (paraphrased, and shortened): 1) When a CAST node is used in a certain query, the wrong results are returned 2) When a sub-query is used, the nullability handling of rolled-up columns is confused I believe that I have figured out the first problem: in my patch, there are certain situations where, during the processing of a row of data, we complete the processing of multiple rolled-up groups. For example, if you are rolling up sales data by DIVISION, QUARTER, and MONTH, and you get a row for a new DIVISION, the accumulated data for the previous MONTH, QUARTER, and DIVISION are now complete. Internally, I am holding these completed-and-not-yet-returned rows in the "finishedResults" array, and returning them one-row-at-a-time when requested. However, I was not correctly calling setCurrentRow() when returning a saved row from the finishedResults array, which meant that operations at the next level, such as projection processing, was accessing the wrong data when it referred to the current row. I've modified the patch to call setCurrentRow appropriately, and the wrong results are no longer returned. Dag's other question remains open to me, and I'm not sure what's going on. It seems to me that the ROLLUP feature can cause NULL values to be returned in non-NULL-able columns, which is a troubling behavior. I believe this behavior is mentioned in Jim Gray's original DataCube research paper, where he proposed a different handling of the placeholder values other than NULL. I will need to spend some time with the SQL Standard to understand how the standard deals with this ability of the ROLLUP feature to produce NULL values where they might otherwise not be expected. I'll try to post an updated patch with the setCurrentRow fix soon. Meanwhile, Knut, I haven't forgotten about your feedback regarding the fact that this patch implements only a subset of the ROLLUP feature as described in the standard. I was definitely aware that I was implementing only part of the feature, but I agree with you that we need to have a good awareness of what parts of the overall standard we did and did not implement, and make sure that is clear in both the code and the documentation. Thanks again to everybody for their continued feedback and support.
          Hide
          Bryan Pendleton added a comment -

          Attached patch calls setCurrentRow when returning a rolled-up grouped
          result from the finishedResults lookaside buffer.

          This patch is growing a bit long in the tooth. I'm considering the following plan:

          • moving the current patch toward commit
          • filing followup issues for the remaining problems, namely:
          • documentation is needed
          • need to investigate the handling of the other varieties of ROLLUP which
            are described by the SQL standard but not covered by this patch
          • need to address the nullability-in-subqueries problem uncovered by Dag

          Does this seem like a reasonable approach?

          Show
          Bryan Pendleton added a comment - Attached patch calls setCurrentRow when returning a rolled-up grouped result from the finishedResults lookaside buffer. This patch is growing a bit long in the tooth. I'm considering the following plan: moving the current patch toward commit filing followup issues for the remaining problems, namely: documentation is needed need to investigate the handling of the other varieties of ROLLUP which are described by the SQL standard but not covered by this patch need to address the nullability-in-subqueries problem uncovered by Dag Does this seem like a reasonable approach?
          Hide
          Knut Anders Hatlen added a comment -

          +1 to the suggested approach. Getting the main functionality in and mostly working as part of this issue and addressing the other issues in separate JIRAs sounds like a good plan.

          Show
          Knut Anders Hatlen added a comment - +1 to the suggested approach. Getting the main functionality in and mostly working as part of this issue and addressing the other issues in separate JIRAs sounds like a good plan.
          Hide
          Dag H. Wanvik added a comment -

          Sure, +1.

          Show
          Dag H. Wanvik added a comment - Sure, +1.
          Hide
          Bryan Pendleton added a comment -

          I feel like I've worked on this code about as long as I can by myself; it's time to get
          the wider Derby developer community to help shake out the next level of problems.

          Many thanks to Knut, Dag, Manish, and all the other reviewers for the helpful
          feedback and suggestions.

          I've committed the current working version of the code to the trunk as revision 824966.

          I intend to work on the documentation patch next (DERBY-4394).

          If no significant issues arise immediately with the code just committed, I'll mark this
          issue as resolved in the next few days, and we can deal with subsequent problems
          as separate Jira issues.

          Show
          Bryan Pendleton added a comment - I feel like I've worked on this code about as long as I can by myself; it's time to get the wider Derby developer community to help shake out the next level of problems. Many thanks to Knut, Dag, Manish, and all the other reviewers for the helpful feedback and suggestions. I've committed the current working version of the code to the trunk as revision 824966. I intend to work on the documentation patch next ( DERBY-4394 ). If no significant issues arise immediately with the code just committed, I'll mark this issue as resolved in the next few days, and we can deal with subsequent problems as separate Jira issues.
          Hide
          Knut Anders Hatlen added a comment -

          Thanks for all the work on this issue, Bryan! It'll be great to get more people kicking the tires.

          If you mark this issue as resolved, it's probably a good idea to convert the remaining sub-tasks to top-level JIRA issues so that they don't disappear from our radar. There's a "Convert to issue" link in the "Operations" menu.

          Show
          Knut Anders Hatlen added a comment - Thanks for all the work on this issue, Bryan! It'll be great to get more people kicking the tires. If you mark this issue as resolved, it's probably a good idea to convert the remaining sub-tasks to top-level JIRA issues so that they don't disappear from our radar. There's a "Convert to issue" link in the "Operations" menu.
          Hide
          Bryan Pendleton added a comment -

          Checked the 'release note needed' flag, as we will need a release note for this feature when it is released.

          Show
          Bryan Pendleton added a comment - Checked the 'release note needed' flag, as we will need a release note for this feature when it is released.
          Hide
          Myrna van Lunteren added a comment -

          I stumbled upon this issue and I wonder - was it the intend to resolve this issue & - as Knut suggested - and convert the remaining subtasks to top level issues?
          And I don't see a release note, did this slip through cracks?

          Show
          Myrna van Lunteren added a comment - I stumbled upon this issue and I wonder - was it the intend to resolve this issue & - as Knut suggested - and convert the remaining subtasks to top level issues? And I don't see a release note, did this slip through cracks?
          Hide
          Bryan Pendleton added a comment -

          Hi Myrna, thanks for following up.

          Indeed, it appears that I never wrote a release note. I can't remember any reason not to, I think I just forgot

          I've converted the two remaining open sub-tasks to top-level issues, and I'll mark this issue resolved.

          Do you see value in writing a release note at this point?

          Show
          Bryan Pendleton added a comment - Hi Myrna, thanks for following up. Indeed, it appears that I never wrote a release note. I can't remember any reason not to, I think I just forgot I've converted the two remaining open sub-tasks to top-level issues, and I'll mark this issue resolved. Do you see value in writing a release note at this point?
          Hide
          Bryan Pendleton added a comment -

          Marking as fixed in release 10.8.1.2. I think that some earlier versions may also have contained this feature, so additional fix versions might be applicable.

          Additional work remains for the ROLLUP feature, but that work is described in separate JIRA issues; the initial work described by this issue is complete.

          Show
          Bryan Pendleton added a comment - Marking as fixed in release 10.8.1.2. I think that some earlier versions may also have contained this feature, so additional fix versions might be applicable. Additional work remains for the ROLLUP feature, but that work is described in separate JIRA issues; the initial work described by this issue is complete.
          Hide
          Myrna van Lunteren added a comment -

          This went in with revision 824966, which was before the 10.6 branch was created (revision 938046), so I'm marking it fixed in 10.6.1.0. I don't think it has to be marked as fixed in a subsequent version, because it was automatically in all the later versions (i.e. there was no backport needed).

          Show
          Myrna van Lunteren added a comment - This went in with revision 824966, which was before the 10.6 branch was created (revision 938046), so I'm marking it fixed in 10.6.1.0. I don't think it has to be marked as fixed in a subsequent version, because it was automatically in all the later versions (i.e. there was no backport needed).
          Hide
          Myrna van Lunteren added a comment -

          I thought usually we mark 'release note needed' when there's some kind of incompatibility with previous releases, and I was wondering what the incompatibility was. Maybe the release note flag was set to explain this was only an initial step in support for ROLLUP style GROUP BY? Or was there incompatibility because of different performance of certain queries?

          But as I've now marked this as fixed in 10.6.1.0, (which I think is the right value), adding the release note won't really be of any use in generating any release notes, and I don't think it belongs in the 10.8 release notes.

          Show
          Myrna van Lunteren added a comment - I thought usually we mark 'release note needed' when there's some kind of incompatibility with previous releases, and I was wondering what the incompatibility was. Maybe the release note flag was set to explain this was only an initial step in support for ROLLUP style GROUP BY? Or was there incompatibility because of different performance of certain queries? But as I've now marked this as fixed in 10.6.1.0, (which I think is the right value), adding the release note won't really be of any use in generating any release notes, and I don't think it belongs in the 10.8 release notes.
          Hide
          Bryan Pendleton added a comment -

          I think I was thinking of the Release Notes as a mechanism for drawing attention to
          new aspects of a release, both features as well as incompatibilities. At least, I suppose
          I must have been thinking that; I really can't remember

          At any rate, I unchecked the Release Note field, as I can't recall that this introduced
          any incompatibilities with existing applications.

          Show
          Bryan Pendleton added a comment - I think I was thinking of the Release Notes as a mechanism for drawing attention to new aspects of a release, both features as well as incompatibilities. At least, I suppose I must have been thinking that; I really can't remember At any rate, I unchecked the Release Note field, as I can't recall that this introduced any incompatibilities with existing applications.
          Hide
          Knut Anders Hatlen added a comment -

          [bulk update] Close all resolved issues that haven't been updated for more than one year.

          Show
          Knut Anders Hatlen added a comment - [bulk update] Close all resolved issues that haven't been updated for more than one year.

            People

            • Assignee:
              Bryan Pendleton
              Reporter:
              Bryan Pendleton
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development