You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-dev@db.apache.org by Jack Klebanoff <kl...@Mutagen.Net> on 2004/12/10 01:59:13 UTC
[PATCH] Intersect and Except
Attached is a patch that implements the SQL INTERSECT and EXCEPT
operators. The INTERSECT operator constructs the intersection of two
tables. The EXCEPT operator finds all rows in one table but not in the
other. The syntax is (roughly):
<query expression> INTERSECT [ALL] <query expression>
<query expression> EXCEPT [ALL] <query expression>
By default these operators remove duplicates, which can occur if there
are duplicates in the inputs. If ALL is specified then duplicates are
not returned. If t1 has m copies of row R and t2 has n copies then t1
INTERSECT ALL t2 returns min(m,n) copies of R, and t1 EXCEPT ALL t2
returns max( 0, m-n) copies of R.
The EXCEPT operator has the same precedence as UNION. INTERSECT has
higher precedence.
This follows the SQL-92 spec. (At least it follows my understanding of
the spec. Spec lawyers are invited to comment).
The implementation uses sorting. The two input tables are sorted and
then scanned together. The appropriate rows from the left input are output.
The compiler binds INTERSECT and EXCEPT like UNION. Therefore a new
class, org.apache.derby.impl.sql.compile.SetOperatorNode, was carved out
of UnionNode. It mainly contains bind methods. Classes UnionNode and
IntersectOrExceptNode extend SetOperatorNode. Classes IntersectNode and
ExceptNode extend IntersectOrExceptNode. IntersectOrExceptNode does most
of the optimization and code generation work. It puts OrderBy nodes in
front of its inputs.
The generated code creates a SetOpProjectRestrictResultSet that reads
its sorted inputs to produce the required output table.
Jack Klebanoff
Re: [PATCH] Intersect and Except
Posted by Daniel John Debrunner <dj...@debrunners.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Jack Klebanoff wrote:
> I have attached an update to my previous INTERSECT/EXCEPT patch. It
> addresses a number of concerns brought up in this thread.
Minor (repeated comment) in SetOpResultSet.java
+ private int compare( DataValueDescriptor[] leftCols,
DataValueDescriptor[] rightCols)
+ throws StandardException
+ {
+ for( int i = 0; ; i++)
+ {
+ if( i >= intermediateOrderByColumns.length)
+ return 0;
This style of loop is still really awkward to read and understand.
Typically it's written
for (int i = 0 ; i < intermediateOrderByColumns.length; i++)
{
...
}
return 0
Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFBw6YmIv0S4qsbfuQRAkjLAJ4rAe9ktat6HQgpAdd/OWxjTQmx5QCg4E/n
dDh6TshqnVhvPB0HqqxR8AY=
=x4/0
-----END PGP SIGNATURE-----
Re: [VOTE] [PATCH] Intersect and Except
Posted by Jack Klebanoff <kl...@Mutagen.Net>.
Satheesh Bandaram wrote:
> I am submitting this patch for a VOTE. It has been pending for about a
> week. My vote is "+1", with the following comments. Since this is a
> new feature, I think, three +1 votes are requied. Here is the status
> of this patch. I am basically waiting for the final +1 vote....
>
> 1. It passed build and all tests.
> 2. Mike and myself have voted +1.
> 3. Dan provided a suggestion, with some syntax improvement. Any
> response from the contributor? I am assuming Dan's vote is a +1. If
> not, please speak up.. :-)
>
> Here are my comments:
>
> 1. IntersectOrExceptNode still refers to SetOpProjectRestrict.
> Should this be SetOpResultSet?
> 2. Doesn't tableConstructor logic apply only to UnionNode? If so,
> should the fields like tableConstructor, topTableConstructor and
> methods like setTableConstructorTypes() be moved to UnionNode? Current
> code in SetOperatorNode refers to subclass UnionNode a lot, which
> could be improved?
>
Satheesh, I think that you are right on both points.
IntersectOrExceptNode should refer to SetOpResultSet instead of
SetOpProjectRestrict.
From reading the code I gather that the tableConstructor field is used
to mark a Union node that is generated from a VALUES expression that has
more than one row. So, while the expression (t1 INTERSECT t2) sonstructs
a table, it will never be a "tableConstructor" in the narrower sense
used by our code.
I will change the code accordingly and submit a new patch. It should be
ready today or first thing tomorrow morning.
Jack
Re: [VOTE] [PATCH] Intersect and Except
Posted by Samuel Andrew McIntyre <fu...@nonintuitive.com>.
On Jan 6, 2005, at 5:08 PM, Satheesh Bandaram wrote:
> Adding
> java\engine\org\apache\derby\impl\sql\compile\IntersectOrExceptNode.jav
> a
I noticed that the intersect test was failing with the jars because the
new Intersect node was not being added to the derby.jar class list
during the jar build. I have added the new node to
tools/jar/DBMSnodes.properties and the test now passes.
andrew
Re: [VOTE] [PATCH] Intersect and Except
Posted by Jack Klebanoff <kl...@Mutagen.Net>.
Satheesh Bandaram wrote:
> I am submitting this patch for a VOTE. It has been pending for about a
> week. My vote is "+1", with the following comments. Since this is a
> new feature, I think, three +1 votes are requied. Here is the status
> of this patch. I am basically waiting for the final +1 vote....
>
> 1. It passed build and all tests.
> 2. Mike and myself have voted +1.
> 3. Dan provided a suggestion, with some syntax improvement. Any
> response from the contributor? I am assuming Dan's vote is a +1. If
> not, please speak up.. :-)
>
> Here are my comments:
>
> 1. IntersectOrExceptNode still refers to SetOpProjectRestrict.
> Should this be SetOpResultSet?
> 2. Doesn't tableConstructor logic apply only to UnionNode? If so,
> should the fields like tableConstructor, topTableConstructor and
> methods like setTableConstructorTypes() be moved to UnionNode? Current
> code in SetOperatorNode refers to subclass UnionNode a lot, which
> could be improved?
>
>
I have revised my patch to address Satheesh and Dan's comments. The
revision changes IntersectOrExceptNode.java, sqlgrammar.jj,
SetOpResultSet.java, TableOperatorNode.java, UnionNode.java, and
SetOperatorNode.java since my last submission. It passed the derbyall
test suite.
Jack
Re: [PATCH] Intersect and Except
Posted by Mike Matrigali <mi...@sbcglobal.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
+1 for applying the patch, assuming system builds and all tests pass.
/mikem
Satheesh Bandaram wrote:
| I am reviewing the change and running tests. Will commit if everything
| is fine...
|
| Since this is a new feature, I think it needs at least two additional +1
| votes. I do hope both Dan and Mike who had some comments on this patch
| earlier can review and vote, in addition to others...
|
| Satheesh
|
| Jack Klebanoff wrote:
|
| > I have attached an update to my previous INTERSECT/EXCEPT patch. It
| addresses a number of concerns brought up in this thread.
| ... rest removed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFBx279EpeslyHqPs0RAmSyAKCIEy7wcD7JnB55oVcWqv8l1S7tOACfTMcx
WGlWItTmqHITceYRjezs/EY=
=2tWj
-----END PGP SIGNATURE-----
Re: [PATCH] Intersect and Except
Posted by Jack Klebanoff <kl...@Mutagen.Net>.
I have attached an update to my previous INTERSECT/EXCEPT patch. It
addresses a number of concerns brought up in this thread.
1. It includes the fix for order by syntax checking posted by Satheesh.
2. It fixes the execution of an order by clause in the statement.
Previously an order by clause was ignored.
3. The intersect/except is still implemented by sorting its two inputs,
but optimizer is given a chance to perform sort avoidance on the inputs.
4. If there is an order by clause on the output of the intersect/except
then that ordering is used for the inputs, avoiding a separate sort on
the intersect/except output.
5. Test cases were added to cover the above code.
6. The copyright notices for the new files were changed to 2004.
7. The SetOpProjectRestrictResultSet class was renamed to
SetOpResultSet, which is more appropriate.
8. The IntersectNode and ExceptNode classes were removed and subsumed in
the IntersectOrExceptNode class.
Some of the concerns about optimization were not entirely addressed.
There is still just the one execution strategy: sort the two inputs and
scan them together. I did not implement other strategies and an
optimizer that picks the best of them. I think that my implementation
strategy performs decently in all cases, and is the best in many cases.
I don't think that it is wise to write a lot of code to optimize an
operation that is probably only used infrequently. (Cloudscape customers
have gotten along without it for all these years).
While this update allows the optimizer to avoid sorting the
intersect/except inputs it does not try to pick an ordering that is more
likely to avoid a sort. For instance, suppose one of the inputs is a
single table select that selects the columns of a unique key. Then you
only have to order that input on the key columns. Depending on the where
clause the optimizer might decide to use the unique key index to
traverse the table in sort order, avoiding a separate sort. The other
input to the intersect/except may be a different story. Those same
columns may not specify a unique key in the other input, in which case
that input must be ordered on more columns.
Unfortunately the Derby compiler architecture does not make it easy for
the IntersectOrExceptNode class to determine a column ordering that is
likely to avoid a sort on its inputs. Its inputs are represented as
ResultSetNodes. It is not easy to determine a ResultSetNode represents a
single table select, and if so whether the selected columns contain a
unique key. One would like to try avoiding a sort on the larger input,
and then try a column ordering that might avoid a sort on the smaller
input if the optimizer cannot avoid sorting the larger input.
Unfortunately this does not work: the architecture requires that the
order by clause be pushed down by the start of optimization.
It is easy to see if the output of the intersect/except must be ordered
and use this ordering to order the inputs, avoiding a separate sort on
the output of the intersect/except. I did this in the attached patch update.
Jack
Jack Klebanoff wrote:
> Attached is a patch that implements the SQL INTERSECT and EXCEPT
> operators. The INTERSECT operator constructs the intersection of two
> tables. The EXCEPT operator finds all rows in one table but not in the
> other. The syntax is (roughly):
>
> <query expression> INTERSECT [ALL] <query expression>
> <query expression> EXCEPT [ALL] <query expression>
>
> By default these operators remove duplicates, which can occur if there
> are duplicates in the inputs. If ALL is specified then duplicates are
> not returned. If t1 has m copies of row R and t2 has n copies then t1
> INTERSECT ALL t2 returns min(m,n) copies of R, and t1 EXCEPT ALL t2
> returns max( 0, m-n) copies of R.
>
> The EXCEPT operator has the same precedence as UNION. INTERSECT has
> higher precedence.
>
> This follows the SQL-92 spec. (At least it follows my understanding of
> the spec. Spec lawyers are invited to comment).
>
> The implementation uses sorting. The two input tables are sorted and
> then scanned together. The appropriate rows from the left input are
> output.
>
> The compiler binds INTERSECT and EXCEPT like UNION. Therefore a new
> class, org.apache.derby.impl.sql.compile.SetOperatorNode, was carved
> out of UnionNode. It mainly contains bind methods. Classes UnionNode
> and IntersectOrExceptNode extend SetOperatorNode. Classes
> IntersectNode and ExceptNode extend IntersectOrExceptNode.
> IntersectOrExceptNode does most of the optimization and code
> generation work. It puts OrderBy nodes in front of its inputs.
>
> The generated code creates a SetOpProjectRestrictResultSet that reads
> its sorted inputs to produce the required output table.
>
> Jack Klebanoff
>
>
Re: [PATCH] Intersect and Except
Posted by Daniel John Debrunner <dj...@debrunners.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Mike Matrigali wrote:
> I have always thought one hole in the derby query processing strategy
> is that it does not support any sort of sort/merge query node. Could
> your new node be used for this?
>
> Does your code take advantage of the case when the rows are already
> sorted? I believe the following case is very common:
I was going to ask the same question, and have two additional thoughts:
- - It seems that if the sort is on top of a table access then if sort
avoidance doesn't happen automatically then something is wrong with
Derby optimizer. At least if the query nodes are all plug and play then
it seems it should come for free. I.e. the sort on top of a table access
should optimize independent of what is above it in the tree.
- - It also seems that intersect could use any unique index that exists on
a sub-set of the intersect columns, thus some optimize step for
intersect could cost various column orders, or look for unique indexes.
Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFBufn7Iv0S4qsbfuQRAlSfAKCDbWjOiEadHAz0whUUZ/oxvcuQ7gCfXEeu
0MAcaqRGbwomvrSS+w6bjcg=
=TCTt
-----END PGP SIGNATURE-----
Re: [PATCH] Intersect and Except
Posted by Mike Matrigali <mi...@sbcglobal.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
I have always thought one hole in the derby query processing strategy
is that it does not support any sort of sort/merge query node. Could
your new node be used for this?
Does your code take advantage of the case when the rows are already
sorted? I believe the following case is very common:
TABLE A with PRIMARY KEY A_KEY
TABLE B with PRIMARY KEY B_KEY
Then a join, intersect or except is done on the 2 tables on the 2
primary keys. In this case it is very easy for the store to return
an ordered stream of rows from each of the tables. In fact if the
either side is known to be unique I believe that there would be no
need to ever have more than one row in memory at a time from either
side.
I believe the duplicate key case is harder, one would either need
to keep all the duplicate key cases in memory, or the store could
provide a "rewind" mechanism to quickly reset the stream of rows back
to the beginning of the duplicate chain.
I don't know very much about intersect or except but for a simple
join on 2 unique keys which already have indexes on them it seems
obvious to me that a sort merge has to perform better than a hash
join and would the difference increases as the size of result set
on either size increases.
Jack Klebanoff wrote:
| RPost wrote:
|
|> Your text says 'If ALL is specified then duplicates are not returned'.
|> You
|> also say that by default duplicates are removed. So is the default
|> ALL? Or
|> did you mean that if ALL is specified then duplicates are not removed?
|>
|> If you don't need to remove duplicates then doesn't that mean that you
|> only
|> need to sort one of the data sets? If so, this would improve
|> performance. If
|> statistics are available then the smaller dataset should be the one
|> that is
|> sorted.
|>
| I am sorry, my typo. My message should have read "If ALL is specified
| then duplicates *are* returned". The default is to remove duplicates,
| ALL is not the default.
|
| Sorting both inputs makes the final selection easier and faster even
| when duplicates are not removed. As RPost suggests, we could implement
| INTERSECT ALL and EXCEPT ALL by just sorting one of the inputs, avoiding
| part of the sort cost. Then we would scan through each row in the
| unsorted input and use a binary search to see if it is in the sorted
| input. In order to output the correct number of duplicates we must mark
| the row as removed from the sorted input. I don't think that the
| org.apache.derby.iapi.sql.ResultSet interface or the SortedResultSet
| class currently implement row deletion or marking.
|
| If the number of rows in the two inputs are m and n the cost of sorting
| both is O(n*log(n) + m*log(m)). The final select step has a cost of
| O(n+m). If we only sort one input, say the second one, then the sort
| cost is O(n*log(n)) and the cost of the final select step is
| O(m*log(n)), for a total cost O((m+n)*log(n)). If n < m this is
| asymptotically better. The binary searches will have poor locality of
| reference and deleting rows from a temporary table that has spilled to
| disk may be expensive, so in practice sorting just one input may only be
| better when the two inputs have significantly different sizes. Perhaps
| in the future we can implement both methods and pick the better one at
| optimize time.
|
| I wanted to make an initial implementation that is simple, handles both
| INTERSECT and EXCEPT, and that fits into the current Derby
| implementation fairly easily. If the performance of INTERSECT or EXCEPT
| proves to be important then we should revisit this.
|
| In fact there are a number of related implementation alternatives that
| may be optimal under different conditions.
| 1. Just sort the smaller input and use a binary search to see if each
| row in the unsorted input is also in the sorted input. INTERSECT is
| commutative, so it does not matter which of its inputs is sorted. EXCEPT
| is not commutative. If we sort its left input and scan through the
| unsorted right input we have to remove/mark the intersection rows in the
| left (sorted) input and output the unremoved/marked rows at the end.
| 2. We can also handle duplicate elimination when just sorting one input
| by removing duplicates when doing the sort, but not removing/marking
| rows from the sorted input as they are found in the other input.
| 3. We can use a hash table instead of sorting. Unfortunately Derby does
| not yet have a hash table implementation that spills to disk.
|
| Jack
| Jack Klebanoff
|
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFBue58EpeslyHqPs0RAoQZAKDHt4+qtnBU90rbKM+BgFcKTm+s2QCfSxfz
b/ooqn8eCrOiM0cKcivk1bU=
=+WdC
-----END PGP SIGNATURE-----
Re: Features - Quick or correct??
Posted by Daniel John Debrunner <dj...@debrunners.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Mike Matrigali wrote:
> In this case I think it is good that a quick implementation of intersect
> and except has been submitted. Especially with new standard features it
> gives the community something to test that the feature is correct. I
> believe these features will allow more applications to ported over to
> derby and thus give us more early feedback on what is important to do
> next. The earlier it
> is submitted the more tests that can be submitted.
My comments in this thread are general comments and not related to
Jack's changes, that's why I changed the subject.
> If it runs too slow then performance can be addressed.
Performance can only be addressed later if the foundation is good, if
the foundation is bad then a re-write is needed which wastes time.
I just don't think the standard approach to any feature should be code
now and worry about performance later (when is "later" and who is going
to do it?). Thinking a little about the design and bouncing it off the
community early can only help a feature, and the quality of Derby.
http://www.joelonsoftware.com/articles/NothingIsSimple.html
And yes, I think an incremental approach to development is great, given
a good design. But since I can't read minds, I would need a contributor
to indicate that the patch is part of an incremental approach or they
believe the feature is complete.
Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFBuh58Iv0S4qsbfuQRAkQ+AJ9uHqZsIM5pb3BAZmarVy6+EvcSlgCgkWpe
hNn7k1ScMgLph51J+VgXNGY=
=XmqE
-----END PGP SIGNATURE-----
Re: Features - Quick or correct??
Posted by Mike Matrigali <mi...@sbcglobal.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
In this case I think it is good that a quick implementation of intersect
and except has been submitted. Especially with new standard features it
gives the community something to test that the feature is correct. I
believe these features will allow more applications to ported over to
derby and thus give us more early feedback on what is important to do
next. The earlier it
is submitted the more tests that can be submitted.
If it runs too slow then performance can be addressed. Given that a
sort merge in memory is being used I don't expect it to be too slow. Of
course once checked in the community can compare it's performance with
other systems. Encouraging iterative development also opens up the code
to the community earlier for testing and review. I think this is better
than possibly sitting on a big prject without multiple checkpoint steps.
~ Of course each checkin should pass all tests, submit new tests for the
new feature and not present regressions to the rest of the code. Again
iterative development is more acceptable now that the community has the
option of picking up the stable branch or the in flux development line.
Daniel John Debrunner wrote:
| RPost wrote:
|
|
|>>>Jack Klebanoff wrote:
|>>>
|>>>I wanted to make an initial implementation that is simple, handles both
|>>>INTERSECT and EXCEPT, and that fits into the current Derby
|>>>implementation fairly easily. If the performance of INTERSECT or EXCEPT
|>>>proves to be important then we should revisit this.
|>>>
|>>
|>>
|>>I certainly agree with this approach. The first priority is to get
|
| something
|
|>>that works
|>>as easily and simply as possible.
|
|
| I'm not completely convinced this is the correct approach. While it is
| good to have the functionality (and maybe more importantly the tests)
| quickly, first impressions count. So if we (the Derby community) produce
| correct but slow features, it will be hard to shake that image.
|
| Contributors & committers should be encouraged to discuss design ideas
| with the list early rather than once they have coded them up.
|
| It's also hard for me to tell with various contributions if the
| contributor thinks the feature is complete, or it's an incremental step
| to the fully completed feature. I think the incremental step is a great
| way to go, but only if it's identified as that, and the future steps are
| listed so the contributor or someone else can address them. Then it's
| also easy to discuss which of those steps are essential before a feature
| is considered ready for production release.
|
| Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFBuhLQEpeslyHqPs0RAnpIAKDe5JBZ49/IMfxrV69+DML3ZIFtQACcDGnP
vPFswuy+3X8OXT5Jxuj25A8=
=7x15
-----END PGP SIGNATURE-----
Re: Features - Quick or correct??
Posted by Dibyendu Majumdar <di...@mazumdar.demon.co.uk>.
Dan wrote:
> Contributors & committers should be encouraged to discuss design ideas
> with the list early rather than once they have coded them up.
Hi, Just to say that I could not agree more. Perhaps a standard process
should be set up where if someone is proposing a product enhancement or
major code revision, then they need to write up what they are proposing, how
it will work, etc. and get agreement from the forum before proceeding to
develop the solution.
I had to say this because I face similar issues in the organisation I work
for.
Regards
Dibyendu
Re: Features - Quick or correct??
Posted by "Geir Magnusson Jr." <ge...@gluecode.com>.
On Dec 10, 2004, at 2:22 PM, Daniel John Debrunner wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> RPost wrote:
>
>>> Jack Klebanoff wrote:
>>>
>>> I wanted to make an initial implementation that is simple, handles
>>> both
>>> INTERSECT and EXCEPT, and that fits into the current Derby
>>> implementation fairly easily. If the performance of INTERSECT or
>>> EXCEPT
>>> proves to be important then we should revisit this.
>>>
>>
>>
>> I certainly agree with this approach. The first priority is to get
> something
>> that works
>> as easily and simply as possible.
>
> I'm not completely convinced this is the correct approach. While it is
> good to have the functionality (and maybe more importantly the tests)
> quickly, first impressions count. So if we (the Derby community)
> produce
> correct but slow features, it will be hard to shake that image.
Well, no - not for the main development trunk in svn. I think that
sucky releases are a problem, but people should expect very little w/
the main development trunk in terms of features. Yes, it should
compile, yes, it should run, but production-grade performance? I don'
think so.
>
> Contributors & committers should be encouraged to discuss design ideas
> with the list early rather than once they have coded them up.
Yes, but sometimes code talks very well, and it also gives people who
don't want to slog through email trails a quick view of the idea, and a
chance to improve.
A good thing about partial or inefficient implementations in main trunk
is that it can act as flypaper for community members - people will come
and pitch in to (forgive the cliché...) "scratch an itch".
I may be uninterested in following the dev list in general, but if
there is some feature I need, and it's part way done, it's much easier
for me to 'hook in' and get going. Sometimes a basic framework for
something lets a developer get started a lot easier than a green field.
>
> It's also hard for me to tell with various contributions if the
> contributor thinks the feature is complete, or it's an incremental step
> to the fully completed feature.
Ask him or her :)
> I think the incremental step is a great
> way to go, but only if it's identified as that, and the future steps
> are
> listed so the contributor or someone else can address them. Then it's
> also easy to discuss which of those steps are essential before a
> feature
> is considered ready for production release.
Fair enough - yes, it's key that you track stuff that way....
geir
>
> Dan.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.5 (MingW32)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFBufduIv0S4qsbfuQRArnpAKC/+mF0mqcKAlVfbyol+DpgihMBMwCfUwkZ
> bkHwm6zG0V06CNLGw6UfVdM=
> =Ctr9
> -----END PGP SIGNATURE-----
>
--
Geir Magnusson Jr +1-203-665-6437
geir@gluecode.com
Features - Quick or correct??
Posted by Daniel John Debrunner <dj...@debrunners.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
RPost wrote:
>>Jack Klebanoff wrote:
>>
>>I wanted to make an initial implementation that is simple, handles both
>>INTERSECT and EXCEPT, and that fits into the current Derby
>>implementation fairly easily. If the performance of INTERSECT or EXCEPT
>>proves to be important then we should revisit this.
>>
>
>
> I certainly agree with this approach. The first priority is to get
something
> that works
> as easily and simply as possible.
I'm not completely convinced this is the correct approach. While it is
good to have the functionality (and maybe more importantly the tests)
quickly, first impressions count. So if we (the Derby community) produce
correct but slow features, it will be hard to shake that image.
Contributors & committers should be encouraged to discuss design ideas
with the list early rather than once they have coded them up.
It's also hard for me to tell with various contributions if the
contributor thinks the feature is complete, or it's an incremental step
to the fully completed feature. I think the incremental step is a great
way to go, but only if it's identified as that, and the future steps are
listed so the contributor or someone else can address them. Then it's
also easy to discuss which of those steps are essential before a feature
is considered ready for production release.
Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFBufduIv0S4qsbfuQRArnpAKC/+mF0mqcKAlVfbyol+DpgihMBMwCfUwkZ
bkHwm6zG0V06CNLGw6UfVdM=
=Ctr9
-----END PGP SIGNATURE-----
Re: [PATCH] Intersect and Except
Posted by RPost <rp...@pacbell.net>.
> Jack Klebanoff wrote:
>
> I wanted to make an initial implementation that is simple, handles both
> INTERSECT and EXCEPT, and that fits into the current Derby
> implementation fairly easily. If the performance of INTERSECT or EXCEPT
> proves to be important then we should revisit this.
>
I certainly agree with this approach. The first priority is to get something
that works
as easily and simply as possible. I am still struggling to get up to speed
with Derby's
internals so am still not as familiar as I need to be with how things work
now and
why they were implemented that way.
Repeating the offer I made in Derby-13 (which received no replies as yet):
I would be happy to work one on one (or in a group) with any of the
developers to begin to document the existing architecture and the design
decisions that went into it. This could be by telephone, email or in person
(I am in the San Francisco Bay area and would be happy to meet with folks on
this).
The suggestions Jack has made in this thread and the alternatives he is
considering
are exactly the type of information that I would like to capture without
getting in the
way of getting the work done.
As I have previously suggested to Dan, we need to pick the gold mine of
these folks minds before
the motherlode vein of information is tapped out. The process isn't all that
painful
and usually doesn't cause any permanent damage.
Re: [PATCH] Intersect and Except
Posted by Jack Klebanoff <kl...@Mutagen.Net>.
RPost wrote:
>Your text says 'If ALL is specified then duplicates are not returned'. You
>also say that by default duplicates are removed. So is the default ALL? Or
>did you mean that if ALL is specified then duplicates are not removed?
>
>If you don't need to remove duplicates then doesn't that mean that you only
>need to sort one of the data sets? If so, this would improve performance. If
>statistics are available then the smaller dataset should be the one that is
>sorted.
>
I am sorry, my typo. My message should have read "If ALL is specified
then duplicates *are* returned". The default is to remove duplicates,
ALL is not the default.
Sorting both inputs makes the final selection easier and faster even
when duplicates are not removed. As RPost suggests, we could implement
INTERSECT ALL and EXCEPT ALL by just sorting one of the inputs, avoiding
part of the sort cost. Then we would scan through each row in the
unsorted input and use a binary search to see if it is in the sorted
input. In order to output the correct number of duplicates we must mark
the row as removed from the sorted input. I don't think that the
org.apache.derby.iapi.sql.ResultSet interface or the SortedResultSet
class currently implement row deletion or marking.
If the number of rows in the two inputs are m and n the cost of sorting
both is O(n*log(n) + m*log(m)). The final select step has a cost of
O(n+m). If we only sort one input, say the second one, then the sort
cost is O(n*log(n)) and the cost of the final select step is
O(m*log(n)), for a total cost O((m+n)*log(n)). If n < m this is
asymptotically better. The binary searches will have poor locality of
reference and deleting rows from a temporary table that has spilled to
disk may be expensive, so in practice sorting just one input may only be
better when the two inputs have significantly different sizes. Perhaps
in the future we can implement both methods and pick the better one at
optimize time.
I wanted to make an initial implementation that is simple, handles both
INTERSECT and EXCEPT, and that fits into the current Derby
implementation fairly easily. If the performance of INTERSECT or EXCEPT
proves to be important then we should revisit this.
In fact there are a number of related implementation alternatives that
may be optimal under different conditions.
1. Just sort the smaller input and use a binary search to see if each
row in the unsorted input is also in the sorted input. INTERSECT is
commutative, so it does not matter which of its inputs is sorted. EXCEPT
is not commutative. If we sort its left input and scan through the
unsorted right input we have to remove/mark the intersection rows in the
left (sorted) input and output the unremoved/marked rows at the end.
2. We can also handle duplicate elimination when just sorting one input
by removing duplicates when doing the sort, but not removing/marking
rows from the sorted input as they are found in the other input.
3. We can use a hash table instead of sorting. Unfortunately Derby does
not yet have a hash table implementation that spills to disk.
Jack
Jack Klebanoff
Re: [PATCH] Intersect and Except
Posted by RPost <rp...@pacbell.net>.
Your text says 'If ALL is specified then duplicates are not returned'. You
also say that by default duplicates are removed. So is the default ALL? Or
did you mean that if ALL is specified then duplicates are not removed?
If you don't need to remove duplicates then doesn't that mean that you only
need to sort one of the data sets? If so, this would improve performance. If
statistics are available then the smaller dataset should be the one that is
sorted.
----- Original Message -----
From: "Jack Klebanoff" <kl...@Mutagen.Net>
To: "Derby Developers" <de...@db.apache.org>
Sent: Thursday, December 09, 2004 4:59 PM
Subject: [PATCH] Intersect and Except
> Attached is a patch that implements the SQL INTERSECT and EXCEPT
> operators. The INTERSECT operator constructs the intersection of two
> tables. The EXCEPT operator finds all rows in one table but not in the
> other. The syntax is (roughly):
>
> <query expression> INTERSECT [ALL] <query expression>
> <query expression> EXCEPT [ALL] <query expression>
>
> By default these operators remove duplicates, which can occur if there
> are duplicates in the inputs. If ALL is specified then duplicates are
> not returned. If t1 has m copies of row R and t2 has n copies then t1
> INTERSECT ALL t2 returns min(m,n) copies of R, and t1 EXCEPT ALL t2
> returns max( 0, m-n) copies of R.
>
> The EXCEPT operator has the same precedence as UNION. INTERSECT has
> higher precedence.
>
> This follows the SQL-92 spec. (At least it follows my understanding of
> the spec. Spec lawyers are invited to comment).
>
> The implementation uses sorting. The two input tables are sorted and
> then scanned together. The appropriate rows from the left input are
output.
>
> The compiler binds INTERSECT and EXCEPT like UNION. Therefore a new
> class, org.apache.derby.impl.sql.compile.SetOperatorNode, was carved out
> of UnionNode. It mainly contains bind methods. Classes UnionNode and
> IntersectOrExceptNode extend SetOperatorNode. Classes IntersectNode and
> ExceptNode extend IntersectOrExceptNode. IntersectOrExceptNode does most
> of the optimization and code generation work. It puts OrderBy nodes in
> front of its inputs.
>
> The generated code creates a SetOpProjectRestrictResultSet that reads
> its sorted inputs to produce the required output table.
>
> Jack Klebanoff
>
>
>
----------------------------------------------------------------------------
----
> Index: java/engine/org/apache/derby/impl/sql/compile/NodeFactoryImpl.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/NodeFactoryImpl.java
(revision 111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/NodeFactoryImpl.java
(working copy)
> @@ -512,6 +512,12 @@
> case C_NodeTypes.UNION_NODE:
> return C_NodeNames.UNION_NODE_NAME;
>
> + case C_NodeTypes.EXCEPT_NODE:
> + return C_NodeNames.EXCEPT_NODE_NAME;
> +
> + case C_NodeTypes.INTERSECT_NODE:
> + return C_NodeNames.INTERSECT_NODE_NAME;
> +
> case C_NodeTypes.CREATE_TRIGGER_NODE:
> return C_NodeNames.CREATE_TRIGGER_NODE_NAME;
>
> Index: java/engine/org/apache/derby/impl/sql/compile/IntersectNode.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/IntersectNode.java
(revision 0)
> +++ java/engine/org/apache/derby/impl/sql/compile/IntersectNode.java
(revision 0)
> @@ -0,0 +1,60 @@
> +/*
> +
> + Derby - Class org.apache.derby.impl.sql.compile.IntersectNode
> +
> + Copyright 1997, 2004 The Apache Software Foundation or its licensors,
as applicable.
> +
> + Licensed under the Apache License, Version 2.0 (the "License");
> + you may not use this file except in compliance with the License.
> + You may obtain a copy of the License at
> +
> + http://www.apache.org/licenses/LICENSE-2.0
> +
> + Unless required by applicable law or agreed to in writing, software
> + distributed under the License is distributed on an "AS IS" BASIS,
> + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
> + See the License for the specific language governing permissions and
> + limitations under the License.
> +
> + */
> +
> +package org.apache.derby.impl.sql.compile;
> +
> +import org.apache.derby.iapi.services.compiler.MethodBuilder;
> +
> +import org.apache.derby.iapi.services.sanity.SanityManager;
> +
> +import org.apache.derby.iapi.error.StandardException;
> +
> +import java.lang.Math;
> +
> +/**
> + * A IntersectNode represents an INTERSECT DML statement.
> + *
> + * @author Jack Klebanoff
> + */
> +
> +public class IntersectNode extends IntersectOrExceptNode
> +{
> + int getOpType()
> + {
> + return INTERSECT_OP;
> + }
> +
> + String getOperatorName()
> + {
> + return "INTERSECT";
> + }
> +
> + double getRowCountEstimate( double leftRowCount, double
rightRowCount)
> + {
> + // The result has at most min( leftRowCount, rightRowCount).
Estimate the actual row count at
> + // half that.
> + return Math.min( leftRowCount, rightRowCount)/2;
> + }
> +
> + double getSingleScanRowCountEstimate( double leftSingleScanRowCount,
double rightSingleScanRowCount)
> + {
> + return Math.min( leftSingleScanRowCount,
rightSingleScanRowCount)/2;
> + }
> +}
> Index: java/engine/org/apache/derby/impl/sql/compile/C_NodeNames.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/C_NodeNames.java
(revision 111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/C_NodeNames.java
(working copy)
> @@ -258,6 +258,10 @@
>
> static final String UNION_NODE_NAME =
"org.apache.derby.impl.sql.compile.UnionNode";
>
> + static final String EXCEPT_NODE_NAME =
"org.apache.derby.impl.sql.compile.ExceptNode";
> +
> + static final String INTERSECT_NODE_NAME =
"org.apache.derby.impl.sql.compile.IntersectNode";
> +
> static final String UNTYPED_NULL_CONSTANT_NODE_NAME =
"org.apache.derby.impl.sql.compile.UntypedNullConstantNode";
>
> static final String UPDATE_NODE_NAME =
"org.apache.derby.impl.sql.compile.UpdateNode";
> Index: java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/UnionNode.java (revision
111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/UnionNode.java (working
copy)
> @@ -20,15 +20,12 @@
>
> package org.apache.derby.impl.sql.compile;
>
> -import org.apache.derby.iapi.services.context.ContextManager;
> -
> import org.apache.derby.iapi.services.compiler.MethodBuilder;
>
> import org.apache.derby.iapi.services.sanity.SanityManager;
>
> import org.apache.derby.iapi.error.StandardException;
>
> -import org.apache.derby.iapi.sql.compile.CompilerContext;
> import org.apache.derby.iapi.sql.compile.Optimizable;
> import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
> import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
> @@ -37,33 +34,16 @@
> import org.apache.derby.iapi.sql.compile.RowOrdering;
> import org.apache.derby.iapi.sql.compile.C_NodeTypes;
>
> -import org.apache.derby.iapi.sql.dictionary.ColumnDescriptor;
> -import org.apache.derby.iapi.sql.dictionary.DataDictionary;
> -import org.apache.derby.iapi.sql.dictionary.DefaultDescriptor;
> -import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
> import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
>
> -import org.apache.derby.iapi.types.DataTypeDescriptor;
> -
> import org.apache.derby.iapi.reference.SQLState;
> import org.apache.derby.iapi.reference.ClassName;
>
> -import org.apache.derby.iapi.sql.Activation;
> -import org.apache.derby.iapi.types.DataTypeDescriptor;
> -import org.apache.derby.iapi.sql.ResultSet;
> -import org.apache.derby.iapi.sql.Row;
> -
> -import org.apache.derby.iapi.types.TypeId;
> -
> import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
>
> import org.apache.derby.iapi.util.JBitSet;
> import org.apache.derby.iapi.services.classfile.VMOpcode;
>
> -import org.apache.derby.catalog.types.DefaultInfoImpl;
> -
> -import java.util.Properties;
> -
> /**
> * A UnionNode represents a UNION in a DML statement. It contains a
boolean
> * telling whether the union operation should eliminate duplicate rows.
> @@ -71,155 +51,12 @@
> * @author Jeff Lichtman
> */
>
> -public class UnionNode extends TableOperatorNode
> +public class UnionNode extends SetOperatorNode
> {
> - /**
> - ** Tells whether to eliminate duplicate rows. all == TRUE means do
> - ** not eliminate duplicates, all == FALSE means eliminate duplicates.
> - */
> - boolean all;
> -
> - /* Is this a UNION ALL generated for a table constructor. */
> - boolean tableConstructor;
> -
> - /* True if this is the top node of a table constructor */
> - boolean topTableConstructor;
> -
> - /* Only optimize a UNION once */
> + /* Only optimize it once */
> /* Only call addNewNodes() once */
> private boolean addNewNodesCalled;
>
> - private OrderByList orderByList;
> -
> - /**
> - * Initializer for a UnionNode.
> - *
> - * @param leftResult The ResultSetNode on the left side of this union
> - * @param rightResult The ResultSetNode on the right side of this union
> - * @param all Whether or not this is a UNION ALL.
> - * @param tableConstructor Whether or not this is from a table
constructor.
> - * @param tableProperties Properties list associated with the table
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - public void init(
> - Object leftResult,
> - Object rightResult,
> - Object all,
> - Object tableConstructor,
> - Object tableProperties)
> - throws StandardException
> - {
> - super.init(leftResult, rightResult, tableProperties);
> -
> - this.all = ((Boolean) all).booleanValue();
> -
> - /* Is this a UNION ALL for a table constructor? */
> - this.tableConstructor = ((Boolean) tableConstructor).booleanValue();
> -
> - /* resultColumns cannot be null, so we make a copy of the left RCL
> - * for now. At bind() time, we need to recopy the list because there
> - * may have been a "*" in the list. (We will set the names and
> - * column types at that time, as expected.)
> - */
> - resultColumns = leftResultSet.getResultColumns().copyListAndObjects();
> - }
> -
> - /**
> - * Mark this as the top node of a table constructor.
> - */
> - public void markTopTableConstructor()
> - {
> - topTableConstructor = true;
> - }
> -
> - /**
> - * Tell whether this is a UNION for a table constructor.
> - */
> - boolean tableConstructor()
> - {
> - return tableConstructor;
> - }
> -
> - /**
> - * Check for (and reject) ? parameters directly under the ResultColumns.
> - * This is done for SELECT statements. Don't reject parameters that
> - * are in a table constructor - these are allowed, as long as the
> - * table constructor is in an INSERT statement or each column of the
> - * table constructor has at least one non-? column. The latter case
> - * is checked below, in bindExpressions().
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown if a ? parameter found
> - * directly under a ResultColumn
> - */
> - public void rejectParameters() throws StandardException
> - {
> - if ( ! tableConstructor())
> - super.rejectParameters();
> - }
> -
> - /**
> - * Set the type of column in the result column lists of each
> - * source of this union tree to the type in the given result column list
> - * (which represents the result columns for an insert).
> - * This is only for table constructors that appear in insert statements.
> - *
> - * @param typeColumns The ResultColumnList containing the desired result
> - * types.
> - *
> - * @exception StandardException Thrown on error
> - */
> - void setTableConstructorTypes(ResultColumnList typeColumns)
> - throws StandardException
> - {
> - if (SanityManager.DEBUG)
> - {
> - SanityManager.ASSERT(resultColumns.size() <= typeColumns.size(),
> - "More columns in ResultColumnList than in base table.");
> - }
> -
> - ResultSetNode rsn;
> -
> - /*
> - ** Should only set types of ? parameters to types of result columns
> - ** if it's a table constructor.
> - */
> - if (tableConstructor())
> - {
> - /* By looping through the union nodes, we avoid recursion */
> - for (rsn = this; rsn instanceof UnionNode; )
> - {
> - UnionNode union = (UnionNode) rsn;
> -
> - /*
> - ** Assume that table constructors are left-deep trees of UnionNodes
> - ** with RowResultSet nodes on the right.
> - */
> - if (SanityManager.DEBUG)
> - SanityManager.ASSERT(
> - union.rightResultSet instanceof RowResultSetNode,
> - "A " + union.rightResultSet.getClass().getName() +
> - " is on the right of a union in a table constructor");
> -
> - ((RowResultSetNode) union.rightResultSet).setTableConstructorTypes(
> - typeColumns);
> -
> - rsn = union.leftResultSet;
> - }
> -
> - /* The last node on the left should be a result set node */
> - if (SanityManager.DEBUG)
> - SanityManager.ASSERT(rsn instanceof RowResultSetNode,
> - "A " + rsn.getClass().getName() +
> - " is at the left end of a table constructor");
> -
> - ((RowResultSetNode) rsn).setTableConstructorTypes(typeColumns);
> - }
> - }
> -
> /*
> * Optimizable interface
> */
> @@ -411,654 +248,6 @@
> return treeTop;
> }
>
> - /**
> - * Convert this object to a String. See comments in QueryTreeNode.java
> - * for how this should be done for tree printing.
> - *
> - * @return This object as a String
> - */
> -
> - public String toString()
> - {
> - if (SanityManager.DEBUG)
> - {
> - return "all: " + all + "\n" +
> - "tableConstructor: " + tableConstructor + "\n" +
> - "orderByList: " +
> - (orderByList != null ? orderByList.toString() : "null") + "\n" +
> - super.toString();
> - }
> - else
> - {
> - return "";
> - }
> - }
> -
> - /**
> - * Bind the expressions under this TableOperatorNode. This means
> - * binding the sub-expressions, as well as figuring out what the
> - * return type is for each expression.
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - public void bindExpressions(FromList fromListParam)
> - throws StandardException
> - {
> - super.bindExpressions(fromListParam);
> -
> - /*
> - ** Each ? parameter in a table constructor that is not in an insert
> - ** statement takes its type from the first non-? in its column
> - ** of the table constructor. It's an error to have a column that
> - ** has all ?s. Do this only for the top of the table constructor
> - ** list - we don't want to do this for every level of union node
> - ** in the table constructor. Also, don't do this for an INSERT -
> - ** the types of the ? parameters come from the columns being inserted
> - ** into in that case.
> - */
> - if (topTableConstructor && ( ! insertSource) )
> - {
> - /*
> - ** Step through all the rows in the table constructor to
> - ** get the type of the first non-? in each column.
> - */
> - DataTypeDescriptor[] types =
> - new DataTypeDescriptor[leftResultSet.getResultColumns().size()];
> -
> - ResultSetNode rsn;
> - int numTypes = 0;
> -
> - /* By looping through the union nodes, we avoid recursion */
> - for (rsn = this; rsn instanceof UnionNode; )
> - {
> - UnionNode union = (UnionNode) rsn;
> -
> - /*
> - ** Assume that table constructors are left-deep trees of
> - ** UnionNodes with RowResultSet nodes on the right.
> - */
> - if (SanityManager.DEBUG)
> - SanityManager.ASSERT(
> - union.rightResultSet instanceof RowResultSetNode,
> - "A " + union.rightResultSet.getClass().getName() +
> - " is on the right side of a union in a table constructor");
> -
> - RowResultSetNode rrsn =
> - (RowResultSetNode) union.rightResultSet;
> -
> - numTypes += getParamColumnTypes(types, rrsn);
> -
> - rsn = union.leftResultSet;
> - }
> -
> - /* The last node on the left should be a result set node */
> - if (SanityManager.DEBUG)
> - SanityManager.ASSERT(rsn instanceof RowResultSetNode);
> -
> - numTypes += getParamColumnTypes(types, (RowResultSetNode) rsn);
> -
> - /* Are there any columns that are all ? parameters? */
> - if (numTypes < types.length)
> - {
> - throw
StandardException.newException(SQLState.LANG_TABLE_CONSTRUCTOR_ALL_PARAM_COL
UMN);
> - }
> -
> - /*
> - ** Loop through the nodes again. This time, look for parameter
> - ** nodes, and give them the type from the type array we just
> - ** constructed.
> - */
> - for (rsn = this; rsn instanceof UnionNode; )
> - {
> - UnionNode union = (UnionNode) rsn;
> - RowResultSetNode rrsn =
> - (RowResultSetNode) union.rightResultSet;
> -
> - setParamColumnTypes(types, rrsn);
> -
> - rsn = union.leftResultSet;
> - }
> -
> - setParamColumnTypes(types, (RowResultSetNode) rsn);
> - }
> - }
> -
> - /**
> - * Bind the result columns of this ResultSetNode when there is no
> - * base table to bind them to. This is useful for SELECT statements,
> - * where the result columns get their types from the expressions that
> - * live under them.
> - *
> - * @param fromListParam FromList to use/append to.
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown on error
> - */
> - public void bindResultColumns(FromList fromListParam)
> - throws StandardException
> - {
> - super.bindResultColumns(fromListParam);
> -
> - /* Now we build our RCL */
> - buildRCL();
> - }
> -
> - /**
> - * Bind the result columns for this ResultSetNode to a base table.
> - * This is useful for INSERT and UPDATE statements, where the
> - * result columns get their types from the table being updated or
> - * inserted into.
> - * If a result column list is specified, then the verification that the
> - * result column list does not contain any duplicates will be done when
> - * binding them by name.
> - *
> - * @param targetTableDescriptor The TableDescriptor for the table being
> - * updated or inserted into
> - * @param targetColumnList For INSERT statements, the user
> - * does not have to supply column
> - * names (for example, "insert into t
> - * values (1,2,3)". When this
> - * parameter is null, it means that
> - * the user did not supply column
> - * names, and so the binding should
> - * be done based on order. When it
> - * is not null, it means do the binding
> - * by name, not position.
> - * @param statement Calling DMLStatementNode (Insert or Update)
> - * @param fromListParam FromList to use/append to.
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - public void bindResultColumns(TableDescriptor targetTableDescriptor,
> - FromVTI targetVTI,
> - ResultColumnList targetColumnList,
> - DMLStatementNode statement,
> - FromList fromListParam)
> - throws StandardException
> - {
> - super.bindResultColumns(targetTableDescriptor,
> - targetVTI,
> - targetColumnList, statement,
> - fromListParam);
> -
> - /* Now we build our RCL */
> - buildRCL();
> - }
> -
> - /**
> - * Build the RCL for this node. We propagate the RCL up from the
> - * left child to form this node's RCL.
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - private void buildRCL() throws StandardException
> - {
> - /* Verify that both sides of the union have the same # of columns in
their
> - * RCL.
> - */
> - if (leftResultSet.getResultColumns().size() !=
> - rightResultSet.getResultColumns().size())
> - {
> - throw
StandardException.newException(SQLState.LANG_UNION_UNMATCHED_COLUMNS);
> - }
> -
> - /* We need to recreate resultColumns for this node, since there
> - * may have been 1 or more *'s in the left's SELECT list.
> - */
> - resultColumns = leftResultSet.getResultColumns().copyListAndObjects();
> -
> - /* Create new expressions with the dominant types after verifying
> - * union compatibility between left and right sides.
> - */
> -
resultColumns.setUnionResultExpression(rightResultSet.getResultColumns(),
tableNumber, level);
> - }
> -
> - /**
> - * Bind the result columns of a table constructor to the types in the
> - * given ResultColumnList. Use when inserting from a table constructor,
> - * and there are nulls in the values clauses.
> - *
> - * @param rcl The ResultColumnList with the types to bind to
> - *
> - * @exception StandardException Thrown on error.
> - */
> - public void bindUntypedNullsToResultColumns(ResultColumnList rcl)
> - throws StandardException
> - {
> - /*
> - ** If the RCL from the parent is null, then
> - ** the types are coming from the union itself.
> - ** So we have to cross check the two child
> - ** rcls.
> - */
> - if (rcl == null)
> - {
> - ResultColumnList lrcl = rightResultSet.getResultColumns();
> - ResultColumnList rrcl = leftResultSet.getResultColumns();
> -
> - leftResultSet.bindUntypedNullsToResultColumns(rrcl);
> - rightResultSet.bindUntypedNullsToResultColumns(lrcl);
> - }
> - else
> - {
> - leftResultSet.bindUntypedNullsToResultColumns(rcl);
> - rightResultSet.bindUntypedNullsToResultColumns(rcl);
> - }
> - }
> -
> - /**
> - * Get the parameter types from the given RowResultSetNode into the
> - * given array of types. If an array position is already filled in,
> - * don't clobber it.
> - *
> - * @param types The array of types to fill in
> - * @param rrsn The RowResultSetNode from which to take the param types
> - *
> - * @return The number of new types found in the RowResultSetNode
> - */
> - int getParamColumnTypes(DataTypeDescriptor[] types, RowResultSetNode
rrsn)
> - {
> - int numTypes = 0;
> -
> - /* Look for columns where we have not found a non-? yet. */
> - for (int i = 0; i < types.length; i++)
> - {
> - if (types[i] == null)
> - {
> - ResultColumn rc =
> - (ResultColumn) rrsn.getResultColumns().elementAt(i);
> - if ( ! (rc.getExpression().isParameterNode()))
> - {
> - types[i] = rc.getExpressionType();
> - numTypes++;
> - }
> - }
> - }
> -
> - return numTypes;
> - }
> -
> - /**
> - * Set the type of each ? parameter in the given RowResultSetNode
> - * according to its ordinal position in the given array of types.
> - *
> - * @param types An array of types containing the proper type for each
> - * ? parameter, by ordinal position.
> - * @param rrsn A RowResultSetNode that could contain ? parameters whose
> - * types need to be set.
> - *
> - * @exception StandardException Thrown on error
> - */
> - void setParamColumnTypes(DataTypeDescriptor[] types, RowResultSetNode
rrsn)
> - throws StandardException
> - {
> - /*
> - ** Look for ? parameters in the result column list
> - ** of each RowResultSetNode
> - */
> - ResultColumnList rrcl = rrsn.getResultColumns();
> - int rrclSize = rrcl.size();
> - for (int index = 0; index < rrclSize; index++)
> - {
> - ResultColumn rc = (ResultColumn) rrcl.elementAt(index);
> -
> - if (rc.getExpression().isParameterNode())
> - {
> - /*
> - ** We found a ? - set its type to the type from the
> - ** type array.
> - */
> - ((ParameterNode) rc.getExpression()).setDescriptor(
> - types[index]);
> - }
> - }
> - }
> -
> - /**
> - * Bind the expressions in the target list. This means binding the
> - * sub-expressions, as well as figuring out what the return type is
> - * for each expression. This is useful for EXISTS subqueries, where we
> - * need to validate the target list before blowing it away and replacing
> - * it with a SELECT true.
> - *
> - * @return Nothing
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - public void bindTargetExpressions(FromList fromListParam)
> - throws StandardException
> - {
> - leftResultSet.bindTargetExpressions(fromListParam);
> - rightResultSet.bindTargetExpressions(fromListParam);
> - }
> -
> - /**
> - * Push the order by list down from the cursor node
> - * into its child result set so that the optimizer
> - * has all of the information that it needs to
> - * consider sort avoidance.
> - *
> - * @param orderByList The order by list
> - *
> - * @return Nothing.
> - */
> - void pushOrderByList(OrderByList orderByList)
> - {
> - this.orderByList = orderByList;
> - }
> -
> - /**
> - * Put a ProjectRestrictNode on top of each FromTable in the FromList.
> - * ColumnReferences must continue to point to the same ResultColumn, so
> - * that ResultColumn must percolate up to the new PRN. However,
> - * that ResultColumn will point to a new expression, a VirtualColumnNode,
> - * which points to the FromTable and the ResultColumn that is the source
for
> - * the ColumnReference.
> - * (The new PRN will have the original of the ResultColumnList and
> - * the ResultColumns from that list. The FromTable will get shallow
copies
> - * of the ResultColumnList and its ResultColumns.
ResultColumn.expression
> - * will remain at the FromTable, with the PRN getting a new
> - * VirtualColumnNode for each ResultColumn.expression.)
> - * We then project out the non-referenced columns. If there are no
referenced
> - * columns, then the PRN's ResultColumnList will consist of a single
ResultColumn
> - * whose expression is 1.
> - *
> - * @param numTables Number of tables in the DML Statement
> - * @param gbl The group by list, if any
> - * @param fromList The from list, if any
> - *
> - * @return The generated ProjectRestrictNode atop the original FromTable.
> - *
> - * @exception StandardException Thrown on error
> - */
> -
> - public ResultSetNode preprocess(int numTables,
> - GroupByList gbl,
> - FromList fromList)
> - throws StandardException
> - {
> - ResultSetNode newTop = this;
> -
> - /* RESOLVE - what does numTables and referencedTableMap mean here? */
> - leftResultSet = leftResultSet.preprocess(numTables, gbl, fromList);
> - rightResultSet = rightResultSet.preprocess(numTables, gbl, fromList);
> -
> - /* Build the referenced table map (left || right) */
> - referencedTableMap = (JBitSet)
leftResultSet.getReferencedTableMap().clone();
> - referencedTableMap.or((JBitSet) rightResultSet.getReferencedTableMap());
> -
> - /* If this is a UNION without an all and we have
> - * an order by then we can consider eliminating the sort for the
> - * order by. All of the columns in the order by list must
> - * be ascending in order to do this. There are 2 cases:
> - * o The order by list is an in order prefix of the columns
> - * in the select list. In this case the output of the
> - * sort from the distinct will be in the right order
> - * so we simply eliminate the order by list.
> - * o The order by list is a subset of the columns in the
> - * the select list. In this case we need to reorder the
> - * columns in the select list so that the ordering columns
> - * are an in order prefix of the select list and put a PRN
> - * above the select so that the shape of the result set
> - * is as expected.
> - */
> - if ((! all) && orderByList != null && orderByList.allAscending())
> - {
> - /* Order by list currently restricted to columns in select
> - * list, so we will always eliminate the order by here.
> - */
> - if (orderByList.isInOrderPrefix(resultColumns))
> - {
> - orderByList = null;
> - }
> - /* RESOLVE - We currently only eliminate the order by if it is
> - * a prefix of the select list. We do not currently do the
> - * elimination if the order by is not a prefix because the code
> - * doesn't work. The problem has something to do with the
> - * fact that we generate additional nodes between the union
> - * and the PRN (for reordering that we would generate here)
> - * when modifying the access paths. VCNs under the PRN can be
> - * seen as correlated since their source resultset is the Union
> - * which is no longer the result set directly under them. This
> - * causes the wrong code to get generated. (jerry - 11/3/98)
> - * (bug 59)
> - */
> - }
> -
> - return newTop;
> - }
> -
> - /**
> - * Ensure that the top of the RSN tree has a PredicateList.
> - *
> - * @param numTables The number of tables in the query.
> - * @return ResultSetNode A RSN tree with a node which has a PredicateList
on top.
> - *
> - * @exception StandardException Thrown on error
> - */
> - public ResultSetNode ensurePredicateList(int numTables)
> - throws StandardException
> - {
> - return genProjectRestrict(numTables);
> - }
> -
> - /**
> - * Verify that a SELECT * is valid for this type of subquery.
> - *
> - * @param outerFromList The FromList from the outer query block(s)
> - * @param subqueryType The subquery type
> - *
> - * @return None
> - *
> - * @exception StandardException Thrown on error
> - */
> - public void verifySelectStarSubquery(FromList outerFromList, int
subqueryType)
> - throws StandardException
> - {
> - /* Check both sides - SELECT * is not valid on either side */
> - leftResultSet.verifySelectStarSubquery(outerFromList, subqueryType);
> - rightResultSet.verifySelectStarSubquery(outerFromList, subqueryType);
> - }
> -
> - /**
> - * Determine whether or not the specified name is an exposed name in
> - * the current query block.
> - *
> - * @param name The specified name to search for as an exposed name.
> - * @param schemaName Schema name, if non-null.
> - * @param exactMatch Whether or not we need an exact match on specified
schema and table
> - * names or match on table id.
> - *
> - * @return The FromTable, if any, with the exposed name.
> - *
> - * @exception StandardException Thrown on error
> - */
> - protected FromTable getFromTableByName(String name, String schemaName,
boolean exactMatch)
> - throws StandardException
> - {
> - /* We search both sides for a TableOperatorNode (join nodes)
> - * but only the left side for a UnionNode.
> - */
> - return leftResultSet.getFromTableByName(name, schemaName, exactMatch);
> - }
> -
> - /**
> - * Set the result column for the subquery to a boolean true,
> - * Useful for transformations such as
> - * changing:
> - * where exists (select ... from ...)
> - * to:
> - * where (select true from ...)
> - *
> - * NOTE: No transformation is performed if the ResultColumn.expression is
> - * already the correct boolean constant.
> - *
> - * @param onlyConvertAlls Boolean, whether or not to just convert *'s
> - *
> - * @return Nothing.
> - *
> - * @exception StandardException Thrown on error
> - */
> - public void setResultToBooleanTrueNode(boolean onlyConvertAlls)
> - throws StandardException
> - {
> - super.setResultToBooleanTrueNode(onlyConvertAlls);
> - leftResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
> - rightResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
> - }
> -
> - /**
> - * This ResultSet is the source for an Insert. The target RCL
> - * is in a different order and/or a superset of this RCL. In most cases
> - * we will reorder and/or add defaults to the current RCL so that is
> - * matches the target RCL. Those RSNs whose generate() method does
> - * not handle projects will insert a PRN, with a new RCL which matches
> - * the target RCL, above the current RSN.
> - * NOTE - The new or enhanced RCL will be fully bound.
> - *
> - * @param numTargetColumns # of columns in target RCL
> - * @param colMap[] int array representation of correspondence between
> - * RCLs - colmap[i] = -1 -> missing in current RCL
> - * colmap[i] = j -> targetRCL(i) <-> thisRCL(j+1)
> - * @param dataDictionary DataDictionary to use
> - * @param targetTD TableDescriptor for target if the target is not a VTI,
null if a VTI
> - * @param targetVTI Target description if it is a VTI, null
if not a VTI
> - *
> - * @return ResultSetNode The new top of the tree
> - *
> - * @exception StandardException Thrown on error
> - */
> - public ResultSetNode enhanceRCLForInsert(int numTargetColumns, int[]
colMap,
> - DataDictionary dataDictionary,
> - TableDescriptor targetTD,
> - FromVTI targetVTI)
> - throws StandardException
> - {
> - // our newResultCols are put into the bound form straight away.
> - ResultColumnList newResultCols =
> - (ResultColumnList) getNodeFactory().getNode(
> - C_NodeTypes.RESULT_COLUMN_LIST,
> - getContextManager());
> - int numResultSetColumns = resultColumns.size();
> -
> - /* Create a massaged version of the source RCL.
> - * (Much simpler to build new list and then assign to source,
> - * rather than massage the source list in place.)
> - */
> - for (int index = 0; index < numTargetColumns; index++)
> - {
> - ResultColumn newResultColumn;
> - ResultColumn oldResultColumn;
> - ColumnReference newColumnReference;
> -
> - if (colMap[index] != -1)
> - {
> - // getResultColumn uses 1-based positioning, so offset the colMap entry
appropriately
> - oldResultColumn = resultColumns.getResultColumn(colMap[index]+1);
> -
> - newColumnReference = (ColumnReference) getNodeFactory().getNode(
> - C_NodeTypes.COLUMN_REFERENCE,
> - oldResultColumn.getName(),
> - null,
> - getContextManager());
> - /* The ColumnReference points to the source of the value */
> - newColumnReference.setSource(oldResultColumn);
> - // colMap entry is 0-based, columnId is 1-based.
> - newColumnReference.setType(oldResultColumn.getExpressionType());
> -
> - // Source of an insert, so nesting levels must be 0
> - newColumnReference.setNestingLevel(0);
> - newColumnReference.setSourceLevel(0);
> -
> - // because the insert already copied the target table's
> - // column descriptors into the result, we grab it from there.
> - // alternatively, we could do what the else clause does,
> - // and look it up in the DD again.
> - newResultColumn = (ResultColumn) getNodeFactory().getNode(
> - C_NodeTypes.RESULT_COLUMN,
> - oldResultColumn.getType(),
> - newColumnReference,
> - getContextManager());
> - }
> - else
> - {
> - newResultColumn = genNewRCForInsert(targetTD, targetVTI, index + 1,
dataDictionary);
> - }
> -
> - newResultCols.addResultColumn(newResultColumn);
> - }
> -
> - /* The generated ProjectRestrictNode now has the ResultColumnList
> - * in the order that the InsertNode expects.
> - * NOTE: This code here is an exception to several "rules":
> - * o This is the only ProjectRestrictNode that is currently
> - * generated outside of preprocess().
> - * o The UnionNode is the only node which is not at the
> - * top of the query tree which has ColumnReferences under
> - * its ResultColumnList prior to expression push down.
> - */
> - return (ResultSetNode) getNodeFactory().getNode(
> - C_NodeTypes.PROJECT_RESTRICT_NODE,
> - this,
> - newResultCols,
> - null,
> - null,
> - null,
> - null,
> - tableProperties,
> - getContextManager());
> - }
> -
> - /**
> - * Evaluate whether or not the subquery in a FromSubquery is flattenable.
> - * Currently, a FSqry is flattenable if all of the following are true:
> - * o Subquery is a SelectNode. (ie, not a RowResultSetNode or a
UnionNode)
> - * o It contains no top level subqueries. (RESOLVE - we can relax this)
> - * o It does not contain a group by or having clause
> - * o It does not contain aggregates.
> - *
> - * @param fromList The outer from list
> - *
> - * @return boolean Whether or not the FromSubquery is flattenable.
> - */
> - public boolean flattenableInFromSubquery(FromList fromList)
> - {
> - /* Unions in FromSubquerys are not flattenable. */
> - return false;
> - }
> -
> - /**
> - * Return whether or not to materialize this ResultSet tree.
> - *
> - * @return Whether or not to materialize this ResultSet tree.
> - * would return valid results.
> - *
> - * @exception StandardException Thrown on error
> - */
> - public boolean performMaterialization(JBitSet outerTables)
> - throws StandardException
> - {
> - // RESOLVE - just say no to materialization right now - should be a cost
based decision
> - return false;
> -
> - /* Actual materialization, if appropriate, will be placed by our parent
PRN.
> - * This is because PRN might have a join condition to apply.
(Materialization
> - * can only occur before that.
> - */
> - //return true;
> - }
> -
> /**
> * Generate the code for this UnionNode.
> *
> @@ -1134,4 +323,9 @@
>
> mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null,
"getUnionResultSet", ClassName.NoPutResultSet, 7);
> }
> +
> + String getOperatorName()
> + {
> + return "UNION";
> + }
> }
> Index: java/engine/org/apache/derby/impl/sql/compile/ExceptNode.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/ExceptNode.java
(revision 0)
> +++ java/engine/org/apache/derby/impl/sql/compile/ExceptNode.java
(revision 0)
> @@ -0,0 +1,60 @@
> +/*
> +
> + Derby - Class org.apache.derby.impl.sql.compile.ExceptNode
> +
> + Copyright 1997, 2004 The Apache Software Foundation or its licensors,
as applicable.
> +
> + Licensed under the Apache License, Version 2.0 (the "License");
> + you may not use this file except in compliance with the License.
> + You may obtain a copy of the License at
> +
> + http://www.apache.org/licenses/LICENSE-2.0
> +
> + Unless required by applicable law or agreed to in writing, software
> + distributed under the License is distributed on an "AS IS" BASIS,
> + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
> + See the License for the specific language governing permissions and
> + limitations under the License.
> +
> + */
> +
> +package org.apache.derby.impl.sql.compile;
> +
> +import org.apache.derby.iapi.services.compiler.MethodBuilder;
> +
> +import org.apache.derby.iapi.services.sanity.SanityManager;
> +
> +import org.apache.derby.iapi.error.StandardException;
> +
> +import java.lang.Math;
> +
> +/**
> + * A ExceptNode represents an EXCEPT DML statement.
> + *
> + * @author Jack Klebanoff
> + */
> +
> +public class ExceptNode extends IntersectOrExceptNode
> +{
> + int getOpType()
> + {
> + return EXCEPT_OP;
> + }
> +
> + String getOperatorName()
> + {
> + return "EXCEPT";
> + }
> +
> + double getRowCountEstimate( double leftRowCount, double
rightRowCount)
> + {
> + // The result has at most min( leftRowCount, rightRowCount).
Estimate the actual row count at
> + // half that.
> + return Math.min( leftRowCount, rightRowCount)/2;
> + }
> +
> + double getSingleScanRowCountEstimate( double leftSingleScanRowCount,
double rightSingleScanRowCount)
> + {
> + return Math.min( leftSingleScanRowCount,
rightSingleScanRowCount)/2;
> + }
> +}
> Index: java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
(revision 0)
> +++ java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
(revision 0)
> @@ -0,0 +1,845 @@
> +/*
> +
> + Derby - Class org.apache.derby.impl.sql.compile.SetOperatorNode
> +
> + Copyright 1997, 2004 The Apache Software Foundation or its licensors,
as applicable.
> +
> + Licensed under the Apache License, Version 2.0 (the "License");
> + you may not use this file except in compliance with the License.
> + You may obtain a copy of the License at
> +
> + http://www.apache.org/licenses/LICENSE-2.0
> +
> + Unless required by applicable law or agreed to in writing, software
> + distributed under the License is distributed on an "AS IS" BASIS,
> + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
> + See the License for the specific language governing permissions and
> + limitations under the License.
> +
> + */
> +
> +package org.apache.derby.impl.sql.compile;
> +
> +import org.apache.derby.iapi.services.sanity.SanityManager;
> +
> +import org.apache.derby.iapi.error.StandardException;
> +
> +import org.apache.derby.iapi.sql.compile.C_NodeTypes;
> +
> +import org.apache.derby.iapi.sql.dictionary.DataDictionary;
> +import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
> +
> +import org.apache.derby.iapi.reference.SQLState;
> +import org.apache.derby.iapi.types.DataTypeDescriptor;
> +
> +import org.apache.derby.iapi.util.JBitSet;
> +
> +/**
> + * A SetOperatorNode represents a UNION, INTERSECT, or EXCEPT in a DML
statement. Binding and optimization
> + * preprocessing is the same for all of these operations, so they share
bind methods in this abstract class.
> + *
> + * The class contains a boolean telling whether the operation should
eliminate
> + * duplicate rows.
> + *
> + * @author Jeff Lichtman
> + */
> +
> +public abstract class SetOperatorNode extends TableOperatorNode
> +{
> + /**
> + ** Tells whether to eliminate duplicate rows. all == TRUE means do
> + ** not eliminate duplicates, all == FALSE means eliminate duplicates.
> + */
> + boolean all;
> +
> + /* Is this a UNION ALL generated for a table constructor. */
> + boolean tableConstructor;
> +
> + /* True if this is the top node of a table constructor */
> + boolean topTableConstructor;
> +
> + OrderByList orderByList;
> +
> +
> + /**
> + * Initializer for a SetOperatorNode.
> + *
> + * @param leftResult The ResultSetNode on the left side of this union
> + * @param rightResult The ResultSetNode on the right side of this union
> + * @param all Whether or not this is an ALL.
> + * @param tableConstructor Whether or not this is from a table
constructor.
> + * @param tableProperties Properties list associated with the table
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public void init(
> + Object leftResult,
> + Object rightResult,
> + Object all,
> + Object tableConstructor,
> + Object tableProperties)
> + throws StandardException
> + {
> + super.init(leftResult, rightResult, tableProperties);
> +
> + this.all = ((Boolean) all).booleanValue();
> +
> + /* Is this an ALL for a table constructor? */
> + this.tableConstructor = ((Boolean) tableConstructor).booleanValue();
> +
> + /* resultColumns cannot be null, so we make a copy of the left RCL
> + * for now. At bind() time, we need to recopy the list because there
> + * may have been a "*" in the list. (We will set the names and
> + * column types at that time, as expected.)
> + */
> + resultColumns = leftResultSet.getResultColumns().copyListAndObjects();
> + }
> +
> + /**
> + * Mark this as the top node of a table constructor.
> + */
> + public void markTopTableConstructor()
> + {
> + topTableConstructor = true;
> + }
> +
> + /**
> + * Tell whether this is a UNION for a table constructor.
> + */
> + boolean tableConstructor()
> + {
> + return tableConstructor;
> + }
> +
> + /**
> + * Check for (and reject) ? parameters directly under the ResultColumns.
> + * This is done for SELECT statements. Don't reject parameters that
> + * are in a table constructor - these are allowed, as long as the
> + * table constructor is in an INSERT statement or each column of the
> + * table constructor has at least one non-? column. The latter case
> + * is checked below, in bindExpressions().
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown if a ? parameter found
> + * directly under a ResultColumn
> + */
> + public void rejectParameters() throws StandardException
> + {
> + if ( ! tableConstructor())
> + super.rejectParameters();
> + }
> +
> + /**
> + * Set the type of column in the result column lists of each
> + * source of this union tree to the type in the given result column list
> + * (which represents the result columns for an insert).
> + * This is only for table constructors that appear in insert statements.
> + *
> + * @param typeColumns The ResultColumnList containing the desired result
> + * types.
> + *
> + * @exception StandardException Thrown on error
> + */
> + void setTableConstructorTypes(ResultColumnList typeColumns)
> + throws StandardException
> + {
> + if (SanityManager.DEBUG)
> + {
> + SanityManager.ASSERT(resultColumns.size() <= typeColumns.size(),
> + "More columns in ResultColumnList than in base table.");
> + }
> +
> + ResultSetNode rsn;
> +
> + /*
> + ** Should only set types of ? parameters to types of result columns
> + ** if it's a table constructor.
> + */
> + if (tableConstructor())
> + {
> + /* By looping through the union nodes, we avoid recursion */
> + for (rsn = this; rsn instanceof UnionNode; )
> + {
> + UnionNode union = (UnionNode) rsn;
> +
> + /*
> + ** Assume that table constructors are left-deep trees of UnionNodes
> + ** with RowResultSet nodes on the right.
> + */
> + if (SanityManager.DEBUG)
> + SanityManager.ASSERT(
> + union.rightResultSet instanceof RowResultSetNode,
> + "A " + union.rightResultSet.getClass().getName() +
> + " is on the right of a union in a table constructor");
> +
> + ((RowResultSetNode) union.rightResultSet).setTableConstructorTypes(
> + typeColumns);
> +
> + rsn = union.leftResultSet;
> + }
> +
> + /* The last node on the left should be a result set node */
> + if (SanityManager.DEBUG)
> + SanityManager.ASSERT(rsn instanceof RowResultSetNode,
> + "A " + rsn.getClass().getName() +
> + " is at the left end of a table constructor");
> +
> + ((RowResultSetNode) rsn).setTableConstructorTypes(typeColumns);
> + }
> + }
> +
> + /**
> + * Convert this object to a String. See comments in QueryTreeNode.java
> + * for how this should be done for tree printing.
> + *
> + * @return This object as a String
> + */
> +
> + public String toString()
> + {
> + if (SanityManager.DEBUG)
> + {
> + return "all: " + all + "\n" +
> + "tableConstructor: " + tableConstructor + "\n" +
> + "orderByList: " +
> + (orderByList != null ? orderByList.toString() : "null") + "\n" +
> + super.toString();
> + }
> + else
> + {
> + return "";
> + }
> + }
> +
> + /**
> + * Bind the expressions under this TableOperatorNode. This means
> + * binding the sub-expressions, as well as figuring out what the
> + * return type is for each expression.
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public void bindExpressions(FromList fromListParam)
> + throws StandardException
> + {
> + super.bindExpressions(fromListParam);
> +
> + /*
> + ** Each ? parameter in a table constructor that is not in an insert
> + ** statement takes its type from the first non-? in its column
> + ** of the table constructor. It's an error to have a column that
> + ** has all ?s. Do this only for the top of the table constructor
> + ** list - we don't want to do this for every level of union node
> + ** in the table constructor. Also, don't do this for an INSERT -
> + ** the types of the ? parameters come from the columns being inserted
> + ** into in that case.
> + */
> + if (topTableConstructor && ( ! insertSource) )
> + {
> + /*
> + ** Step through all the rows in the table constructor to
> + ** get the type of the first non-? in each column.
> + */
> + DataTypeDescriptor[] types =
> + new DataTypeDescriptor[leftResultSet.getResultColumns().size()];
> +
> + ResultSetNode rsn;
> + int numTypes = 0;
> +
> + /* By looping through the union nodes, we avoid recursion */
> + for (rsn = this; rsn instanceof SetOperatorNode; )
> + {
> + SetOperatorNode setOperator = (SetOperatorNode) rsn;
> +
> + /*
> + ** Assume that table constructors are left-deep trees of
> + ** SetOperatorNodes with RowResultSet nodes on the right.
> + */
> + if (SanityManager.DEBUG)
> + SanityManager.ASSERT(
> + setOperator.rightResultSet instanceof RowResultSetNode,
> + "A " + setOperator.rightResultSet.getClass().getName() +
> + " is on the right side of a setOperator in a table constructor");
> +
> + RowResultSetNode rrsn =
> + (RowResultSetNode) setOperator.rightResultSet;
> +
> + numTypes += getParamColumnTypes(types, rrsn);
> +
> + rsn = setOperator.leftResultSet;
> + }
> +
> + /* The last node on the left should be a result set node */
> + if (SanityManager.DEBUG)
> + SanityManager.ASSERT(rsn instanceof RowResultSetNode);
> +
> + numTypes += getParamColumnTypes(types, (RowResultSetNode) rsn);
> +
> + /* Are there any columns that are all ? parameters? */
> + if (numTypes < types.length)
> + {
> + throw
StandardException.newException(SQLState.LANG_TABLE_CONSTRUCTOR_ALL_PARAM_COL
UMN);
> + }
> +
> + /*
> + ** Loop through the nodes again. This time, look for parameter
> + ** nodes, and give them the type from the type array we just
> + ** constructed.
> + */
> + for (rsn = this; rsn instanceof SetOperatorNode; )
> + {
> + SetOperatorNode setOperator = (SetOperatorNode) rsn;
> + RowResultSetNode rrsn = (RowResultSetNode) setOperator.rightResultSet;
> +
> + setParamColumnTypes(types, rrsn);
> +
> + rsn = setOperator.leftResultSet;
> + }
> +
> + setParamColumnTypes(types, (RowResultSetNode) rsn);
> + }
> + }
> +
> + /**
> + * Bind the result columns of this ResultSetNode when there is no
> + * base table to bind them to. This is useful for SELECT statements,
> + * where the result columns get their types from the expressions that
> + * live under them.
> + *
> + * @param fromListParam FromList to use/append to.
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown on error
> + */
> + public void bindResultColumns(FromList fromListParam)
> + throws StandardException
> + {
> + super.bindResultColumns(fromListParam);
> +
> + /* Now we build our RCL */
> + buildRCL();
> + }
> +
> + /**
> + * Bind the result columns for this ResultSetNode to a base table.
> + * This is useful for INSERT and UPDATE statements, where the
> + * result columns get their types from the table being updated or
> + * inserted into.
> + * If a result column list is specified, then the verification that the
> + * result column list does not contain any duplicates will be done when
> + * binding them by name.
> + *
> + * @param targetTableDescriptor The TableDescriptor for the table being
> + * updated or inserted into
> + * @param targetColumnList For INSERT statements, the user
> + * does not have to supply column
> + * names (for example, "insert into t
> + * values (1,2,3)". When this
> + * parameter is null, it means that
> + * the user did not supply column
> + * names, and so the binding should
> + * be done based on order. When it
> + * is not null, it means do the binding
> + * by name, not position.
> + * @param statement Calling DMLStatementNode (Insert or Update)
> + * @param fromListParam FromList to use/append to.
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public void bindResultColumns(TableDescriptor targetTableDescriptor,
> + FromVTI targetVTI,
> + ResultColumnList targetColumnList,
> + DMLStatementNode statement,
> + FromList fromListParam)
> + throws StandardException
> + {
> + super.bindResultColumns(targetTableDescriptor,
> + targetVTI,
> + targetColumnList, statement,
> + fromListParam);
> +
> + /* Now we build our RCL */
> + buildRCL();
> + }
> +
> + /**
> + * Build the RCL for this node. We propagate the RCL up from the
> + * left child to form this node's RCL.
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + private void buildRCL() throws StandardException
> + {
> + /* Verify that both sides of the union have the same # of columns in
their
> + * RCL.
> + */
> + if (leftResultSet.getResultColumns().size() !=
> + rightResultSet.getResultColumns().size())
> + {
> + throw
StandardException.newException(SQLState.LANG_UNION_UNMATCHED_COLUMNS,
> + getOperatorName());
> + }
> +
> + /* We need to recreate resultColumns for this node, since there
> + * may have been 1 or more *'s in the left's SELECT list.
> + */
> + resultColumns = leftResultSet.getResultColumns().copyListAndObjects();
> +
> + /* Create new expressions with the dominant types after verifying
> + * union compatibility between left and right sides.
> + */
> +
resultColumns.setUnionResultExpression(rightResultSet.getResultColumns(),
tableNumber, level, getOperatorName());
> + }
> +
> + /**
> + * Bind the result columns of a table constructor to the types in the
> + * given ResultColumnList. Use when inserting from a table constructor,
> + * and there are nulls in the values clauses.
> + *
> + * @param rcl The ResultColumnList with the types to bind to
> + *
> + * @exception StandardException Thrown on error.
> + */
> + public void bindUntypedNullsToResultColumns(ResultColumnList rcl)
> + throws StandardException
> + {
> + /*
> + ** If the RCL from the parent is null, then
> + ** the types are coming from the union itself.
> + ** So we have to cross check the two child
> + ** rcls.
> + */
> + if (rcl == null)
> + {
> + ResultColumnList lrcl = rightResultSet.getResultColumns();
> + ResultColumnList rrcl = leftResultSet.getResultColumns();
> +
> + leftResultSet.bindUntypedNullsToResultColumns(rrcl);
> + rightResultSet.bindUntypedNullsToResultColumns(lrcl);
> + }
> + else
> + {
> + leftResultSet.bindUntypedNullsToResultColumns(rcl);
> + rightResultSet.bindUntypedNullsToResultColumns(rcl);
> + }
> + }
> +
> + /**
> + * Get the parameter types from the given RowResultSetNode into the
> + * given array of types. If an array position is already filled in,
> + * don't clobber it.
> + *
> + * @param types The array of types to fill in
> + * @param rrsn The RowResultSetNode from which to take the param types
> + *
> + * @return The number of new types found in the RowResultSetNode
> + */
> + int getParamColumnTypes(DataTypeDescriptor[] types, RowResultSetNode
rrsn)
> + {
> + int numTypes = 0;
> +
> + /* Look for columns where we have not found a non-? yet. */
> + for (int i = 0; i < types.length; i++)
> + {
> + if (types[i] == null)
> + {
> + ResultColumn rc =
> + (ResultColumn) rrsn.getResultColumns().elementAt(i);
> + if ( ! (rc.getExpression().isParameterNode()))
> + {
> + types[i] = rc.getExpressionType();
> + numTypes++;
> + }
> + }
> + }
> +
> + return numTypes;
> + }
> +
> + /**
> + * Set the type of each ? parameter in the given RowResultSetNode
> + * according to its ordinal position in the given array of types.
> + *
> + * @param types An array of types containing the proper type for each
> + * ? parameter, by ordinal position.
> + * @param rrsn A RowResultSetNode that could contain ? parameters whose
> + * types need to be set.
> + *
> + * @exception StandardException Thrown on error
> + */
> + void setParamColumnTypes(DataTypeDescriptor[] types, RowResultSetNode
rrsn)
> + throws StandardException
> + {
> + /*
> + ** Look for ? parameters in the result column list
> + ** of each RowResultSetNode
> + */
> + ResultColumnList rrcl = rrsn.getResultColumns();
> + int rrclSize = rrcl.size();
> + for (int index = 0; index < rrclSize; index++)
> + {
> + ResultColumn rc = (ResultColumn) rrcl.elementAt(index);
> +
> + if (rc.getExpression().isParameterNode())
> + {
> + /*
> + ** We found a ? - set its type to the type from the
> + ** type array.
> + */
> + ((ParameterNode) rc.getExpression()).setDescriptor(
> + types[index]);
> + }
> + }
> + }
> +
> + /**
> + * Bind the expressions in the target list. This means binding the
> + * sub-expressions, as well as figuring out what the return type is
> + * for each expression. This is useful for EXISTS subqueries, where we
> + * need to validate the target list before blowing it away and replacing
> + * it with a SELECT true.
> + *
> + * @return Nothing
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public void bindTargetExpressions(FromList fromListParam)
> + throws StandardException
> + {
> + leftResultSet.bindTargetExpressions(fromListParam);
> + rightResultSet.bindTargetExpressions(fromListParam);
> + }
> +
> + /**
> + * Push the order by list down from the cursor node
> + * into its child result set so that the optimizer
> + * has all of the information that it needs to
> + * consider sort avoidance.
> + *
> + * @param orderByList The order by list
> + *
> + * @return Nothing.
> + */
> + void pushOrderByList(OrderByList orderByList)
> + {
> + this.orderByList = orderByList;
> + }
> +
> + /**
> + * Put a ProjectRestrictNode on top of each FromTable in the FromList.
> + * ColumnReferences must continue to point to the same ResultColumn, so
> + * that ResultColumn must percolate up to the new PRN. However,
> + * that ResultColumn will point to a new expression, a VirtualColumnNode,
> + * which points to the FromTable and the ResultColumn that is the source
for
> + * the ColumnReference.
> + * (The new PRN will have the original of the ResultColumnList and
> + * the ResultColumns from that list. The FromTable will get shallow
copies
> + * of the ResultColumnList and its ResultColumns.
ResultColumn.expression
> + * will remain at the FromTable, with the PRN getting a new
> + * VirtualColumnNode for each ResultColumn.expression.)
> + * We then project out the non-referenced columns. If there are no
referenced
> + * columns, then the PRN's ResultColumnList will consist of a single
ResultColumn
> + * whose expression is 1.
> + *
> + * @param numTables Number of tables in the DML Statement
> + * @param gbl The group by list, if any
> + * @param fromList The from list, if any
> + *
> + * @return The generated ProjectRestrictNode atop the original FromTable.
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public ResultSetNode preprocess(int numTables,
> + GroupByList gbl,
> + FromList fromList)
> + throws StandardException
> + {
> + ResultSetNode newTop = this;
> +
> + /* RESOLVE - what does numTables and referencedTableMap mean here? */
> + leftResultSet = leftResultSet.preprocess(numTables, gbl, fromList);
> + rightResultSet = rightResultSet.preprocess(numTables, gbl, fromList);
> +
> + /* Build the referenced table map (left || right) */
> + referencedTableMap = (JBitSet)
leftResultSet.getReferencedTableMap().clone();
> + referencedTableMap.or((JBitSet) rightResultSet.getReferencedTableMap());
> +
> + /* If this is a UNION without an all and we have
> + * an order by then we can consider eliminating the sort for the
> + * order by. All of the columns in the order by list must
> + * be ascending in order to do this. There are 2 cases:
> + * o The order by list is an in order prefix of the columns
> + * in the select list. In this case the output of the
> + * sort from the distinct will be in the right order
> + * so we simply eliminate the order by list.
> + * o The order by list is a subset of the columns in the
> + * the select list. In this case we need to reorder the
> + * columns in the select list so that the ordering columns
> + * are an in order prefix of the select list and put a PRN
> + * above the select so that the shape of the result set
> + * is as expected.
> + */
> + if ((! all) && orderByList != null && orderByList.allAscending())
> + {
> + /* Order by list currently restricted to columns in select
> + * list, so we will always eliminate the order by here.
> + */
> + if (orderByList.isInOrderPrefix(resultColumns))
> + {
> + orderByList = null;
> + }
> + /* RESOLVE - We currently only eliminate the order by if it is
> + * a prefix of the select list. We do not currently do the
> + * elimination if the order by is not a prefix because the code
> + * doesn't work. The problem has something to do with the
> + * fact that we generate additional nodes between the union
> + * and the PRN (for reordering that we would generate here)
> + * when modifying the access paths. VCNs under the PRN can be
> + * seen as correlated since their source resultset is the Union
> + * which is no longer the result set directly under them. This
> + * causes the wrong code to get generated. (jerry - 11/3/98)
> + * (bug 59)
> + */
> + }
> +
> + return newTop;
> + }
> +
> + /**
> + * Ensure that the top of the RSN tree has a PredicateList.
> + *
> + * @param numTables The number of tables in the query.
> + * @return ResultSetNode A RSN tree with a node which has a PredicateList
on top.
> + *
> + * @exception StandardException Thrown on error
> + */
> + public ResultSetNode ensurePredicateList(int numTables)
> + throws StandardException
> + {
> + return genProjectRestrict(numTables);
> + }
> +
> + /**
> + * Verify that a SELECT * is valid for this type of subquery.
> + *
> + * @param outerFromList The FromList from the outer query block(s)
> + * @param subqueryType The subquery type
> + *
> + * @return None
> + *
> + * @exception StandardException Thrown on error
> + */
> + public void verifySelectStarSubquery(FromList outerFromList, int
subqueryType)
> + throws StandardException
> + {
> + /* Check both sides - SELECT * is not valid on either side */
> + leftResultSet.verifySelectStarSubquery(outerFromList, subqueryType);
> + rightResultSet.verifySelectStarSubquery(outerFromList, subqueryType);
> + }
> +
> + /**
> + * Determine whether or not the specified name is an exposed name in
> + * the current query block.
> + *
> + * @param name The specified name to search for as an exposed name.
> + * @param schemaName Schema name, if non-null.
> + * @param exactMatch Whether or not we need an exact match on specified
schema and table
> + * names or match on table id.
> + *
> + * @return The FromTable, if any, with the exposed name.
> + *
> + * @exception StandardException Thrown on error
> + */
> + protected FromTable getFromTableByName(String name, String schemaName,
boolean exactMatch)
> + throws StandardException
> + {
> + /* We search both sides for a TableOperatorNode (join nodes)
> + * but only the left side for a UnionNode.
> + */
> + return leftResultSet.getFromTableByName(name, schemaName, exactMatch);
> + }
> +
> + /**
> + * Set the result column for the subquery to a boolean true,
> + * Useful for transformations such as
> + * changing:
> + * where exists (select ... from ...)
> + * to:
> + * where (select true from ...)
> + *
> + * NOTE: No transformation is performed if the ResultColumn.expression is
> + * already the correct boolean constant.
> + *
> + * @param onlyConvertAlls Boolean, whether or not to just convert *'s
> + *
> + * @return Nothing.
> + *
> + * @exception StandardException Thrown on error
> + */
> + public void setResultToBooleanTrueNode(boolean onlyConvertAlls)
> + throws StandardException
> + {
> + super.setResultToBooleanTrueNode(onlyConvertAlls);
> + leftResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
> + rightResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
> + }
> +
> + /**
> + * This ResultSet is the source for an Insert. The target RCL
> + * is in a different order and/or a superset of this RCL. In most cases
> + * we will reorder and/or add defaults to the current RCL so that is
> + * matches the target RCL. Those RSNs whose generate() method does
> + * not handle projects will insert a PRN, with a new RCL which matches
> + * the target RCL, above the current RSN.
> + * NOTE - The new or enhanced RCL will be fully bound.
> + *
> + * @param numTargetColumns # of columns in target RCL
> + * @param colMap[] int array representation of correspondence between
> + * RCLs - colmap[i] = -1 -> missing in current RCL
> + * colmap[i] = j -> targetRCL(i) <-> thisRCL(j+1)
> + * @param dataDictionary DataDictionary to use
> + * @param targetTD TableDescriptor for target if the target is not a VTI,
null if a VTI
> + * @param targetVTI Target description if it is a VTI, null
if not a VTI
> + *
> + * @return ResultSetNode The new top of the tree
> + *
> + * @exception StandardException Thrown on error
> + */
> + public ResultSetNode enhanceRCLForInsert(int numTargetColumns, int[]
colMap,
> + DataDictionary dataDictionary,
> + TableDescriptor targetTD,
> + FromVTI targetVTI)
> + throws StandardException
> + {
> + // our newResultCols are put into the bound form straight away.
> + ResultColumnList newResultCols =
> + (ResultColumnList) getNodeFactory().getNode(
> + C_NodeTypes.RESULT_COLUMN_LIST,
> + getContextManager());
> + int numResultSetColumns = resultColumns.size();
> +
> + /* Create a massaged version of the source RCL.
> + * (Much simpler to build new list and then assign to source,
> + * rather than massage the source list in place.)
> + */
> + for (int index = 0; index < numTargetColumns; index++)
> + {
> + ResultColumn newResultColumn;
> + ResultColumn oldResultColumn;
> + ColumnReference newColumnReference;
> +
> + if (colMap[index] != -1)
> + {
> + // getResultColumn uses 1-based positioning, so offset the colMap entry
appropriately
> + oldResultColumn = resultColumns.getResultColumn(colMap[index]+1);
> +
> + newColumnReference = (ColumnReference) getNodeFactory().getNode(
> + C_NodeTypes.COLUMN_REFERENCE,
> + oldResultColumn.getName(),
> + null,
> + getContextManager());
> + /* The ColumnReference points to the source of the value */
> + newColumnReference.setSource(oldResultColumn);
> + // colMap entry is 0-based, columnId is 1-based.
> + newColumnReference.setType(oldResultColumn.getExpressionType());
> +
> + // Source of an insert, so nesting levels must be 0
> + newColumnReference.setNestingLevel(0);
> + newColumnReference.setSourceLevel(0);
> +
> + // because the insert already copied the target table's
> + // column descriptors into the result, we grab it from there.
> + // alternatively, we could do what the else clause does,
> + // and look it up in the DD again.
> + newResultColumn = (ResultColumn) getNodeFactory().getNode(
> + C_NodeTypes.RESULT_COLUMN,
> + oldResultColumn.getType(),
> + newColumnReference,
> + getContextManager());
> + }
> + else
> + {
> + newResultColumn = genNewRCForInsert(targetTD, targetVTI, index + 1,
dataDictionary);
> + }
> +
> + newResultCols.addResultColumn(newResultColumn);
> + }
> +
> + /* The generated ProjectRestrictNode now has the ResultColumnList
> + * in the order that the InsertNode expects.
> + * NOTE: This code here is an exception to several "rules":
> + * o This is the only ProjectRestrictNode that is currently
> + * generated outside of preprocess().
> + * o The UnionNode is the only node which is not at the
> + * top of the query tree which has ColumnReferences under
> + * its ResultColumnList prior to expression push down.
> + */
> + return (ResultSetNode) getNodeFactory().getNode(
> + C_NodeTypes.PROJECT_RESTRICT_NODE,
> + this,
> + newResultCols,
> + null,
> + null,
> + null,
> + null,
> + tableProperties,
> + getContextManager());
> + }
> +
> + /**
> + * Evaluate whether or not the subquery in a FromSubquery is flattenable.
> + * Currently, a FSqry is flattenable if all of the following are true:
> + * o Subquery is a SelectNode. (ie, not a RowResultSetNode or a
UnionNode)
> + * o It contains no top level subqueries. (RESOLVE - we can relax this)
> + * o It does not contain a group by or having clause
> + * o It does not contain aggregates.
> + *
> + * @param fromList The outer from list
> + *
> + * @return boolean Whether or not the FromSubquery is flattenable.
> + */
> + public boolean flattenableInFromSubquery(FromList fromList)
> + {
> + /* Unions in FromSubquerys are not flattenable. */
> + return false;
> + }
> +
> + /**
> + * Return whether or not to materialize this ResultSet tree.
> + *
> + * @return Whether or not to materialize this ResultSet tree.
> + * would return valid results.
> + *
> + * @exception StandardException Thrown on error
> + */
> + public boolean performMaterialization(JBitSet outerTables)
> + throws StandardException
> + {
> + // RESOLVE - just say no to materialization right now - should be a cost
based decision
> + return false;
> +
> + /* Actual materialization, if appropriate, will be placed by our parent
PRN.
> + * This is because PRN might have a join condition to apply.
(Materialization
> + * can only occur before that.
> + */
> + //return true;
> + }
> +
> + /**
> + * @return the operator name: "UNION", "INTERSECT", or "EXCEPT"
> + */
> + abstract String getOperatorName();
> +}
> Index: java/engine/org/apache/derby/impl/sql/compile/sqlgrammar.jj
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/sqlgrammar.jj (revision
111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/sqlgrammar.jj (working
copy)
> @@ -175,6 +175,15 @@
> // Define for UTF8 max
> private static final int MAX_UTF8_LENGTH = 65535;
>
> + // Constants for set operator types
> + private static final int NO_SET_OP = 0;
> + private static final int UNION_OP = 1;
> + private static final int UNION_ALL_OP = 2;
> + private static final int EXCEPT_OP = 3;
> + private static final int EXCEPT_ALL_OP = 4;
> + private static final int INTERSECT_OP = 5;
> + private static final int INTERSECT_ALL_OP = 6;
> +
> private StringSlicer stringSlicer;
> private Object[] paramDefaults;
> private String statementSQLText;
> @@ -809,6 +818,74 @@
> return retval;
> }
>
> + /**
> + * Make a result set node for UNION, EXCEPT, INTERSECT, or no set
operation.
> + *
> + * @param leftSide null if opType == NO_SET_OP
> + * @param opType NO_SET_OP, UNION_OP, UNION_ALL_OP, EXCEPT_OP,
EXCEPT_ALL_OP, INTERSECT_OP, or INTERSECT_ALL_OP
> + * @param rightSide
> + *
> + * @return a ResultSetNode
> + */
> + private ResultSetNode makeSetOpNode( ResultSetNode leftSide, int
operatorType, ResultSetNode rightSide)
> + throws StandardException
> + {
> + int nodeType = 0;
> + Boolean all = null;
> +
> + switch( operatorType)
> + {
> + case NO_SET_OP:
> + return rightSide;
> +
> + case UNION_OP:
> + nodeType = C_NodeTypes.UNION_NODE;
> + all = Boolean.FALSE;
> + break;
> +
> + case UNION_ALL_OP:
> + nodeType = C_NodeTypes.UNION_NODE;
> + all = Boolean.TRUE;
> + break;
> +
> + case EXCEPT_OP:
> + nodeType = C_NodeTypes.EXCEPT_NODE;
> + all = Boolean.FALSE;
> + break;
> +
> + case EXCEPT_ALL_OP:
> + nodeType = C_NodeTypes.EXCEPT_NODE;
> + all = Boolean.TRUE;
> + break;
> +
> + case INTERSECT_OP:
> + nodeType = C_NodeTypes.INTERSECT_NODE;
> + all = Boolean.FALSE;
> + break;
> +
> + case INTERSECT_ALL_OP:
> + nodeType = C_NodeTypes.INTERSECT_NODE;
> + all = Boolean.TRUE;
> + break;
> +
> + default:
> + if (SanityManager.DEBUG)
> + {
> + SanityManager.THROWASSERT( "Invalid set operator type: "
+ operatorType);
> + }
> + return null;
> + }
> +
> + return (ResultSetNode) nodeFactory.getNode(
> + nodeType,
> + leftSide,
> + rightSide,
> + all,
> + Boolean.FALSE,
> + null,
> + getContextManager());
> + } // end of makeSetOpNode
> +
> /**
> * Determine whether the next sequence of tokens can be the beginning
> * of a remainingPredicate() rule.
> @@ -2683,7 +2760,7 @@
> OrderByList orderCols = null;
> }
> {
> - queryExpression = queryExpression(null, Boolean.FALSE)
> + queryExpression = queryExpression(null, NO_SET_OP)
> [ orderCols = orderByClause() ]
> [ <FOR> forUpdateState = forUpdateClause(updateColumns) ]
> [ isolationLevel = atIsolationLevel() ]
> @@ -4129,24 +4206,37 @@
>
> /*
> * <A NAME="queryExpression">queryExpression</A>
> + *
> + * We have to be carefull to get the associativity correct. According to
the SQL spec
> + * <non-join query expression> ::=
> + * <non-join query term>
> + * | <query expression body> UNION [ ALL ] <query term>
> + * | <query expression body> EXCEPT [ ALL ] <query term>
> + * Meaning that
> + * t1 UNION ALL t2 UNION t3
> + * is equivalent to
> + * (t1 UNION ALL t2) UNION t3
> + * However recursive descent parsers want recursion to be on the right,
so this kind of associativity is unnatural
> + * for our parser. The queryExpression method must know whether it is
being called as the right hand side of a
> + * set operator to produce a query tree with the correct associativity.
> */
> ResultSetNode
> -queryExpression(ResultSetNode leftSide, Boolean unionAll) throws
StandardException :
> +queryExpression(ResultSetNode leftSide, int operatorType) throws
StandardException :
> {
> ResultSetNode term;
> }
> {
> - term = nonJoinQueryTerm(leftSide, unionAll) [ term = union(term) ]
> + term = nonJoinQueryTerm(leftSide, operatorType) [ term =
unionOrExcept(term) ]
> {
> return term;
> }
> }
>
> /*
> - * <A NAME="union">union</A>
> + * <A NAME="unionOrExcept">unionOrExcept</A>
> */
> ResultSetNode
> -union(ResultSetNode term) throws StandardException :
> +unionOrExcept(ResultSetNode term) throws StandardException :
> {
> ResultSetNode expression;
> Token tok = null;
> @@ -4154,46 +4244,61 @@
> {
> <UNION> [ tok = <ALL> ] expression =
> queryExpression(term,
> - (tok != null) ? Boolean.TRUE : Boolean.FALSE)
> + (tok != null) ? UNION_ALL_OP : UNION_OP)
> {
> return expression;
> }
> +|
> + <EXCEPT> [ tok = <ALL> ] expression =
> + queryExpression(term,
> + (tok != null) ? EXCEPT_ALL_OP : EXCEPT_OP)
> + {
> + return expression;
> + }
> }
>
>
> /*
> * <A NAME="nonJoinQueryTerm">nonJoinQueryTerm</A>
> + *
> + * Be careful with the associativity of INTERSECT. According to the SQL
spec
> + * t1 INTERSECT t2 INTERSECT ALL t3
> + * is equivalent to
> + * (t1 INTERSECT t2) INTERSECT ALL t3
> + * which is not the same as
> + * t1 INTERSECT (t2 INTERSECT ALL t3)
> + * See the comment on queryExpression.
> */
> ResultSetNode
> -nonJoinQueryTerm(ResultSetNode leftSide, Boolean unionAll) throws
StandardException :
> +nonJoinQueryTerm(ResultSetNode leftSide, int operatorType) throws
StandardException :
> {
> ResultSetNode term;
> }
> {
> - /*
> - ** Omitted "intersect".
> - */
> - term = nonJoinQueryPrimary()
> + term = nonJoinQueryPrimary() [ term = intersect( term) ]
> {
> - if (leftSide != null)
> - {
> - return (ResultSetNode) nodeFactory.getNode(
> - C_NodeTypes.UNION_NODE,
> - leftSide,
> - term,
> - unionAll,
> - Boolean.FALSE,
> - null,
> - getContextManager());
> - }
> - else
> - {
> - return term;
> - }
> + return makeSetOpNode( leftSide, operatorType, term);
> }
> }
>
> /*
> + * <A NAME="intersect">intersect</A>
> + */
> +ResultSetNode
> +intersect(ResultSetNode term) throws StandardException :
> +{
> + ResultSetNode expression;
> + Token tok = null;
> +}
> +{
> + <INTERSECT> [ tok = <ALL> ] expression =
> + nonJoinQueryTerm(term, (tok != null) ? INTERSECT_ALL_OP : INTERSECT_OP)
> + {
> + return expression;
> + }
> +}
> +
> +/*
> * <A NAME="nonJoinQueryPrimary">nonJoinQueryPrimary</A>
> */
> ResultSetNode
> @@ -4207,7 +4312,7 @@
> return primary;
> }
> |
> - <LEFT_PAREN> primary = queryExpression(null, Boolean.FALSE)
<RIGHT_PAREN>
> + <LEFT_PAREN> primary = queryExpression(null, NO_SET_OP) <RIGHT_PAREN>
> {
> return primary;
> }
> @@ -6750,7 +6855,7 @@
> <LEFT_PAREN> columnList = insertColumnList() <RIGHT_PAREN>
> ]
> [ targetProperties = propertyList() ]
> - queryExpression = queryExpression(null, Boolean.FALSE)
> + queryExpression = queryExpression(null, NO_SET_OP)
> {
> return (QueryTreeNode) nodeFactory.getNode(
> C_NodeTypes.INSERT_NODE,
> @@ -6997,7 +7102,7 @@
> SubqueryNode subqueryNode;
> }
> {
> - queryExpression = queryExpression(null, Boolean.FALSE)
> + queryExpression = queryExpression(null, NO_SET_OP)
> {
> subqueryNode = (SubqueryNode) nodeFactory.getNode(
> C_NodeTypes.SUBQUERY_NODE,
> @@ -8778,7 +8883,7 @@
> {
> <VIEW> tableName = qualifiedName(DB2Limit.DB2_MAX_IDENTIFIER_LENGTH128)
> [ <LEFT_PAREN> resultColumns = viewColumnList() <RIGHT_PAREN> ]
> - <AS> queryExpression = queryExpression(null, Boolean.FALSE)
> + <AS> queryExpression = queryExpression(null, NO_SET_OP)
> {
> checkOptionType = ViewDescriptor.NO_CHECK_OPTION;
> endToken = getToken(0);
> @@ -9662,7 +9767,7 @@
> <EXECUTE> <STATEMENT> stmtName =
qualifiedName(DB2Limit.DB2_MAX_IDENTIFIER_LENGTH128)
> [ LOOKAHEAD( { getToken(1).kind == USING } )
> usingToken = <USING> usingClause =
> - queryExpression(null, Boolean.FALSE) ]
> + queryExpression(null, NO_SET_OP) ]
> {
> endToken = getToken(0);
>
> Index:
java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
> ===================================================================
> ---
java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
(revision 0)
> +++
java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
(revision 0)
> @@ -0,0 +1,304 @@
> +/*
> +
> + Derby - Class org.apache.derby.impl.sql.compile.IntersectNode
> +
> + Copyright 1997, 2004 The Apache Software Foundation or its licensors,
as applicable.
> +
> + Licensed under the Apache License, Version 2.0 (the "License");
> + you may not use this file except in compliance with the License.
> + You may obtain a copy of the License at
> +
> + http://www.apache.org/licenses/LICENSE-2.0
> +
> + Unless required by applicable law or agreed to in writing, software
> + distributed under the License is distributed on an "AS IS" BASIS,
> + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
> + See the License for the specific language governing permissions and
> + limitations under the License.
> +
> + */
> +
> +package org.apache.derby.impl.sql.compile;
> +
> +import org.apache.derby.iapi.reference.ClassName;
> +
> +import org.apache.derby.iapi.services.sanity.SanityManager;
> +import org.apache.derby.iapi.services.classfile.VMOpcode;
> +import org.apache.derby.iapi.services.compiler.MethodBuilder;
> +import org.apache.derby.iapi.services.context.ContextManager;
> +
> +import org.apache.derby.iapi.error.StandardException;
> +
> +import org.apache.derby.iapi.sql.compile.NodeFactory;
> +import org.apache.derby.iapi.sql.compile.Optimizable;
> +import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
> +import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
> +import org.apache.derby.iapi.sql.compile.Optimizer;
> +import org.apache.derby.iapi.sql.compile.CostEstimate;
> +import org.apache.derby.iapi.sql.compile.RowOrdering;
> +import org.apache.derby.iapi.sql.compile.C_NodeTypes;
> +
> +import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
> +
> +import org.apache.derby.iapi.reference.SQLState;
> +
> +import org.apache.derby.iapi.types.DataTypeDescriptor;
> +
> +import org.apache.derby.iapi.util.JBitSet;
> +import org.apache.derby.iapi.util.ReuseFactory;
> +
> +import java.sql.Types;
> +
> +/**
> + * A IntersectOrExceptNode represents an INTERSECT or EXCEPT DML
statement.
> + *
> + * @author Jack Klebanoff
> + */
> +
> +public abstract class IntersectOrExceptNode extends SetOperatorNode
> +{
> + /* Currently we implement INTERSECT and EXCEPT by rewriting
> + * t1 (INTERSECT|EXCEPT) [ALL] t2
> + * as (roughly)
> + * setOpProjectRestrict( opType, all, (select * from t1 order by
1,2,...n), (select * from t2 ORDER BY 1,2,...,n))
> + * where n is the number of columns in t1 (which must be the same as
the number of columns in t2),
> + * and opType is INTERSECT, or EXCEPT.
> + *
> + * The setOpProjectRestrict result set simultaneously scans through
its two ordered inputs and
> + * performs the intersect or except.
> + *
> + * There are other query plans that may be more efficient, depending
on the sizes. One plan is
> + * to make a hash table from one of the input tables and then look up
each row of the other input
> + * table in the hash table. However, we have not yet implemented
spilling to disk in the
> + * BackingStoreHashtable class: currently the whole hash table is in
RAM. If we were to use it
> + * we would blow up on large input tables.
> + */
> + private CostEstimate leftOrderByCostEstimate;
> + private CostEstimate rightOrderByCostEstimate;
> +
> + /* Only optimize it once */
> + /* Only call addNewNodes() once */
> + private boolean addNewNodesCalled;
> +
> + /**
> + * Initializer for a SetOperatorNode.
> + *
> + * @param leftResult The ResultSetNode on the left side of this union
> + * @param rightResult The ResultSetNode on the right side of this union
> + * @param all Whether or not this is an ALL.
> + * @param tableConstructor Whether or not this is from a table
constructor.
> + * @param tableProperties Properties list associated with the table
> + *
> + * @exception StandardException Thrown on error
> + */
> +
> + public void init( Object leftResult,
> + Object rightResult,
> + Object all,
> + Object tableConstructor,
> + Object tableProperties)
> + throws StandardException
> + {
> + super.init( leftResult, rightResult, all, tableConstructor,
tableProperties);
> + }
> +
> + /**
> + * @see org.apache.derby.iapi.sql.compile.Optimizable#estimateCost
> + */
> + public CostEstimate estimateCost( OptimizablePredicateList predList,
> + ConglomerateDescriptor cd,
> + CostEstimate outerCost,
> + Optimizer optimizer,
> + RowOrdering rowOrdering)
> + throws StandardException
> + {
> + getGeneratedNodeCostEstimates();
> + estimateOrderByCost( leftOrderByCostEstimate, leftResultSet);
> + estimateOrderByCost( rightOrderByCostEstimate, rightResultSet);
> +
> + CostEstimate costEstimate = getCostEstimate(optimizer);
> + // The cost is the sum of the two child costs plus the cost of
sorting the union.
> + costEstimate.setCost( leftOrderByCostEstimate.getEstimatedCost()
+ rightOrderByCostEstimate.getEstimatedCost(),
> + getRowCountEstimate(
leftOrderByCostEstimate.rowCount(),
> +
rightOrderByCostEstimate.rowCount()),
> + getSingleScanRowCountEstimate(
leftOrderByCostEstimate.singleScanRowCount(),
> +
rightOrderByCostEstimate.singleScanRowCount()));
> + // RESOLVE: We should add in the cost of the generated
project/restrict, but this is not high.
> +
> + return costEstimate;
> + } // End of estimateCost
> +
> + private void getGeneratedNodeCostEstimates()
> + throws StandardException
> + {
> + if( leftOrderByCostEstimate == null)
> + leftOrderByCostEstimate = getNewCostEstimate();
> + if( rightOrderByCostEstimate == null)
> + rightOrderByCostEstimate = getNewCostEstimate();
> + }
> +
> + private void estimateOrderByCost( CostEstimate costEstimate,
ResultSetNode rsn)
> + throws StandardException
> + {
> + CostEstimate childCost = rsn.getCostEstimate();
> + costEstimate.setCost( childCost.getEstimatedCost(),
> + childCost.rowCount(),
> + childCost.singleScanRowCount());
> + // RESOLVE: We should add in the cost of the sort, which may be
quite high.
> + // The cost of the sort is C*(leftCount +
rightCount)*log(leftCount + rightCount)
> + // I do not know the correct value for C. Sort costs are also
unresolved problems
> + // in DistinctNode and GroupByNode.
> + } // end of estimateOrderByCost
> +
> + /**
> + * @see Optimizable#modifyAccessPath
> + *
> + * @exception StandardException Thrown on error
> + */
> + public Optimizable modifyAccessPath(JBitSet outerTables) throws
StandardException
> + {
> + Optimizable retOptimizable;
> + retOptimizable = super.modifyAccessPath(outerTables);
> +
> + /* We only want call addNewNodes() once */
> + if (addNewNodesCalled)
> + {
> + return retOptimizable;
> + }
> + return (Optimizable) addNewNodes();
> + }
> +
> + /**
> + * @see ResultSetNode#modifyAccessPaths
> + *
> + * @exception StandardException Thrown on error
> + */
> + public ResultSetNode modifyAccessPaths() throws StandardException
> + {
> + ResultSetNode retRSN;
> + retRSN = super.modifyAccessPaths();
> +
> + /* We only want call addNewNodes() once */
> + if (addNewNodesCalled)
> + {
> + return retRSN;
> + }
> + return addNewNodes();
> + }
> +
> + /**
> + * Add any new ResultSetNodes that are necessary to the tree.
> + * We wait until after optimization to do this in order to
> + * make it easier on the optimizer.
> + *
> + * @return (Potentially new) head of the ResultSetNode tree.
> + *
> + * @exception StandardException Thrown on error
> + */
> + private ResultSetNode addNewNodes()
> + throws StandardException
> + {
> + /* Only call addNewNodes() once */
> + if (addNewNodesCalled)
> + {
> + return this;
> + }
> +
> + addNewNodesCalled = true;
> +
> + NodeFactory nf = getNodeFactory();
> + ContextManager cm = getContextManager();
> +
> + getGeneratedNodeCostEstimates();
> +
> + leftResultSet = generateOrderBy( leftResultSet,
leftOrderByCostEstimate);
> + rightResultSet = generateOrderBy( rightResultSet,
rightOrderByCostEstimate);
> + return this;
> + } // end of addNewNodes
> +
> + private ResultSetNode generateOrderBy( ResultSetNode source,
CostEstimate generatedOrderByCostEstimate)
> + throws StandardException
> + {
> + int columnCount = source.getResultColumns().size();
> + ContextManager cm = getContextManager();
> + NodeFactory nf = getNodeFactory();
> + OrderByList orderByList = (OrderByList) nf.getNode(
C_NodeTypes.ORDER_BY_LIST, cm);
> + for( int i = 1; i <= columnCount; i++)
> + {
> + OrderByColumn orderByColumn = (OrderByColumn) nf.getNode(
C_NodeTypes.ORDER_BY_COLUMN,
> +
ReuseFactory.getInteger( i),
> +
cm);
> + orderByList.addOrderByColumn( orderByColumn);
> + }
> + orderByList.bindOrderByColumns( source);
> +
> + OrderByNode generatedOrderBy = (OrderByNode)
> + getNodeFactory().getNode( C_NodeTypes.ORDER_BY_NODE,
> + source,
> + orderByList,
> + tableProperties,
> + getContextManager());
> + ResultColumnList sourceRCL = source.getResultColumns();
> + ResultColumnList orderByRCL = sourceRCL.copyListAndObjects();
> + orderByRCL.genVirtualColumnNodes( source, sourceRCL);
> + generatedOrderBy.setResultColumns( orderByRCL);
> + generatedOrderBy.assignCostEstimate(
generatedOrderByCostEstimate);
> +
> + return generatedOrderBy;
> + } // end of generateOrderBy
> +
> + /**
> + * Generate the code.
> + *
> + * @exception StandardException Thrown on error
> + */
> + public void generate( ActivationClassBuilder acb,
> + MethodBuilder mb)
> + throws StandardException
> + {
> +
> + /* Get the next ResultSet #, so that we can number this ResultSetNode,
its
> + * ResultColumnList and ResultSet.
> + */
> + assignResultSetNumber();
> +
> + // build up the tree.
> +
> + /* Generate the SetOpResultSet. Arguments:
> + * 1) expression for left child ResultSet
> + * 2) expression for right child ResultSet
> + * 3) activation
> + * 4) resultSetNumber
> + * 5) estimated row count
> + * 6) estimated cost
> + * 7) opType
> + * 8) all
> + * 9) close method
> + */
> +
> + acb.pushGetResultSetFactoryExpression(mb); // instance for
getUnionResultSet
> +
> + getLeftResultSet().generate( acb, mb);
> + getRightResultSet().generate( acb, mb);
> +
> + acb.pushThisAsActivation(mb);
> + mb.push(resultSetNumber);
> + mb.push( costEstimate.getEstimatedRowCount());
> + mb.push( costEstimate.getEstimatedCost());
> + mb.push( getOpType());
> + mb.push( all);
> + closeMethodArgument(acb, mb);
> +
> + mb.callMethod(VMOpcode.INVOKEINTERFACE,
> + (String) null,
> + "getSetOpProjectRestrictResultSet",
> + ClassName.NoPutResultSet, 9);
> + } // end of generate
> +
> + abstract int getOpType();
> + public static final int INTERSECT_OP = 1;
> + public static final int EXCEPT_OP = 2;
> +
> + abstract double getRowCountEstimate( double leftRowCount, double
rightRowCount);
> + abstract double getSingleScanRowCountEstimate( double
leftSingleScanRowCount, double rightSingleScanRowCount);
> +}
> Index:
java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
(revision 111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
(working copy)
> @@ -376,8 +376,8 @@
> ** Parameters not allowed in select list of either side of union,
> ** except when the union is for a table constructor.
> */
> - if ( ! (this instanceof UnionNode) ||
> - ! ((UnionNode) this).tableConstructor())
> + if ( ! (this instanceof SetOperatorNode) ||
> + ! ((SetOperatorNode) this).tableConstructor())
> {
> leftResultSet.rejectParameters();
> rightResultSet.rejectParameters();
> Index: java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java
(revision 111283)
> +++ java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java
(working copy)
> @@ -2025,7 +2025,7 @@
> }
>
> /**
> - * Set up the result expressions for a UNION:
> + * Set up the result expressions for a UNION, INTERSECT, or EXCEPT:
> * o Verify union type compatiblity
> * o Get dominant type for result (type + max length + nullability)
> * o Create a new ColumnReference with dominant type and name of from
this
> @@ -2038,14 +2038,16 @@
> * @param otherRCL RCL from other side of the UNION.
> * @param tableNumber The tableNumber for the UNION.
> * @param level The nesting level for the UNION.
> + * @param operatorName "UNION", "INTERSECT", or "EXCEPT"
> *
> * @return Nothing.
> *
> * @exception StandardException Thrown on error
> */
> public void setUnionResultExpression(ResultColumnList otherRCL,
> - int tableNumber,
> - int level)
> + int tableNumber,
> + int level,
> + String operatorName)
> throws StandardException
> {
> TableName dummyTN;
> @@ -2116,8 +2118,9 @@
> !otherExpr.getTypeCompiler().storable(thisTypeId, cf))
> {
> throw StandardException.newException(SQLState.LANG_NOT_UNION_COMPATIBLE,
> - thisTypeId.getSQLTypeName(),
> - otherTypeId.getSQLTypeName() );
> +
thisTypeId.getSQLTypeName(),
> +
otherTypeId.getSQLTypeName(),
> + operatorName);
> }
>
> DataTypeDescriptor resultType =
thisExpr.getTypeServices().getDominantType(
> Index: java/engine/org/apache/derby/impl/sql/build.xml
> ===================================================================
> --- java/engine/org/apache/derby/impl/sql/build.xml (revision 111283)
> +++ java/engine/org/apache/derby/impl/sql/build.xml (working copy)
> @@ -16,6 +16,8 @@
> <property file="${properties.dir}/extrapath.properties"/>
> <property file="${properties.dir}/compilepath.properties"/>
>
> + <property name="cur.dir" value="impl/sql"/>
> +
> <!-- Targets -->
> <target name="parser">
> <ant antfile="${src.dir}/build.xml" target="genParser">
> @@ -42,9 +44,9 @@
> <classpath>
> <pathelement path="${compile.classpath}"/>
> </classpath>
> - <include name="${derby.dir}/impl/sql/**"/>
> + <include name="${derby.dir}/${cur.dir}/**"/>
> </javac>
> - <copy file="catalog/metadata_net.properties"
tofile="${out.dir}/org/apache/derby/impl/sql/catalog/metadata_net.properties
"/>
> + <copy
file="${derby.engine.src.dir}/${derby.dir}/${cur.dir}/catalog/metadata_net.p
roperties"
tofile="${out.dir}/org/apache/derby/impl/sql/catalog/metadata_net.properties
"/>
> </target>
>
> </project>
> Index:
java/engine/org/apache/derby/impl/sql/execute/SetOpProjectRestrictResultSet.
java
> ===================================================================
> ---
java/engine/org/apache/derby/impl/sql/execute/SetOpProjectRestrictResultSet.
java (revision 0)
> +++
java/engine/org/apache/derby/impl/sql/execute/SetOpProjectRestrictResultSet.
java (revision 0)
> @@ -0,0 +1,274 @@
> +/*
> +
> + Derby - Class
org.apache.derby.impl.sql.execute.SetOpProjectRestrictResultSet
> +
> + Copyright 1997, 2004 The Apache Software Foundation or its licensors,
as applicable.
> +
> + Licensed under the Apache License, Version 2.0 (the "License");
> + you may not use this file except in compliance with the License.
> + You may obtain a copy of the License at
> +
> + http://www.apache.org/licenses/LICENSE-2.0
> +
> + Unless required by applicable law or agreed to in writing, software
> + distributed under the License is distributed on an "AS IS" BASIS,
> + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
> + See the License for the specific language governing permissions and
> + limitations under the License.
> +
> + */
> +
> +package org.apache.derby.impl.sql.execute;
> +
> +import org.apache.derby.iapi.error.StandardException;
> +
> +import org.apache.derby.iapi.services.loader.GeneratedMethod;
> +import org.apache.derby.iapi.services.sanity.SanityManager;
> +
> +import org.apache.derby.iapi.sql.Activation;
> +import org.apache.derby.iapi.sql.ResultDescription;
> +
> +import org.apache.derby.iapi.sql.execute.CursorResultSet;
> +import org.apache.derby.iapi.sql.execute.ExecRow;
> +import org.apache.derby.iapi.sql.execute.NoPutResultSet;
> +
> +import org.apache.derby.iapi.types.DataValueDescriptor;
> +import org.apache.derby.iapi.types.Orderable;
> +import org.apache.derby.iapi.types.RowLocation;
> +
> +import org.apache.derby.impl.sql.compile.IntersectOrExceptNode;
> +
> +/**
> + * Takes the result set produced by an ordered UNION ALL of two tagged
result sets and produces
> + * the INTERSECT or EXCEPT of the two input result sets. This also
projects out the tag, the last column
> + * of the input rows.
> + */
> +public class SetOpProjectRestrictResultSet extends NoPutResultSetImpl
> + implements CursorResultSet
> +{
> + private final NoPutResultSet leftSource;
> + private final NoPutResultSet rightSource;
> + private final GeneratedMethod closeCleanup;
> + private final Activation activation;
> + private final int opType;
> + private final boolean all;
> + private final int resultSetNumber;
> + private DataValueDescriptor[] prevCols; /* Used to remove duplicates
in the EXCEPT DISTINCT case.
> + * It is equal to the
previously output columns.
> + */
> + private int rightDuplicateCount; // Number of duplicates of the
current row from the right input
> + private ExecRow leftInputRow;
> + private ExecRow rightInputRow;
> +
> + SetOpProjectRestrictResultSet( NoPutResultSet leftSource,
> + NoPutResultSet rightSource,
> + Activation activation,
> + int resultSetNumber,
> + long optimizerEstimatedRowCount,
> + double optimizerEstimatedCost,
> + int opType,
> + boolean all,
> + GeneratedMethod closeCleanup)
> + {
> + super(activation, resultSetNumber,
> + optimizerEstimatedRowCount, optimizerEstimatedCost);
> + this.leftSource = leftSource;
> + this.rightSource = rightSource;
> + this.activation = activation;
> + this.resultSetNumber = resultSetNumber;
> + this.opType = opType;
> + this.all = all;
> + this.closeCleanup = closeCleanup;
> + constructorTime += getElapsedMillis(beginTime);
> + }
> +
> + /**
> + * open the first source.
> + * @exception StandardException thrown on failure
> + */
> + public void openCore() throws StandardException
> + {
> + beginTime = getCurrentTimeMillis();
> + if (SanityManager.DEBUG)
> + SanityManager.ASSERT( ! isOpen, "SetOpProjectRestrictResultSet
already open");
> +
> + isOpen = true;
> + leftSource.openCore();
> + rightSource.openCore();
> + rightInputRow = rightSource.getNextRowCore();
> + numOpens++;
> +
> + openTime += getElapsedMillis(beginTime);
> + } // end of openCore
> +
> + /**
> + * @return the next row of the intersect or except, null if there is
none
> + * @exception StandardException thrown on failure
> + */
> + public ExecRow getNextRowCore() throws StandardException
> + {
> + beginTime = getCurrentTimeMillis();
> + if ( isOpen )
> + {
> + while( (leftInputRow = leftSource.getNextRowCore()) != null)
> + {
> + DataValueDescriptor[] leftColumns =
leftInputRow.getRowArray();
> + if( !all)
> + {
> + if( isDuplicate( leftColumns))
> + continue; // Get the next left row
> + prevCols = leftInputRow.getRowArrayClone();
> + }
> + int compare = 0;
> + // Advance the right until there are no more right rows
or leftRow <= rightRow
> + while( rightInputRow != null && (compare = compare(
leftColumns, rightInputRow.getRowArray())) > 0)
> + rightInputRow = rightSource.getNextRowCore();
> +
> + if( rightInputRow == null || compare < 0)
> + {
> + // The left row is not in the right source.
> + if( opType == IntersectOrExceptNode.EXCEPT_OP)
> + // Output this row
> + break;
> + }
> + else
> + {
> + // The left and right rows are the same
> + if( SanityManager.DEBUG)
> + SanityManager.ASSERT( rightInputRow != null &&
compare == 0,
> + "Insert/Except execution
has gotten confused.");
> + if( all)
> + // Just advance the right input by one row.
> + rightInputRow = rightSource.getNextRowCore();
> + // If !all then we will skip past duplicates on the
left at the top of this loop,
> + // which will then force us to skip past any right
duplicates.
> + if( opType == IntersectOrExceptNode.INTERSECT_OP)
> + break; // output this row
> +
> + // opType == IntersectOrExceptNode.EXCEPT_OP
> + // This row should not be ouput
> + }
> + }
> + }
> + currentRow = leftInputRow;
> + setCurrentRow( currentRow);
> + nextTime += getElapsedMillis(beginTime);
> + return currentRow;
> + } // end of getNextRowCore
> +
> + private void advanceRightPastDuplicates( DataValueDescriptor[]
leftColumns)
> + throws StandardException
> + {
> + while((rightInputRow = rightSource.getNextRowCore()) != null
> + && compare( leftColumns, rightInputRow.getRowArray()) == 0)
> + ;
> + } // end of advanceRightPastDuplicates
> +
> + private int compare( DataValueDescriptor[] leftCols,
DataValueDescriptor[] rightCols)
> + throws StandardException
> + {
> + for( int i = 0; ; i++)
> + {
> + if( i >= leftCols.length)
> + return 0;
> + if( leftCols[i].compare( Orderable.ORDER_OP_LESSTHAN,
> + rightCols[i],
> + true, // nulls sort high
> + false))
> + return -1;
> + if( ! leftCols[i].compare( Orderable.ORDER_OP_EQUALS,
> + rightCols[i],
> + true, // nulls sort high
> + false))
> + return 1;
> + }
> + } // end of compare
> +
> + private boolean isDuplicate( DataValueDescriptor[] curColumns)
> + throws StandardException
> + {
> + if( prevCols == null)
> + return false;
> + for( int i = 0; i < prevCols.length; i++)
> + {
> + if( ! curColumns[i].compare( Orderable.ORDER_OP_EQUALS,
prevCols[i], true, false))
> + return false;
> + }
> + return true;
> + }
> +
> + public ExecRow getCurrentRow()
> + {
> + return currentRow;
> + }
> +
> + /**
> + * If the result set has been opened,
> + * close the currently open source.
> + *
> + * @exception StandardException thrown on error
> + */
> + public void close() throws StandardException
> + {
> + beginTime = getCurrentTimeMillis();
> + if ( isOpen )
> + {
> + if (closeCleanup != null)
> + closeCleanup.invoke(activation); // let activation tidy up
> + clearCurrentRow();
> + currentRow = null;
> + prevCols = null;
> + leftSource.close();
> + rightSource.close();
> + super.close();
> + }
> + else
> + if (SanityManager.DEBUG)
> + SanityManager.DEBUG("CloseRepeatInfo","Close of UnionResultSet
repeated");
> +
> + closeTime += getElapsedMillis(beginTime);
> + } // end of close
> +
> + public void finish() throws StandardException
> + {
> + leftSource.finish();
> + rightSource.finish();
> + finishAndRTS();
> + }
> +
> + /**
> + * Return the total amount of time spent in this ResultSet
> + *
> + * @param type CURRENT_RESULTSET_ONLY - time spent only in this ResultSet
> + * ENTIRE_RESULTSET_TREE - time spent in this ResultSet and below.
> + *
> + * @return long The total amount of time spent (in milliseconds).
> + */
> + public long getTimeSpent(int type)
> + {
> + long totTime = constructorTime + openTime + nextTime + closeTime;
> +
> + if (type == NoPutResultSet.CURRENT_RESULTSET_ONLY)
> + {
> + return totTime - leftSource.getTimeSpent(ENTIRE_RESULTSET_TREE)
> + - rightSource.getTimeSpent(ENTIRE_RESULTSET_TREE);
> + }
> + else
> + {
> + return totTime;
> + }
> + } // end of getTimeSpent
> +
> + /**
> + * @see CursorResultSet
> + *
> + * @return the row location of the current cursor row.
> + * @exception StandardException thrown on failure
> + */
> + public RowLocation getRowLocation() throws StandardException
> + {
> + // RESOLVE: What is the row location of an INTERSECT supposed to
be: the location from the
> + // left side, the right side, or null?
> + return ((CursorResultSet)leftSource).getRowLocation();
> + }
> +}
> Index:
java/engine/org/apache/derby/impl/sql/execute/GenericResultSetFactory.java
> ===================================================================
> ---
java/engine/org/apache/derby/impl/sql/execute/GenericResultSetFactory.java
(revision 111283)
> +++
java/engine/org/apache/derby/impl/sql/execute/GenericResultSetFactory.java
(working copy)
> @@ -1053,6 +1053,28 @@
> closeCleanup);
> }
>
> + public NoPutResultSet getSetOpProjectRestrictResultSet(
NoPutResultSet leftSource,
> +
NoPutResultSet rightSource,
> + Activation
activation,
> + int
resultSetNumber,
> + long
optimizerEstimatedRowCount,
> + double
optimizerEstimatedCost,
> + int opType,
> + boolean all,
> +
GeneratedMethod closeCleanup)
> + throws StandardException
> + {
> + return new SetOpProjectRestrictResultSet( leftSource,
> + rightSource,
> + activation,
> + resultSetNumber,
> +
optimizerEstimatedRowCount,
> + optimizerEstimatedCost,
> + opType,
> + all,
> + closeCleanup);
> + }
> +
> /**
> * A last index key sresult set returns the last row from
> * the index in question. It is used as an ajunct to max().
> Index: java/engine/org/apache/derby/iapi/sql/compile/C_NodeTypes.java
> ===================================================================
> --- java/engine/org/apache/derby/iapi/sql/compile/C_NodeTypes.java
(revision 111283)
> +++ java/engine/org/apache/derby/iapi/sql/compile/C_NodeTypes.java
(working copy)
> @@ -185,7 +185,9 @@
> static final int SUBSTRING_OPERATOR_NODE = 154;
> // UNUSED static final int BOOLEAN_NODE = 155;
> static final int DROP_ALIAS_NODE = 156;
> - // 157 - 185 available
> + static final int EXCEPT_NODE = 157;
> + static final int INTERSECT_NODE = 158;
> + // 159 - 185 available
> static final int MODIFY_COLUMN_TYPE_NODE = 186;
> static final int MODIFY_COLUMN_CONSTRAINT_NODE = 187;
> static final int ABSOLUTE_OPERATOR_NODE = 188;
> Index: java/engine/org/apache/derby/iapi/sql/execute/ResultSetFactory.java
> ===================================================================
> --- java/engine/org/apache/derby/iapi/sql/execute/ResultSetFactory.java
(revision 111283)
> +++ java/engine/org/apache/derby/iapi/sql/execute/ResultSetFactory.java
(working copy)
> @@ -1428,6 +1428,34 @@
> throws StandardException;
>
>
> + /**
> + * The SetOpProjectRestrictResultSet is used to implement an
INTERSECT or EXCEPT operation.
> + * It selects rows from an ordered UNION ALL of the source tables and
strips off the generated tag
> + * column used to identify the source of each of the rows.
> + *
> + * @param source The result set that implements the ordered UNION
ALL.
> + * @param activation the activation for this result set
> + * @param resultSetNumber
> + * @param opType IntersectOrExceptNode.INTERSECT_OP or EXCEPT_OP
> + * @param all true if the operation is an INTERSECT ALL or an EXCEPT
ALL,
> + * false if the operation is an INTERSECT DISCTINCT or an
EXCEPT DISCTINCT
> + *
> + * @return A ResultSet from which the caller can get the INTERSECT or
EXCEPT
> + *
> + * @exception StandardException Thrown on failure
> + */
> + NoPutResultSet getSetOpProjectRestrictResultSet( NoPutResultSet
leftSource,
> + NoPutResultSet
rightSource,
> + Activation
activation,
> + int resultSetNumber,
> + long
optimizerEstimatedRowCount,
> + double
optimizerEstimatedCost,
> + int opType,
> + boolean all,
> + GeneratedMethod
closeCleanup)
> + throws StandardException;
> +
> +
> //
> // Misc operations
> //
> Index: java/engine/org/apache/derby/loc/messages_en.properties
> ===================================================================
> --- java/engine/org/apache/derby/loc/messages_en.properties (revision
111283)
> +++ java/engine/org/apache/derby/loc/messages_en.properties (working copy)
> @@ -469,10 +469,10 @@
> 42X55=Table name ''{1}'' should be the same as ''{0}''.
> 42X56=The number of columns in the view column list does not match the
number of columns in the underlying query expression in the view definition
for ''{0}''.
> 42X57=The getColumnCount() for external virtual table ''{0}'' returned an
invalid value ''{1}''. Valid values are >= 1.
> -42X58=The number of columns on the left and right sides of the UNION must
be the same.
> +42X58=The number of columns on the left and right sides of the {0} must
be the same.
> 42X59=The number of columns in each VALUES constructor must be the same.
> 42X60=Invalid value ''{0}'' for insertMode property specified for table
''{1}''.
> -42X61=Types ''{0}'' and ''{1}'' are not UNION compatible.
> +42X61=Types ''{0}'' and ''{1}'' are not {2} compatible.
> 42X62=''{0}'' is not allowed in the ''{1}'' schema.
> 42X63=The USING clause did not return any results, no parameters can be
set.
> 42X64=Invalid value ''{0}'' specified for useStatistics property in the
Properties list. TRUE or FALSE are the only valid values.
> @@ -919,7 +919,7 @@
> X0X61.S=The values for column ''{4}'' in index ''{0}'' and table
''{1}.{2}'' do not match for row location {3}. The value in the index is
''{5}'', while the value in the base table is ''{6}''. The full index key,
including the row location, is ''{7}''. The suggested corrective action is
to recreate the index.
> X0X62.S=Inconsistency found between table ''{0}'' and index ''{1}''.
Error when trying to retrieve row location ''{2}'' from the table. The full
index key, including the row location, is ''{3}''. The suggested corrective
action is to recreate the index.
> X0X63.S=Got IOException ''{0}''.
> -X0X67.S=Columns of type ''{0}'' may not be used in CREATE INDEX, ORDER
BY, GROUP BY, UNION, or DISTINCT, because comparisons are not supported for
that type.
> +X0X67.S=Columns of type ''{0}'' may not be used in CREATE INDEX, ORDER
BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because comparisons are
not supported for that type.
> X0X81.S={0} ''{1}'' does not exist.
> X0X85.S=Index ''{0}'' was not created because ''{1}'' is not a valid
index type.
> X0X86.S=0 is an invalid parameter value for ResultSet.absolute(int row).
> Index:
java/testing/org/apache/derbyTesting/functionTests/tests/lang/intersect.sql
> ===================================================================
> ---
java/testing/org/apache/derbyTesting/functionTests/tests/lang/intersect.sql
(revision 0)
> +++
java/testing/org/apache/derbyTesting/functionTests/tests/lang/intersect.sql
(revision 0)
> @@ -0,0 +1,133 @@
> +create table t1( id integer not null primary key, i1 integer, i2 integer,
c10 char(10), c30 char(30), tm time);
> +create table t2( id integer not null primary key, i1 integer, i2 integer,
vc20 varchar(20), d double, dt date);
> +insert into t1(id,i1,i2,c10,c30) values
> + (1,1,1,'a','123456789012345678901234567890'),
> + (2,1,2,'a','bb'),
> + (3,1,3,'b','bb'),
> + (4,1,3,'zz','5'),
> + (5,null,null,null,'1.0'),
> + (6,null,null,null,'a');
> +insert into t2(id,i1,i2,vc20,d) values
> + (1,1,1,'a',1.0),
> + (2,1,2,'a',1.1),
> + (5,null,null,'12345678901234567890',3),
> + (100,1,3,'zz',3),
> + (101,1,2,'bb',null),
> + (102,5,5,'',null),
> + (103,1,3,' a',null),
> + (104,1,3,'null',7.4);
> +
> +-- no duplicates
> +select id,i1,i2 from t1 intersect select id,i1,i2 from t2 order by 1,2,3;
> +select id,i1,i2 from t1 intersect all select id,i1,i2 from t2 order by
1,2,3;
> +
> +-- duplicates
> +select i1,i2 from t1 intersect select i1,i2 from t2 order by 1,2;
> +select i1,i2 from t1 intersect all select i1,i2 from t2 order by 1,2;
> +
> +-- right side is empty
> +select i1,i2 from t1 intersect select i1,i2 from t2 where id = -1;
> +select i1,i2 from t1 intersect all select i1,i2 from t2 where id = -1;
> +
> +-- left side is empty
> +select i1,i2 from t1 where id = -1 intersect all select i1,i2 from t2;
> +
> +-- check precedence
> +select i1,i2 from t1 intersect all select i1,i2 from t2 intersect
values(5,5),(1,3) order by 1,2;
> +(select i1,i2 from t1 intersect all select i1,i2 from t2) intersect
values(5,5),(1,3) order by 1,2;
> +
> +values(-1,-1,-1) union select id,i1,i2 from t1 intersect select id,i1,i2
from t2 order by 1,2,3;
> +select id,i1,i2 from t1 intersect select id,i1,i2 from t2 union
values(-1,-1,-1) order by 1,2,3;
> +
> +-- check conversions
> +select c10 from t1 intersect select vc20 from t2 order by 1;
> +select c30 from t1 intersect select vc20 from t2;
> +select c30 from t1 intersect all select vc20 from t2;
> +
> +-- check insert intersect into table and intersect without order by
> +create table r( i1 integer, i2 integer);
> +insert into r select i1,i2 from t1 intersect select i1,i2 from t2;
> +select i1,i2 from r order by 1,2;
> +delete from r;
> +
> +insert into r select i1,i2 from t1 intersect all select i1,i2 from t2;
> +select i1,i2 from r order by 1,2;
> +delete from r;
> +
> +-- test LOB
> +create table t3( i1 integer, cl clob(64), bl blob(1M));
> +insert into t3 values
> + (1, cast( 'aa' as clob(64)), cast(X'01' as blob(1M)));
> +create table t4( i1 integer, cl clob(64), bl blob(1M));
> +insert into t4 values
> + (1, cast( 'aa' as clob(64)), cast(X'01' as blob(1M)));
> +
> +select cl from t3 intersect select cl from t4 order by 1;
> +
> +select bl from t3 intersect select bl from t4 order by 1;
> +
> +-- invalid conversion
> +select tm from t1 intersect select dt from t2;
> +select c30 from t1 intersect select d from t2;
> +
> +-- different number of columns
> +select i1 from t1 intersect select i1,i2 from t2;
> +
> +-- ? in select list of intersect
> +select ? from t1 intersect select i1 from t2;
> +select i1 from t1 intersect select ? from t2;
> +
> +-- except tests
> +select id,i1,i2 from t1 except select id,i1,i2 from t2 order by 1,2,3;
> +select id,i1,i2 from t1 except all select id,i1,i2 from t2 order by
1,2,3;
> +select id,i1,i2 from t2 except select id,i1,i2 from t1 order by 1,2,3;
> +select id,i1,i2 from t2 except all select id,i1,i2 from t1 order by
1,2,3;
> +
> +select i1,i2 from t1 except select i1,i2 from t2 order by 1,2;
> +select i1,i2 from t1 except all select i1,i2 from t2 order by 1,2;
> +select i1,i2 from t2 except select i1,i2 from t1 order by 1,2;
> +select i1,i2 from t2 except all select i1,i2 from t1 order by 1,2;
> +
> +-- right side is empty
> +select i1,i2 from t1 except select i1,i2 from t2 where id = -1 order by
1,2;
> +select i1,i2 from t1 except all select i1,i2 from t2 where id = -1 order
by 1,2;
> +
> +-- left side is empty
> +select i1,i2 from t1 where id = -1 except select i1,i2 from t2 order by
1,2;
> +select i1,i2 from t1 where id = -1 except all select i1,i2 from t2 order
by 1,2;
> +
> +-- Check precedence. Union and except have the same precedence. Intersect
has higher precedence.
> +select i1,i2 from t1 except select i1,i2 from t2 intersect values(-1,-1)
order by 1,2;
> +select i1,i2 from t1 except (select i1,i2 from t2 intersect
values(-1,-1)) order by 1,2;
> +select i1,i2 from t2 except select i1,i2 from t1 union values(5,5) order
by 1,2;
> +(select i1,i2 from t2 except select i1,i2 from t1) union values(5,5)
order by 1,2;
> +select i1,i2 from t2 except all select i1,i2 from t1 except select i1,i2
from t1 where id = 3 order by 1,2;
> +(select i1,i2 from t2 except all select i1,i2 from t1) except select
i1,i2 from t1 where id = 3 order by 1,2;
> +
> +-- check conversions
> +select c10 from t1 except select vc20 from t2 order by 1;
> +select c30 from t1 except select vc20 from t2 order by 1;
> +select c30 from t1 except all select vc20 from t2;
> +
> +-- check insert except into table and except without order by
> +insert into r select i1,i2 from t2 except select i1,i2 from t1;
> +select i1,i2 from r order by 1,2;
> +delete from r;
> +
> +insert into r select i1,i2 from t2 except all select i1,i2 from t1;
> +select i1,i2 from r order by 1,2;
> +delete from r;
> +
> +-- test LOB
> +select cl from t3 except select cl from t4 order by 1;
> +select bl from t3 except select bl from t4 order by 1;
> +
> +-- invalid conversion
> +select tm from t1 except select dt from t2;
> +select c30 from t1 except select d from t2;
> +
> +-- different number of columns
> +select i1 from t1 except select i1,i2 from t2;
> +
> +-- ? in select list of except
> +select ? from t1 except select i1 from t2;
> Index:
java/testing/org/apache/derbyTesting/functionTests/tests/lang/copyfiles.ant
> ===================================================================
> ---
java/testing/org/apache/derbyTesting/functionTests/tests/lang/copyfiles.ant
(revision 111283)
> +++
java/testing/org/apache/derbyTesting/functionTests/tests/lang/copyfiles.ant
(working copy)
> @@ -95,6 +95,7 @@
> innerjoin.sql
> insert.sql
> insert_sed.properties
> +intersect.sql
> isolationLevels.sql
> joinDeadlock.sql
> joinDeadlock.sql1
> Index:
java/testing/org/apache/derbyTesting/functionTests/master/groupBy.out
> ===================================================================
> --- java/testing/org/apache/derbyTesting/functionTests/master/groupBy.out
(revision 111283)
> +++ java/testing/org/apache/derbyTesting/functionTests/master/groupBy.out
(working copy)
> @@ -45,7 +45,7 @@
> create table unmapped(c1 long varchar);
> 0 rows inserted/updated/deleted
> ij> select c1, max(1) from unmapped group by c1;
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- clean up
> drop table t1;
> 0 rows inserted/updated/deleted
> Index: java/testing/org/apache/derbyTesting/functionTests/master/LOB.out
> ===================================================================
> --- java/testing/org/apache/derbyTesting/functionTests/master/LOB.out
(revision 111283)
> +++ java/testing/org/apache/derbyTesting/functionTests/master/LOB.out
(working copy)
> @@ -266,13 +266,13 @@
> 0 rows inserted/updated/deleted
> ij> -- create index (not allowed)
> create index ia on a(a);
> -ERROR X0X67: Columns of type 'BLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'BLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> create index ib on b(a);
> -ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX, ORDE
R BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because comparisons
are not supported for that type.
> ij> create index ic on c(a);
> ERROR 42Y55: 'CREATE INDEX' cannot be performed on 'C' because it does
not exist.
> ij> create index id on d(a);
> -ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- cleanup
> drop table a;
> 0 rows inserted/updated/deleted
> @@ -535,7 +535,7 @@
> 1 row inserted/updated/deleted
> ij> -- UNION
> select * from testPredicate1 union select * from testPredicate2;
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- IN predicate
> select c1 from testPredicate1 where c1 IN (select c1 from
testPredicate2);
> ERROR 42818: Comparisons between 'LONG VARCHAR' and 'LONG VARCHAR' are
not supported.
> @@ -544,10 +544,10 @@
> ERROR 42818: Comparisons between 'LONG VARCHAR' and 'LONG VARCHAR' are
not supported.
> ij> -- ORDER BY clause
> select * from testPredicate1 order by c1;
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- GROUP BY clause
> select substr(c1,1,2) from testPredicate1 group by c1;
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- JOIN
> select * from testPredicate1 t1, testPredicate2 t2 where t1.c1=t2.c1;
> ERROR 42818: Comparisons between 'LONG VARCHAR' and 'LONG VARCHAR' are
not supported.
> @@ -555,15 +555,15 @@
> ERROR 42818: Comparisons between 'LONG VARCHAR' and 'LONG VARCHAR' are
not supported.
> ij> -- PRIMARY KEY
> create table testConst1(c1 long varchar not null primary key);
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- UNIQUE KEY constraints
> CREATE TABLE testconst2 (col1 long varchar not null, CONSTRAINT uk UNIQUE
(col1));
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> -- FOREIGN KEY constraints
> create table testConst3 (c1 char(10) not null, primary key (c1));
> 0 rows inserted/updated/deleted
> ij> create table testConst4 (c1 long varchar not null, constraint fk
foreign key (c1) references testConst3 (c1));
> -ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, or DISTINCT, because comparisons are not
supported for that type.
> +ERROR X0X67: Columns of type 'LONG VARCHAR' may not be used in CREATE
INDEX, ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> ij> drop table testConst3;
> 0 rows inserted/updated/deleted
> ij> -- MAX aggregate function
> Index:
java/testing/org/apache/derbyTesting/functionTests/master/intersect.out
> ===================================================================
> ---
java/testing/org/apache/derbyTesting/functionTests/master/intersect.out
(revision 0)
> +++
java/testing/org/apache/derbyTesting/functionTests/master/intersect.out
(revision 0)
> @@ -0,0 +1,313 @@
> +ij> create table t1( id integer not null primary key, i1 integer, i2
integer, c10 char(10), c30 char(30), tm time);
> +0 rows inserted/updated/deleted
> +ij> create table t2( id integer not null primary key, i1 integer, i2
integer, vc20 varchar(20), d double, dt date);
> +0 rows inserted/updated/deleted
> +ij> insert into t1(id,i1,i2,c10,c30) values
> + (1,1,1,'a','123456789012345678901234567890'),
> + (2,1,2,'a','bb'),
> + (3,1,3,'b','bb'),
> + (4,1,3,'zz','5'),
> + (5,null,null,null,'1.0'),
> + (6,null,null,null,'a');
> +6 rows inserted/updated/deleted
> +ij> insert into t2(id,i1,i2,vc20,d) values
> + (1,1,1,'a',1.0),
> + (2,1,2,'a',1.1),
> + (5,null,null,'12345678901234567890',3),
> + (100,1,3,'zz',3),
> + (101,1,2,'bb',null),
> + (102,5,5,'',null),
> + (103,1,3,' a',null),
> + (104,1,3,'null',7.4);
> +8 rows inserted/updated/deleted
> +ij> -- no duplicates
> +select id,i1,i2 from t1 intersect select id,i1,i2 from t2 order by 1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +1 |1 |1
> +2 |1 |2
> +5 |NULL |NULL
> +ij> select id,i1,i2 from t1 intersect all select id,i1,i2 from t2 order
by 1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +1 |1 |1
> +2 |1 |2
> +5 |NULL |NULL
> +ij> -- duplicates
> +select i1,i2 from t1 intersect select i1,i2 from t2 order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +NULL |NULL
> +ij> select i1,i2 from t1 intersect all select i1,i2 from t2 order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +1 |3
> +NULL |NULL
> +ij> -- right side is empty
> +select i1,i2 from t1 intersect select i1,i2 from t2 where id = -1;
> +I1 |I2
> +-----------------------
> +ij> select i1,i2 from t1 intersect all select i1,i2 from t2 where id
= -1;
> +I1 |I2
> +-----------------------
> +ij> -- left side is empty
> +select i1,i2 from t1 where id = -1 intersect all select i1,i2 from t2;
> +I1 |I2
> +-----------------------
> +ij> -- check precedence
> +select i1,i2 from t1 intersect all select i1,i2 from t2 intersect
values(5,5),(1,3) order by 1,2;
> +1 |2
> +-----------------------
> +1 |3
> +ij> (select i1,i2 from t1 intersect all select i1,i2 from t2) intersect
values(5,5),(1,3) order by 1,2;
> +1 |2
> +-----------------------
> +1 |3
> +ij> values(-1,-1,-1) union select id,i1,i2 from t1 intersect select
id,i1,i2 from t2 order by 1,2,3;
> +1 |2 |3
> +-----------------------------------
> +-1 |-1 |-1
> +1 |1 |1
> +2 |1 |2
> +5 |NULL |NULL
> +ij> select id,i1,i2 from t1 intersect select id,i1,i2 from t2 union
values(-1,-1,-1) order by 1,2,3;
> +1 |2 |3
> +-----------------------------------
> +-1 |-1 |-1
> +1 |1 |1
> +2 |1 |2
> +5 |NULL |NULL
> +ij> -- check conversions
> +select c10 from t1 intersect select vc20 from t2 order by 1;
> +1
> +--------------------
> +a
> +zz
> +ij> select c30 from t1 intersect select vc20 from t2;
> +1
> +------------------------------
> +a
> +bb
> +ij> select c30 from t1 intersect all select vc20 from t2;
> +1
> +------------------------------
> +a
> +bb
> +ij> -- check insert intersect into table and intersect without order by
> +create table r( i1 integer, i2 integer);
> +0 rows inserted/updated/deleted
> +ij> insert into r select i1,i2 from t1 intersect select i1,i2 from t2;
> +4 rows inserted/updated/deleted
> +ij> select i1,i2 from r order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +NULL |NULL
> +ij> delete from r;
> +4 rows inserted/updated/deleted
> +ij> insert into r select i1,i2 from t1 intersect all select i1,i2 from
t2;
> +5 rows inserted/updated/deleted
> +ij> select i1,i2 from r order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +1 |3
> +NULL |NULL
> +ij> delete from r;
> +5 rows inserted/updated/deleted
> +ij> -- test LOB
> +create table t3( i1 integer, cl clob(64), bl blob(1M));
> +0 rows inserted/updated/deleted
> +ij> insert into t3 values
> + (1, cast( 'aa' as clob(64)), cast(X'01' as blob(1M)));
> +1 row inserted/updated/deleted
> +ij> create table t4( i1 integer, cl clob(64), bl blob(1M));
> +0 rows inserted/updated/deleted
> +ij> insert into t4 values
> + (1, cast( 'aa' as clob(64)), cast(X'01' as blob(1M)));
> +1 row inserted/updated/deleted
> +ij> select cl from t3 intersect select cl from t4 order by 1;
> +ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> +ij> select bl from t3 intersect select bl from t4 order by 1;
> +ERROR X0X67: Columns of type 'BLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> +ij> -- invalid conversion
> +select tm from t1 intersect select dt from t2;
> +ERROR 42X61: Types 'TIME' and 'DATE' are not INTERSECT compatible.
> +ij> select c30 from t1 intersect select d from t2;
> +ERROR 42X61: Types 'CHAR' and 'DOUBLE' are not INTERSECT compatible.
> +ij> -- different number of columns
> +select i1 from t1 intersect select i1,i2 from t2;
> +ERROR 42X58: The number of columns on the left and right sides of the
INTERSECT must be the same.
> +ij> -- ? in select list of intersect
> +select ? from t1 intersect select i1 from t2;
> +ERROR 42X34: There is a ? parameter in the select list. This is not
allowed.
> +ij> select i1 from t1 intersect select ? from t2;
> +ERROR 42X34: There is a ? parameter in the select list. This is not
allowed.
> +ij> -- except tests
> +select id,i1,i2 from t1 except select id,i1,i2 from t2 order by 1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +3 |1 |3
> +4 |1 |3
> +6 |NULL |NULL
> +ij> select id,i1,i2 from t1 except all select id,i1,i2 from t2 order by
1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +3 |1 |3
> +4 |1 |3
> +6 |NULL |NULL
> +ij> select id,i1,i2 from t2 except select id,i1,i2 from t1 order by
1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +100 |1 |3
> +101 |1 |2
> +102 |5 |5
> +103 |1 |3
> +104 |1 |3
> +ij> select id,i1,i2 from t2 except all select id,i1,i2 from t1 order by
1,2,3;
> +ID |I1 |I2
> +-----------------------------------
> +100 |1 |3
> +101 |1 |2
> +102 |5 |5
> +103 |1 |3
> +104 |1 |3
> +ij> select i1,i2 from t1 except select i1,i2 from t2 order by 1,2;
> +I1 |I2
> +-----------------------
> +ij> select i1,i2 from t1 except all select i1,i2 from t2 order by 1,2;
> +I1 |I2
> +-----------------------
> +NULL |NULL
> +ij> select i1,i2 from t2 except select i1,i2 from t1 order by 1,2;
> +I1 |I2
> +-----------------------
> +5 |5
> +ij> select i1,i2 from t2 except all select i1,i2 from t1 order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |2
> +1 |3
> +5 |5
> +ij> -- right side is empty
> +select i1,i2 from t1 except select i1,i2 from t2 where id = -1 order by
1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +NULL |NULL
> +ij> select i1,i2 from t1 except all select i1,i2 from t2 where id = -1
order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +1 |3
> +NULL |NULL
> +NULL |NULL
> +ij> -- left side is empty
> +select i1,i2 from t1 where id = -1 except select i1,i2 from t2 order by
1,2;
> +I1 |I2
> +-----------------------
> +ij> select i1,i2 from t1 where id = -1 except all select i1,i2 from t2
order by 1,2;
> +I1 |I2
> +-----------------------
> +ij> -- Check precedence. Union and except have the same precedence.
Intersect has higher precedence.
> +select i1,i2 from t1 except select i1,i2 from t2 intersect values(-1,-1)
order by 1,2;
> +1 |2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +NULL |NULL
> +ij> select i1,i2 from t1 except (select i1,i2 from t2 intersect
values(-1,-1)) order by 1,2;
> +1 |2
> +-----------------------
> +1 |1
> +1 |2
> +1 |3
> +NULL |NULL
> +ij> select i1,i2 from t2 except select i1,i2 from t1 union values(5,5)
order by 1,2;
> +1 |2
> +-----------------------
> +5 |5
> +ij> (select i1,i2 from t2 except select i1,i2 from t1) union values(5,5)
order by 1,2;
> +1 |2
> +-----------------------
> +5 |5
> +ij> select i1,i2 from t2 except all select i1,i2 from t1 except select
i1,i2 from t1 where id = 3 order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |2
> +5 |5
> +ij> (select i1,i2 from t2 except all select i1,i2 from t1) except select
i1,i2 from t1 where id = 3 order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |2
> +5 |5
> +ij> -- check conversions
> +select c10 from t1 except select vc20 from t2 order by 1;
> +1
> +--------------------
> +b
> +NULL
> +ij> select c30 from t1 except select vc20 from t2 order by 1;
> +1
> +------------------------------
> +1.0
> +123456789012345678901234567890
> +5
> +ij> select c30 from t1 except all select vc20 from t2;
> +1
> +------------------------------
> +1.0
> +123456789012345678901234567890
> +5
> +bb
> +ij> -- check insert except into table and except without order by
> +insert into r select i1,i2 from t2 except select i1,i2 from t1;
> +1 row inserted/updated/deleted
> +ij> select i1,i2 from r order by 1,2;
> +I1 |I2
> +-----------------------
> +5 |5
> +ij> delete from r;
> +1 row inserted/updated/deleted
> +ij> insert into r select i1,i2 from t2 except all select i1,i2 from t1;
> +3 rows inserted/updated/deleted
> +ij> select i1,i2 from r order by 1,2;
> +I1 |I2
> +-----------------------
> +1 |2
> +1 |3
> +5 |5
> +ij> delete from r;
> +3 rows inserted/updated/deleted
> +ij> -- test LOB
> +select cl from t3 except select cl from t4 order by 1;
> +ERROR X0X67: Columns of type 'CLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> +ij> select bl from t3 except select bl from t4 order by 1;
> +ERROR X0X67: Columns of type 'BLOB' may not be used in CREATE INDEX,
ORDER BY, GROUP BY, UNION, INTERSECT, EXCEPT or DISTINCT, because
comparisons are not supported for that type.
> +ij> -- invalid conversion
> +select tm from t1 except select dt from t2;
> +ERROR 42X61: Types 'TIME' and 'DATE' are not EXCEPT compatible.
> +ij> select c30 from t1 except select d from t2;
> +ERROR 42X61: Types 'CHAR' and 'DOUBLE' are not EXCEPT compatible.
> +ij> -- different number of columns
> +select i1 from t1 except select i1,i2 from t2;
> +ERROR 42X58: The number of columns on the left and right sides of the
EXCEPT must be the same.
> +ij> -- ? in select list of except
> +select ? from t1 except select i1 from t2;
> +ERROR 42X34: There is a ? parameter in the select list. This is not
allowed.
> +ij>
> Index:
java/testing/org/apache/derbyTesting/functionTests/suites/derbylang.runall
> ===================================================================
> ---
java/testing/org/apache/derbyTesting/functionTests/suites/derbylang.runall
(revision 111283)
> +++
java/testing/org/apache/derbyTesting/functionTests/suites/derbylang.runall
(working copy)
> @@ -67,6 +67,7 @@
> lang/infostreams.sql
> lang/innerjoin.sql
> lang/insert.sql
> +lang/intersect.sql
> lang/isolationLevels.sql
> lang/joinDeadlock.sql
> lang/joins.sql
>
Re: [PATCH] Intersect and Except
Posted by Jack Klebanoff <kl...@Mutagen.Net>.
Satheesh Bandaram wrote:
> I believe this change is also needed to the original patch submitted.
> Minor change, but the original patch was allowing the following
> statement, when it should have failed:
>
> ij> select * from app.t intersect select * from app.t1 order by t.i;
> I
> -----------
>
> 0 rows selected
>
> Satheesh
>
> [bandaram:satheesh] svn diff OrderByColumn.java
> Index: OrderByColumn.java
> ===================================================================
> --- OrderByColumn.java (revision 111541)
> +++ OrderByColumn.java (working copy)
> @@ -172,7 +172,7 @@
> ResultColumnList targetCols =
> target.getResultColumns();
>
> //bug 5716 - for db2 compatibility - no qualified names
> allowed in order by clause when union/union all operator is used
> - if (target instanceof UnionNode && correlationName !=
> null)
> + if (target instanceof SetOperatorNode && correlationName
> != null
> )
> {
> String fullName = (schemaName != null) ?
> (schemaName + "." + correlationName +
> "." + columnName) :
> [bandaram:satheesh]
Good catch Satheesh! Actually there is another bug with order by in
intersect -- it is not implemented! I will post an update to my patch
when I have fixed this and some other issues.
Jack
Re: [PATCH] Intersect and Except
Posted by Satheesh Bandaram <sa...@Sourcery.Org>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
I believe this change is also needed to the original patch submitted.
Minor change, but the original patch was allowing the following
statement, when it should have failed:
ij> select * from app.t intersect select * from app.t1 order by t.i;
I
- -----------
0 rows selected
Satheesh
[bandaram:satheesh] svn diff OrderByColumn.java
Index: OrderByColumn.java
===================================================================
- --- OrderByColumn.java (revision 111541)
+++ OrderByColumn.java (working copy)
@@ -172,7 +172,7 @@
ResultColumnList targetCols =
target.getResultColumns();
//bug 5716 - for db2 compatibility - no qualified names
allowed in order by clause when union/union all operator is used
- - if (target instanceof UnionNode && correlationName !=
null)
+ if (target instanceof SetOperatorNode && correlationName
!= null
)
{
String fullName = (schemaName != null) ?
(schemaName + "." + correlationName +
"." + columnName) :
[bandaram:satheesh]
Daniel John Debrunner wrote:
> For java source files that are completely new code (e.g.
> IntersectOrExceptNode.java) the copyright creation date should be 2004,
> not 1997.
>
> Can you explain why we need the classes ExceptNode.java and
> IntersectNode.java? They seem to provide little value and the code could
> be folded into the parent class easily. I'm always concerned about the
> footprint of Derby and each class file has overhead.
>
> Does the javadoc comment for SetOpProjectRestrictResultSet match what it
> is doing? Is a UNION ALL being used?
>
> +/**
> + * Takes the result set produced by an ordered UNION ALL of two tagged
> result sets and produces
> + * the INTERSECT or EXCEPT of the two input result sets. This also
> projects out the tag, the last column
> + * of the input rows.
> + */
>
> In SetOpProjectRestrictResultSet.compare() this code confused me for a
> while. It would be better written as a standard loop with the condition
> i < leftCols.length in the for operator, and then return 0 after the
> loop. Similar to how the next method isDuplicate() is coded.
>
> + for( int i = 0; ; i++)
> + {
> + if( i >= leftCols.length)
> + return 0;
>
>
>
>
> Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFBukILENVNIY6DZ7ERAmkOAJ4rEWnAYq/B1Top6pA33+2jxHn9SQCgjSnT
xXurNIAW5m7Z5pZTpCV41Zg=
=DhJj
-----END PGP SIGNATURE-----
Re: [PATCH] Intersect and Except
Posted by Daniel John Debrunner <dj...@debrunners.com>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
For java source files that are completely new code (e.g.
IntersectOrExceptNode.java) the copyright creation date should be 2004,
not 1997.
Can you explain why we need the classes ExceptNode.java and
IntersectNode.java? They seem to provide little value and the code could
be folded into the parent class easily. I'm always concerned about the
footprint of Derby and each class file has overhead.
Does the javadoc comment for SetOpProjectRestrictResultSet match what it
is doing? Is a UNION ALL being used?
+/**
+ * Takes the result set produced by an ordered UNION ALL of two tagged
result sets and produces
+ * the INTERSECT or EXCEPT of the two input result sets. This also
projects out the tag, the last column
+ * of the input rows.
+ */
In SetOpProjectRestrictResultSet.compare() this code confused me for a
while. It would be better written as a standard loop with the condition
i < leftCols.length in the for operator, and then return 0 after the
loop. Similar to how the next method isDuplicate() is coded.
+ for( int i = 0; ; i++)
+ {
+ if( i >= leftCols.length)
+ return 0;
Dan.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFBuiRaIv0S4qsbfuQRAhEcAKCe6OmLmhjS14A8ymzUuTXehdgD3wCg3w+I
Ne3biR85T9EwMptYWESfUlI=
=ZXbp
-----END PGP SIGNATURE-----