Foreign keys + NATURAL JOIN

[Kristoffer Danielsson]

Q: Does foreign keys affect NATURAL JOINs?



SQLite 3.6.18 sample (NO foreign keys):

CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);

CREATE TABLE t2 (x INTEGER PRIMARY KEY, y INTEGER NOT NULL);

SELECT * FROM a NATURAL JOIN b; -- Cartesian product!



SQLite 3.6.19 sample (using foreign keys):

CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);

CREATE TABLE t2 (x INTEGER PRIMARY KEY, FOREIGN KEY(y) REFERENCES t1(a) );



SELECT * FROM a NATURAL JOIN b; -- Inner join??



I haven't tested this. Does this NATURAL JOIN produce an inner join or a cartesian product?





Anyway, I think this should be documented.

_________________________________________________________________
Hitta hetaste singlarna på MSN Dejting!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952

[Darren Duncan]

Post by Kristoffer Danielsson
Q: Does foreign keys affect NATURAL JOINs?
I haven't tested this. Does this NATURAL JOIN produce an inner join or a cartesian product?

The presence of foreign key constraints has no effect on the results of any
queries, using natural joins or otherwise.

A natural join between 2 tables/rowsets gives you a cartesian product if and
only if none of the column names are the same. A natural join gives you an
inner join if and only if at least one column name is the same in both
tables/rowsets.

Post by Kristoffer Danielsson
Anyway, I think this should be documented.

What I have described above is normal/proper behavior in relational or SQL
DBMSs. What details exactly are you proposing need explicit documentation
versus what would be going too far or stating the obvious?

Post by Kristoffer Danielsson
CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);
CREATE TABLE t2 (x INTEGER PRIMARY KEY, y INTEGER NOT NULL);
SELECT * FROM a NATURAL JOIN b; -- Cartesian product!

I think you meant to say:

SELECT * FROM t1 NATURAL JOIN t2;

... and yes, this is indeed a cartesian product since (a,b)∩(x,y) is the empty set.

Post by Kristoffer Danielsson
CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);
CREATE TABLE t2 (x INTEGER PRIMARY KEY, FOREIGN KEY(y) REFERENCES t1(a) );
SELECT * FROM a NATURAL JOIN b; -- Inner join??

I think you meant to say:

CREATE TABLE t2 (x INTEGER PRIMARY KEY, y INTEGER NOT NULL, FOREIGN KEY(y)
REFERENCES t1(a) );

SELECT * FROM t1 NATURAL JOIN t2;

... and no, this is also a cartesian product since (a,b)∩(x,y) is the empty set.

-- Darren Duncan

[Kristoffer Danielsson]

Thanks.



This leads me to the next question.



Why does the statement below yield a cartesian product?

SELECT COUNT(*) FROM t1 NATURAL JOIN t1; -- Sloooooooow!



Why does the statement below NOT yield a cartesian product?

SELECT COUNT(*) FROM (t1) NATURAL JOIN (t1); -- Several magnitudes faster than the query above!



Sure, the query is brain-damaged, but this could happen "by accident" in my software.



I'd expect SQLite to optimize this to simply "t1"!

Date: Sat, 17 Oct 2009 21:08:31 -0700
Subject: Re: [sqlite] Foreign keys + NATURAL JOIN

Post by Kristoffer Danielsson
Q: Does foreign keys affect NATURAL JOINs?
I haven't tested this. Does this NATURAL JOIN produce an inner join or a cartesian product?

The presence of foreign key constraints has no effect on the results of any
queries, using natural joins or otherwise.
A natural join between 2 tables/rowsets gives you a cartesian product if and
only if none of the column names are the same. A natural join gives you an
inner join if and only if at least one column name is the same in both
tables/rowsets.

Post by Kristoffer Danielsson
Anyway, I think this should be documented.

What I have described above is normal/proper behavior in relational or SQL
DBMSs. What details exactly are you proposing need explicit documentation
versus what would be going too far or stating the obvious?

Post by Kristoffer Danielsson
CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);
CREATE TABLE t2 (x INTEGER PRIMARY KEY, y INTEGER NOT NULL);
SELECT * FROM a NATURAL JOIN b; -- Cartesian product!

SELECT * FROM t1 NATURAL JOIN t2;
... and yes, this is indeed a cartesian product since (a,b)∩(x,y) is the empty set.

Post by Kristoffer Danielsson
CREATE TABLE t1 (a INTEGER PRIMARY KEY, b INTEGER NOT NULL);
CREATE TABLE t2 (x INTEGER PRIMARY KEY, FOREIGN KEY(y) REFERENCES t1(a) );
SELECT * FROM a NATURAL JOIN b; -- Inner join??

CREATE TABLE t2 (x INTEGER PRIMARY KEY, y INTEGER NOT NULL, FOREIGN KEY(y)
REFERENCES t1(a) );
SELECT * FROM t1 NATURAL JOIN t2;
... and no, this is also a cartesian product since (a,b)∩(x,y) is the empty set.
-- Darren Duncan
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Windows Live: Dina vänner får dina uppdateringar från Flickr, Yelp och Digg när de skickar e-post till dig.
http://www.microsoft.com/windows/windowslive/see-it-in-action/social-network-basics.aspx?ocid=PID23461::T:WLMTAGL:ON:WL:sv-se:SI_SB_3:092010

[Darren Duncan]

Post by Kristoffer Danielsson
Thanks.
This leads me to the next question.
Why does the statement below yield a cartesian product?
SELECT COUNT(*) FROM t1 NATURAL JOIN t1; -- Sloooooooow!

It doesn't. In fact "t1 NATURAL JOIN t1" would do the exact opposite, because
*all* of the columns have the same names, and moreover because both rowsets
being joined are the same rowset, the result should be identical to if you said
"t1 INTERSECT t1", which is the same as if you simply said "t1" without a join
at all. Natural joining something with itself results in itself, and is
analogous to "1 * 1 = 1" in math.

Post by Kristoffer Danielsson
Why does the statement below NOT yield a cartesian product?
SELECT COUNT(*) FROM (t1) NATURAL JOIN (t1); -- Several magnitudes faster than the query above!

This statement should have an identical result to the first one. Having
parenthesis around each t1 should make no difference.

Post by Kristoffer Danielsson
Sure, the query is brain-damaged, but this could happen "by accident" in my software.
I'd expect SQLite to optimize this to simply "t1"!

If SQLite is treating the above 2 queries differently, I would think that an
error. Are you sure that's what's happening?

If you are natural joining a table to itself, or intersecting a table with
itself, or unioning a table with itself, then hopefully the optimizer is smart
enough to replace that operation with simply the table itself.

-- Darren Duncan

[Kristoffer Danielsson]

Thanks Duncan, for your feedback.



This is indeed a bug (currently running SQLite 3.6.18). I guess this is where you report bugs?



1) Run the C++ program below to generate the necessary SQL data.

2) Then run sqlite3.exe and read it in! (.read test.sql)

3) Execute the following queries:



Blistering fast:

SELECT COUNT(*) FROM Item;

Result: 10000



Slooooow! WRONG result:

SELECT COUNT(*) FROM Item NATURAL JOIN Item;

Result: 100000000



Clearly, SQLite executes a cartesian product!



Oddly, this works as intented:

SELECT COUNT(*) FROM (Item) NATURAL JOIN (Item);

Result: 10000





Unfortunately, this is absolutely crucial for my application. I hope this can be fixed very soon!



//////////////////////////////////////////////////////////////////////////

#include <fstream>

int main()
{
std::ofstream file ("test.sql");

file << "CREATE TABLE IF NOT EXISTS Item (ItemID INTEGER PRIMARY KEY, A INTEGER NOT NULL, B INTEGER NOT NULL, C INTEGER NOT NULL, D INTEGER NOT NULL, E INTEGER NOT NULL, UNIQUE (A, B));\r\n";
file << "BEGIN TRANSACTION;\r\n";
for (int i = 0; i < 10000; ++i)
{
file << "INSERT INTO Item (A, B, C, D, E) VALUES ("
<< i << ", " << i + 1 << ", " << i + 2 << ", "
<< i + 3 << ", " << i + 4 << ");\r\n";
}
file << "COMMIT TRANSACTION;\r\n";

file.close();

return 0;
}

//////////////////////////////////////////////////////////////////////////

Date: Sat, 17 Oct 2009 23:02:10 -0700
Subject: Re: [sqlite] Foreign keys + NATURAL JOIN

Post by Kristoffer Danielsson
Thanks.
This leads me to the next question.
Why does the statement below yield a cartesian product?
SELECT COUNT(*) FROM t1 NATURAL JOIN t1; -- Sloooooooow!

It doesn't. In fact "t1 NATURAL JOIN t1" would do the exact opposite, because
*all* of the columns have the same names, and moreover because both rowsets
being joined are the same rowset, the result should be identical to if you said
"t1 INTERSECT t1", which is the same as if you simply said "t1" without a join
at all. Natural joining something with itself results in itself, and is
analogous to "1 * 1 = 1" in math.

Post by Kristoffer Danielsson
Why does the statement below NOT yield a cartesian product?
SELECT COUNT(*) FROM (t1) NATURAL JOIN (t1); -- Several magnitudes faster than the query above!

This statement should have an identical result to the first one. Having
parenthesis around each t1 should make no difference.

Post by Kristoffer Danielsson
Sure, the query is brain-damaged, but this could happen "by accident" in my software.
I'd expect SQLite to optimize this to simply "t1"!

If SQLite is treating the above 2 queries differently, I would think that an
error. Are you sure that's what's happening?
If you are natural joining a table to itself, or intersecting a table with
itself, or unioning a table with itself, then hopefully the optimizer is smart
enough to replace that operation with simply the table itself.
-- Darren Duncan
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Windows Live: Gör det enklare för dina vänner att se vad du håller på med på Facebook.
http://www.microsoft.com/windows/windowslive/see-it-in-action/social-network-basics.aspx?ocid=PID23461::T:WLMTAGL:ON:WL:sv-se:SI_SB_2:092009

[Jay A. Kreibich]

Post by Kristoffer Danielsson
SELECT COUNT(*) FROM Item;
Result: 10000
SELECT COUNT(*) FROM Item NATURAL JOIN Item;
Result: 100000000
Clearly, SQLite executes a cartesian product!

Look at the output. It does not produce a Cartesian product. All
the rows are valid:

SQLite version 3.6.19
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table t (c1, c2);
sqlite> insert into t values ( 1, 2 );
sqlite> insert into t values ( 3, 4 );
sqlite> insert into t values ( 5, 6 );
sqlite> select * from t natural join t;
1|2
1|2
1|2
3|4
3|4
3|4
5|6
5|6
5|6

I'm not sure I'd call it correct, but it isn't a product.

-j

[Darren Duncan]

Post by Jay A. Kreibich

Post by Kristoffer Danielsson
Clearly, SQLite executes a cartesian product!

Look at the output. It does not produce a Cartesian product. All
SQLite version 3.6.19
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table t (c1, c2);
sqlite> insert into t values ( 1, 2 );
sqlite> insert into t values ( 3, 4 );
sqlite> insert into t values ( 5, 6 );
sqlite> select * from t natural join t;
1|2
1|2
1|2
3|4
3|4
3|4
5|6
5|6
5|6
I'm not sure I'd call it correct, but it isn't a product.

Jay, you've just proven Kristoffer's point. That result demonstrates that a
cartesian product *was* produced. The table t had 3 rows, and the result had
3*3 rows, which is a cartesian product by definition.

Your query should have produced the same result as this query:

select t1.* from t as t1 inner join t as t2 using (c1,c2);

... but instead it produced the same result as this query:

select t1.* from t as t1 cross join t as t2 using (c1,c2);

Now I would be ready to consider that SQLite has a bug, but then looking at the
syntax at http://sqlite.org/lang_select.html I see that SQLite defines multiple
versions of natural join; it has *both* NATURAL INNER JOIN and NATURAL CROSS
JOIN, and I'm guessing that if you leave the middle word out it is using CROSS
by default, ostensibly for consistency for when you simply say JOIN.

So if that is the case, then the current behavior is clearly documented as
expected and so not an implementation bug. And so then you would have to say this:

select * from t natural inner join t;

... to get the expected result of 3 rows.

This all being said, the whole mess strikes me as a *design bug*. It simply
doesn't make sense to have both NATURAL INNER and NATURAL CROSS syntax. One
should simply be able to say NATURAL and it would do the right thing, which is a
cartesian product when no column names are the same, an intersect when all
column names are the same, and an inner join otherwise.

My proposal is certainly logically sound. A natural join by definition only has
a result row for each distinct pair of source rows that have the same values for
the subset of their columns with the same names; a cartesian product is a
degenerate case where that subset of columns has zero members, and so since the
empty set matches the empty set every row from each source rowsets would match
every row from the other rowsets.

The only variations that make sense on a natural join is OUTER.

-- Darren Duncan

[Kristoffer Danielsson]

NATURAL INNER JOIN yields a cartesian product too. Just tried it!

Date: Sun, 18 Oct 2009 15:54:11 -0700
Subject: Re: [sqlite] "x NATURAL JOIN x" BUG

Post by Kristoffer Danielsson
Clearly, SQLite executes a cartesian product!

Look at the output. It does not produce a Cartesian product. All
SQLite version 3.6.19
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table t (c1, c2);
sqlite> insert into t values ( 1, 2 );
sqlite> insert into t values ( 3, 4 );
sqlite> insert into t values ( 5, 6 );
sqlite> select * from t natural join t;
1|2
1|2
1|2
3|4
3|4
3|4
5|6
5|6
5|6
I'm not sure I'd call it correct, but it isn't a product.

Jay, you've just proven Kristoffer's point. That result demonstrates that a
cartesian product *was* produced. The table t had 3 rows, and the result had
3*3 rows, which is a cartesian product by definition.
select t1.* from t as t1 inner join t as t2 using (c1,c2);
select t1.* from t as t1 cross join t as t2 using (c1,c2);
Now I would be ready to consider that SQLite has a bug, but then looking at the
syntax at http://sqlite.org/lang_select.html I see that SQLite defines multiple
versions of natural join; it has *both* NATURAL INNER JOIN and NATURAL CROSS
JOIN, and I'm guessing that if you leave the middle word out it is using CROSS
by default, ostensibly for consistency for when you simply say JOIN.
So if that is the case, then the current behavior is clearly documented as
select * from t natural inner join t;
... to get the expected result of 3 rows.
This all being said, the whole mess strikes me as a *design bug*. It simply
doesn't make sense to have both NATURAL INNER and NATURAL CROSS syntax. One
should simply be able to say NATURAL and it would do the right thing, which is a
cartesian product when no column names are the same, an intersect when all
column names are the same, and an inner join otherwise.
My proposal is certainly logically sound. A natural join by definition only has
a result row for each distinct pair of source rows that have the same values for
the subset of their columns with the same names; a cartesian product is a
degenerate case where that subset of columns has zero members, and so since the
empty set matches the empty set every row from each source rowsets would match
every row from the other rowsets.
The only variations that make sense on a natural join is OUTER.
-- Darren Duncan
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Windows Live: Gör det enklare för dina vänner att se vad du håller på med på Facebook.
http://www.microsoft.com/windows/windowslive/see-it-in-action/social-network-basics.aspx?ocid=PID23461::T:WLMTAGL:ON:WL:sv-se:SI_SB_2:092009

[Darren Duncan]

Post by Kristoffer Danielsson
NATURAL INNER JOIN yields a cartesian product too. Just tried it!

Well then, *surely* that at least has to be a SQLite bug.

That said, it would be useful for clarity if you posted to the list exactly how
you wrote your NATURAL INNER, what the exact SQL you used was, with test data
and result, so we know you didn't just make a typo in your test.

Use the simplest possible example that illustrates the point, such as with Jay's
example.

And I would expect NATURAL JOIN to default to INNER even if JOIN defaults to
CROSS, just because that makes the most sense. When people specify NATURAL,
then what they expect is INNER semantics in the general case.

-- Darren Duncan

[Kristoffer Danielsson]

I did provide a sample with test data in my original post. However, I posted it here too:

http://www.sqlite.org/cvstrac/tktview?tn=4043



The tracker is obviously closed, but still, there it is :P. Don't know where else to post it.



/Chris

Date: Sun, 18 Oct 2009 16:25:48 -0700
Subject: Re: [sqlite] "x NATURAL JOIN x" BUG

Post by Kristoffer Danielsson
NATURAL INNER JOIN yields a cartesian product too. Just tried it!

Well then, *surely* that at least has to be a SQLite bug.
That said, it would be useful for clarity if you posted to the list exactly how
you wrote your NATURAL INNER, what the exact SQL you used was, with test data
and result, so we know you didn't just make a typo in your test.
Use the simplest possible example that illustrates the point, such as with Jay's
example.
And I would expect NATURAL JOIN to default to INNER even if JOIN defaults to
CROSS, just because that makes the most sense. When people specify NATURAL,
then what they expect is INNER semantics in the general case.
-- Darren Duncan
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Hitta kärleken nu i vår!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952

[Dan Kennedy]

Post by Kristoffer Danielsson
http://www.sqlite.org/cvstrac/tktview?tn=4043
The tracker is obviously closed, but still, there it is :P. Don't
know where else to post it.

Thanks for finding this bug. There is now a ticket here:

http://www.sqlite.org/src/info/b73fb0bd64

Current policy on bug reports is here:

http://www.sqlite.org/src/wiki?name=Bug+Reports

IMO it is a good idea to include "BUG" in the subject (as you have
done in
this thread) if your mail is a bug report. This will help make sure that
the report doesn't get missed.

Dan.

[Jay A. Kreibich]

Post by Darren Duncan

Post by Jay A. Kreibich

Post by Kristoffer Danielsson
Clearly, SQLite executes a cartesian product!

Look at the output. It does not produce a Cartesian product. All
SQLite version 3.6.19
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table t (c1, c2);
sqlite> insert into t values ( 1, 2 );
sqlite> insert into t values ( 3, 4 );
sqlite> insert into t values ( 5, 6 );
sqlite> select * from t natural join t;
1|2
1|2
1|2
3|4
3|4
3|4
5|6
5|6
5|6
I'm not sure I'd call it correct, but it isn't a product.

Jay, you've just proven Kristoffer's point. That result demonstrates that a
cartesian product *was* produced. The table t had 3 rows, and the result had
3*3 rows, which is a cartesian product by definition.

The definition of a Cartesian product is a bit more complete than "N rows
and M rows results in N * M rows." It is possible that a Cartesian
product may have been computed internally to arrive at these results,
but that does not change the fact that the result is not a Cartesian
product.

Post by Darren Duncan
select t1.* from t as t1 inner join t as t2 using (c1,c2);

Most likely, yes.

Post by Darren Duncan
select t1.* from t as t1 cross join t as t2 using (c1,c2);

Yes. And the result of this query is not a Cartesian product either,
as you've thrown away half the columns.

-j

[Kristoffer Danielsson]

Hi,



Great to hear. I was starting to think my code was damaged. Anyway, please beware of cases such as this:



SELECT * FROM X NATURAL JOIN (X NATURAL JOIN Y);



This yields the same error. Probably the same bug, but you never know.



When can we expect a bug fix? Days, weeks, months?



Thanks.

Date: Mon, 19 Oct 2009 14:44:27 +0700
Subject: Re: [sqlite] "x NATURAL JOIN x" BUG

Post by Kristoffer Danielsson
I did provide a sample with test data in my original post. However,
http://www.sqlite.org/cvstrac/tktview?tn=4043
The tracker is obviously closed, but still, there it is :P. Don't
know where else to post it.

http://www.sqlite.org/src/info/b73fb0bd64
http://www.sqlite.org/src/wiki?name=Bug+Reports
IMO it is a good idea to include "BUG" in the subject (as you have
done in
this thread) if your mail is a bug report. This will help make sure that
the report doesn't get missed.
Dan.
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Hitta kärleken nu i vår!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952

[Roger Binns]

Post by Kristoffer Danielsson
When can we expect a bug fix? Days, weeks, months?

Go to http://www.sqlite.org/src/reportlist and you can see all open tickets.
(Currently there is no report in priority order). SQLite consortium
members and paying customers get first priority.

You can see the timeline for what work is being done:

http://www.sqlite.org/src/timeline

Other than that (and I do not speak for the SQLite team here - just a long
time observer) criteria such as how many people are affected, the severity,
the difficulty of the fix, the likelihood of the fix breaking something else
etc are used. For example if this bug has been present in SQLite since 3.0
(5 years ago) then many people don't hit it. If you can narrow it down to
the release (or even better checkin) that caused the problem then that makes
it considerably easier to fix. You can do a bisection search to find the
culprit. (Sadly it doesn't appear that fossil can do bisection so you'll
have to do it manually.)

Roger

[Kristoffer Danielsson]

It makes sense.



I'll investigate this bug later. I'm quite sure it's no more than a couple of months old, since I only got these crazy performance hits just after the summer (I upgrade regularly, but haven't tested my software thoroughly - until now :P).



Thanks for your info.

Date: Mon, 19 Oct 2009 12:19:02 -0700
Subject: Re: [sqlite] "x NATURAL JOIN x" BUG
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Post by Kristoffer Danielsson
When can we expect a bug fix? Days, weeks, months?

Go to http://www.sqlite.org/src/reportlist and you can see all open tickets.
(Currently there is no report in priority order). SQLite consortium
members and paying customers get first priority.
http://www.sqlite.org/src/timeline
Other than that (and I do not speak for the SQLite team here - just a long
time observer) criteria such as how many people are affected, the severity,
the difficulty of the fix, the likelihood of the fix breaking something else
etc are used. For example if this bug has been present in SQLite since 3.0
(5 years ago) then many people don't hit it. If you can narrow it down to
the release (or even better checkin) that caused the problem then that makes
it considerably easier to fix. You can do a bisection search to find the
culprit. (Sadly it doesn't appear that fossil can do bisection so you'll
have to do it manually.)
Roger
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAkrcu6IACgkQmOOfHg372QSYHQCfbQ6XSVCvbJXn3eR2u9L5WHuq
+wwAoIQuky96CdIQypBHBMkhpSX9wWkz
=dxic
-----END PGP SIGNATURE-----
_______________________________________________
sqlite-users mailing list
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_________________________________________________________________
Windows Live: Håll dina vänner uppdaterade om vad du gör online.
http://www.microsoft.com/windows/windowslive/see-it-in-action/social-network-basics.aspx?ocid=PID23461::T:WLMTAGL:ON:WL:sv-se:SI_SB_1:092010

[Jay A. Kreibich]

Post by Kristoffer Danielsson
I'll investigate this bug later. I'm quite sure it's no more than a
couple of months old,

Just tested in 3.4.0 (June 2007) and it does the exact same thing.

-j