Cartesian Join

5 posts / 0 new
Last post
mick.francis
mick.francis's picture
Offline
Last seen: 4 months 1 week ago
Joined: Apr 7 2010
Junior Boarder

Posts: 4

Mick Francis
Cartesian Join

Hi,

In several cases we need to carry out a cartesian join between two tables (i.e. where there is no join predicate). A simple example is this:

create table t1(c char(1)) engine=infinidb;
create table t2(c char(1)) engine=infinidb;

insert into t1 values('a');
insert into t1 values('b');
insert into t2 values('x');
insert into t3 values('y');

select t1.c, t2.c from t1,t2;

With the InfiniDB engine (InfiniDB Community Edition 1.1-1 Alpha (GPL), Win64), I get:

ERROR 138 (HY000): IDB-1000: 't1' is not joined.

whereas with InnoDB (for example) I get:

+------+------+
| c | c |
+------+------+
| a | x |
| b | x |
| a | y |
| b | y |
+------+------+
4 rows in set (0.00 sec)

Are there plans to implement this in InfiniDB?

Kind regards,

Mick.

jtommaney
jtommaney's picture
Offline
Last seen: 4 weeks 5 hours ago
Joined: Oct 27 2009
Expert Boarder

Posts: 58

Jim Tommaney
Re:Cartesian Join

Today, unjoined tables are not currently allowed within InfiniDB, so cartesian results cannot currently be executed with the usual method of skipping the join. However, InfiniDB does support cartesian results for joined tables to cover examples like a many-many join. This can be leveraged to use cartesian results to generate data in something close to the usual manner.

Here we add a second column and populate with the value of 1 for all rows. Joining on c2 = c2 will join all rows against all rows, yielding cartesian results. Example below.

Cartesian joins can be used to generate something like 100 million rows using the work-around show below. Long-term, we may allow a flag that would let unjoined tables through, however the downside for a missing join on expected table cardinalities (100 million dimensions and 100 billion facts) can be very bad. So, no immediate plans to change the default behavior, but would welcome feedback on whether this work-around is reasonable or whether the flag should be considered.

Thanks - Jim Tommaney

[code]mysql> create table t1(c char(1), c2 tinyint) engine=infinidb;
Query OK, 0 rows affected (0.35 sec)

mysql> create table t2(c char(1), c2 tinyint) engine=infinidb;
Query OK, 0 rows affected (0.58 sec)

mysql>
mysql> insert into t1 values('a',1);
Query OK, 1 row affected (0.07 sec)

mysql> insert into t1 values('b',1);
Query OK, 1 row affected (0.02 sec)

mysql> insert into t2 values('x',1);
Query OK, 1 row affected (0.06 sec)

mysql> insert into t2 values('y',1);
Query OK, 1 row affected (0.04 sec)

mysql>
mysql> select t1.c, t2.c from t1 join t2 using (c2);
+---------+---------+
| jt.t1.c | jt.t2.c |
+---------+---------+
| a | x |
| a | y |
| b | x |
| b | y |
+---------+---------+
4 rows in set (0.56 sec)

mysql> select count(*) from t1 join t2 using(c2) join t2 t3 using(c2);
+----------+
| count(*) |
+----------+
| 8 |
+----------+
1 row in set (0.14 sec)

mysql> select count(*) from t1 join t2 using(c2) join t2 t3 using(c2) join t2 t4 using(c2) join t2 t5 using(c2) join t2 t6 using(c2) ;
+----------+
| count(*) |
+----------+
| 64 |
+----------+
1 row in set (0.04 sec)[/code]

mick.francis
mick.francis's picture
Offline
Last seen: 4 months 1 week ago
Joined: Apr 7 2010
Junior Boarder

Posts: 4

Mick Francis
Re:Cartesian Join

Thanks for the reply Jim.

Perhaps a better solution would be to allow a /*!ALLOW_NO_JOIN*/ (or some such) pragmatic comment? This way you'd get the best of both worlds: Catch missing joins that should be there, but allow no join where explicitly requested.

A solution would be useful for us, as we try to keep as much commonality as possible between the SQL we generate for the various DBMS back-ends we support.

Kind regards,

Mick.

jtommaney
jtommaney's picture
Offline
Last seen: 4 weeks 5 hours ago
Joined: Oct 27 2009
Expert Boarder

Posts: 58

Jim Tommaney
Re:Cartesian Join

Mick,

I like the idea of using the hint here, that appears the direction we will head eventually.

Thanks - Jim Tommaney

mick.francis
mick.francis's picture
Offline
Last seen: 4 months 1 week ago
Joined: Apr 7 2010
Junior Boarder

Posts: 4

Mick Francis
Re:Cartesian Join

Hi Jim,

Another possibility that springs to mind is the use of the CROSS JOIN syntax to allow no join predicates - this feels in keeping with the spirit of the SQL syntax. (My only reservation is that perhaps CROSS JOIN is parsed as equivalent to INNER JOIN by the MySQL parser before you get hold of the parse tree?)

Do you have any feel for when predicate-less joins will be supported (in whatever way)?

Kind regards,

Mick.