[
https://issues.apache.org/jira/browse/DERBY-3926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12699721#action_12699721
]
Bryan Pendleton commented on DERBY-3926:
----------------------------------------
Thanks Army for taking the time to look at this, and for pointing us to a good
theory!
I like Army's suggestion. I wish I had a clearer grasp on the concept of a
'partial join order'. I think that
this is an intermediate stage during optimization, where the optimizer has so
far chosen an ordering
for some, but not yet all, of the tables. It looks like the code is trying to
handle the problem of how
to make a sort avoidance check at this intermediate point in optimization.
I think that all *chosen* query plans eventually reach a *complete* join order,
but a query plan which
is *discarded* due to being too expensive may never get beyond a *partial* join
order. Is that true?
It seems to me that there may be two topics here:
1) it would be valid to make such a check for the purposes of doing some
preliminary costing of
the join order up to this point, but for such an algorithm, the code would have
to then re-visit the
sort avoidance decision later in the optimization, once the partial join order
had become a full join order.
That is, I wonder if the overall flow is something like:
- optimizer investigates a partial join order, decides to cost it, determines
that (so far) a sort is not required.
- optimizer later completes this join order, decides that it is acceptable,
but does NOT re-analyze
whether a sort is now required for the complete join order
- optimizer then chooses the correct full join order, but incorrectly avoids
the sort due to the decision
it made when considering the partial join order.
2) The comment ("ORDER BY S.A, T.B, S.C") raises the interesting question of
the situation in
which each column, considered individually, is ordered properly, but because
the ORDER BY
clause interleaves columns from different tables, a sort is still required.
That is, if S had an index
on (A, C), and T had an index on B, we might look at ORDER BY S.A, T.B, S.C and
think that no
sorting of the results was required, because the join from S -> T would emit
the rows in the
correct order, but that is wrong; the interleaving of the columns means that
the sort must still be performed.
And, presumably, there is the interesting situation where we need to cost out a
query at a point
where we have determined a partial join order that contains a position for S,
but not T, or vice versa.
It would be interesting to know more about the Wisconsin test cases, about the
queries involved, and
about the before- and after- query plan differences, with respect to sorting.
Are *all* the changes due
to situations where we formerly avoided a sort, but now we choose one? That's
interesting, I think; we
want to be careful to avoid introducing un-necessary sorts because that could
be a substantial
performance regression (of course, if the old query was returning the rows in
the wrong order, but
the test didn't check, and the new query is now being performed correctly,
that's important to know, too!)
It would also be interesting to see if we can construct an example along the
lines of the
ORDER BY S.A, T.B, S.C case, such that various other permutations (ORDER BY
S.A, S.C, T.B or
ORDER BY T.B, S.A, S.C) did not require sorting, but ORDER BY S.A, T.B, S.C
did, and see how
the query plans emitted for these various cases behaved.
> Incorrect ORDER BY caused by index
> ----------------------------------
>
> Key: DERBY-3926
> URL: https://issues.apache.org/jira/browse/DERBY-3926
> Project: Derby
> Issue Type: Bug
> Components: SQL
> Affects Versions: 10.1.3.3, 10.2.3.0, 10.3.3.1, 10.4.2.0
> Reporter: Tars Joris
> Attachments: derby-reproduce.zip
>
>
> I think I found a bug in Derby that is triggered by an index on a large
> column: VARCHAR(1024). I know it is generally not a good idea to have an
> index on such a large column.
> I have a table (table2) with a column "value", my query orders on this column
> but the result is not sorted. It is sorted if I remove the index on that
> column.
> The output of the attached script is as follows (results should be ordered on
> the middle column):
> ID |VALUE |VALUE
> ----------------------------------------------
> 2147483653 |000002 |21857
> 2147483654 |000003 |21857
> 4294967297 |000001 |21857
> While I would expect:
> ID |VALUE |VALUE
> ----------------------------------------------
> 4294967297 |000001 |21857
> 2147483653 |000002 |21857
> 2147483654 |000003 |21857
> This is the definition:
> CREATE TABLE table1 (id BIGINT NOT NULL, PRIMARY KEY(id));
> CREATE INDEX key1 ON table1(id);
> CREATE TABLE table2 (id BIGINT NOT NULL, name VARCHAR(40) NOT NULL, value
> VARCHAR(1024), PRIMARY KEY(id, name));
> CREATE UNIQUE INDEX key2 ON table2(id, name);
> CREATE INDEX key3 ON table2(value);
> This is the query:
> SELECT table1.id, m0.value, m1.value
> FROM table1, table2 m0, table2 m1
> WHERE table1.id=m0.id
> AND m0.name='PageSequenceId'
> AND table1.id=m1.id
> AND m1.name='PostComponentId'
> AND m1.value='21857'
> ORDER BY m0.value;
> The bug can be reproduced by just executing the attached script with the
> ij-tool.
> Note that the result of the query becomes correct when enough data is
> changed. This prevented me from creating a smaller example.
> See the attached file "derby-reproduce.zip" for sysinfo, derby.log and
> script.sql.
> Michael Segel pointed out:
> "It looks like its hitting the index ordering on id,name from table 2 and is
> ignoring the order by clause."
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
