Virtuel-Counting-Row

[walexand@web.de]

I use the database mysql v.4.

My problem is...
I have a select like:
select * from user where language = "de";

the result are then:
id name
=============== ====
1 max
5 tim
99 otto

so and what i need is a virtuell row (pos) with a counting index of the result:
id name pos
=============== ==== ===
1 max 1
5 tim 2
99 otto 3

how can i make this with mysql?
My first idea was to made that with views but mysql can't do that!

MFG Alexander W.

[Siemel Naran]

Re: Virtuel-Counting-Row

<walexand@web.d e> wrote in message
[color=blue]
> I have a select like:
> select * from user where language = "de";
>
> the result are then:
> id name
> =============== ====
> 1 max
> 5 tim
> 99 otto
>
> so and what i need is a virtuell row (pos) with a counting index of the[/color]
result:[color=blue]
> id name pos
> =============== ==== ===
> 1 max 1
> 5 tim 2
> 99 otto 3
>
> how can i make this with mysql?
> My first idea was to made that with views but mysql can't do that![/color]

There might be some special function, I don't know for sure. But in 5.0
they will have cursors, and in the present version you can always do it in
C++ and other languages.

I can think of trying an extra table, but it doesn't seem like the best
solution.

create table temp_product (
id int(1) unsigned auto_increment,
product_id int(1) unsigned not null references product(id),
primary key (id)
);

....

delete from temp_product;

insert into temp_product (product_id)
select id from product
order by name desc;

select temp_product.id , product.*
from product inner join temp_product on product.id =
temp_product.pr oduct_id;

[Siemel Naran]

Re: Virtuel-Counting-Row

<walexand@web.d e> wrote in message
[color=blue]
> I have a select like:
> select * from user where language = "de";
>
> the result are then:
> id name
> =============== ====
> 1 max
> 5 tim
> 99 otto
>
> so and what i need is a virtuell row (pos) with a counting index of the[/color]
result:[color=blue]
> id name pos
> =============== ==== ===
> 1 max 1
> 5 tim 2
> 99 otto 3
>
> how can i make this with mysql?
> My first idea was to made that with views but mysql can't do that![/color]

There might be some special function, I don't know for sure. But in 5.0
they will have cursors, and in the present version you can always do it in
C++ and other languages.

I can think of trying an extra table, but it doesn't seem like the best
solution.

create table temp_product (
id int(1) unsigned auto_increment,
product_id int(1) unsigned not null references product(id),
primary key (id)
);

....

delete from temp_product;

insert into temp_product (product_id)
select id from product
order by name desc;

select temp_product.id , product.*
from product inner join temp_product on product.id =
temp_product.pr oduct_id;

[Mike Chirico]

Re: Virtuel-Counting-Row


<walexand@web.d e> wrote in message
news:b125b4b9.0 405051452.7b2b6 dd0@posting.goo gle.com...[color=blue]
> I use the database mysql v.4.
>
> My problem is...
> I have a select like:
> select * from user where language = "de";
>
> the result are then:
> id name
> =============== ====
> 1 max
> 5 tim
> 99 otto
>
> so and what i need is a virtuell row (pos) with a counting index of the[/color]
result:[color=blue]
> id name pos
> =============== ==== ===
> 1 max 1
> 5 tim 2
> 99 otto 3
>[/color]


Assume the following table:

CREATE TABLE student (
s_id int(11) NOT NULL auto_increment,
name varchar(15),
PRIMARY KEY (s_id)
);

Add some rows and delete (just to convice you this works in all cases
independent of the primary key)

insert into student (name) values ('tom');
insert into student (name) values ('bob');
insert into student (name) values ('sue');
insert into student (name) values ('mike');
insert into student (name) values ('joe');
insert into student (name) values ('zoe');
insert into student (name) values ('harpo');

delete from student where name = 'bob';

Now, note mc is the row count...indepen dent of s_id;


select a.name,sum(1) as mc
from student a, student b
where a.s_id <= b.s_id
group by a.s_id, a.name order by mc;
+-------+------+

| name | mc |
+-------+------+
| harpo | 1 |
| zoe | 2 |
| joe | 3 |
| mike | 4 |
| sue | 5 |
| tom | 6 |
+-------+------+
6 rows in set (0.00 sec)

Reference (TIP 22)

http://osdn.dl.sourceforge.net/sourceforge/souptonuts/README_mysql.txt

Hope this helps,

Mike Chirico

[Mike Chirico]

Re: Virtuel-Counting-Row


<walexand@web.d e> wrote in message
news:b125b4b9.0 405051452.7b2b6 dd0@posting.goo gle.com...[color=blue]
> I use the database mysql v.4.
>
> My problem is...
> I have a select like:
> select * from user where language = "de";
>
> the result are then:
> id name
> =============== ====
> 1 max
> 5 tim
> 99 otto
>
> so and what i need is a virtuell row (pos) with a counting index of the[/color]
result:[color=blue]
> id name pos
> =============== ==== ===
> 1 max 1
> 5 tim 2
> 99 otto 3
>[/color]


Assume the following table:

CREATE TABLE student (
s_id int(11) NOT NULL auto_increment,
name varchar(15),
PRIMARY KEY (s_id)
);

Add some rows and delete (just to convice you this works in all cases
independent of the primary key)

insert into student (name) values ('tom');
insert into student (name) values ('bob');
insert into student (name) values ('sue');
insert into student (name) values ('mike');
insert into student (name) values ('joe');
insert into student (name) values ('zoe');
insert into student (name) values ('harpo');

delete from student where name = 'bob';

Now, note mc is the row count...indepen dent of s_id;


select a.name,sum(1) as mc
from student a, student b
where a.s_id <= b.s_id
group by a.s_id, a.name order by mc;
+-------+------+

| name | mc |
+-------+------+
| harpo | 1 |
| zoe | 2 |
| joe | 3 |
| mike | 4 |
| sue | 5 |
| tom | 6 |
+-------+------+
6 rows in set (0.00 sec)

Reference (TIP 22)

http://osdn.dl.sourceforge.net/sourceforge/souptonuts/README_mysql.txt

Hope this helps,

Mike Chirico

[Siemel Naran]

Re: Virtuel-Counting-Row

"Mike Chirico" <mchirico@comca st.net> wrote in message
news:L66dncvnK4 TEdAfdRVn-
[color=blue]
> select a.name,sum(1) as mc
> from student a, student b
> where a.s_id <= b.s_id
> group by a.s_id, a.name order by mc;[/color]

That's pretty cool!
[color=blue]
> Reference (TIP 22)
> http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]

[Siemel Naran]

Re: Virtuel-Counting-Row

"Mike Chirico" <mchirico@comca st.net> wrote in message
news:L66dncvnK4 TEdAfdRVn-
[color=blue]
> select a.name,sum(1) as mc
> from student a, student b
> where a.s_id <= b.s_id
> group by a.s_id, a.name order by mc;[/color]

That's pretty cool!
[color=blue]
> Reference (TIP 22)
> http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]

[Mike Chirico]

Re: Virtuel-Counting-Row


"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:VwCmc.2716 7$Ut1.787960@bg tnsc05-news.ops.worldn et.att.net...[color=blue]
> "Mike Chirico" <mchirico@comca st.net> wrote in message
> news:L66dncvnK4 TEdAfdRVn-
>[color=green]
> > select a.name,sum(1) as mc
> > from student a, student b
> > where a.s_id <= b.s_id
> > group by a.s_id, a.name order by mc;[/color]
>
> That's pretty cool!
>[color=green]
> > Reference (TIP 22)
> > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color][/color]

It's also possible to compute running aggregates. Assume the following
table
and data:

CREATE TABLE dice (
d_id int(11) NOT NULL auto_increment,
roll int,
PRIMARY KEY (d_id)
);

insert into dice (roll) values (1);
insert into dice (roll) values (2);
insert into dice (roll) values (3);
insert into dice (roll) values (4);
insert into dice (roll) values (5);
insert into dice (roll) values (6);


The following gives a running, cumulative, sum:

mysql> select a.roll, sum(b.roll) from dice a, dice b
where b.d_id <= a.d_id group by a.d_id, a.roll;

+------+-------------+

| roll | sum(b.roll) |
+------+-------------+
| 1 | 1 |
| 2 | 3 |
| 3 | 6 |
| 4 | 10 |
| 5 | 15 |
| 6 | 21 |
+------+-------------+
6 rows in set (0.00 sec)


To get a running average change the
sum to avg as follows:


mysql> select a.roll, avg(b.roll) from dice a, dice b
where b.d_id <= a.d_id group by a.d_id, a.roll;

+------+-------------+
| roll | avg(b.roll) |
+------+-------------+
| 1 | 1.0000 |
| 2 | 1.5000 |
| 3 | 2.0000 |

| 4 | 2.5000 |
| 5 | 3.0000 |
| 6 | 3.5000 |
+------+-------------+
6 rows in set (0.00 sec)


Regards,

Mike Chirico

Reference (TIP 23)

http://osdn.dl.sourceforge.net/sourceforge/souptonuts/README_mysql.txt

[Mike Chirico]

Re: Virtuel-Counting-Row


"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:VwCmc.2716 7$Ut1.787960@bg tnsc05-news.ops.worldn et.att.net...[color=blue]
> "Mike Chirico" <mchirico@comca st.net> wrote in message
> news:L66dncvnK4 TEdAfdRVn-
>[color=green]
> > select a.name,sum(1) as mc
> > from student a, student b
> > where a.s_id <= b.s_id
> > group by a.s_id, a.name order by mc;[/color]
>
> That's pretty cool!
>[color=green]
> > Reference (TIP 22)
> > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color][/color]

It's also possible to compute running aggregates. Assume the following
table
and data:

CREATE TABLE dice (
d_id int(11) NOT NULL auto_increment,
roll int,
PRIMARY KEY (d_id)
);

insert into dice (roll) values (1);
insert into dice (roll) values (2);
insert into dice (roll) values (3);
insert into dice (roll) values (4);
insert into dice (roll) values (5);
insert into dice (roll) values (6);


The following gives a running, cumulative, sum:

mysql> select a.roll, sum(b.roll) from dice a, dice b
where b.d_id <= a.d_id group by a.d_id, a.roll;

+------+-------------+

| roll | sum(b.roll) |
+------+-------------+
| 1 | 1 |
| 2 | 3 |
| 3 | 6 |
| 4 | 10 |
| 5 | 15 |
| 6 | 21 |
+------+-------------+
6 rows in set (0.00 sec)


To get a running average change the
sum to avg as follows:


mysql> select a.roll, avg(b.roll) from dice a, dice b
where b.d_id <= a.d_id group by a.d_id, a.roll;

+------+-------------+
| roll | avg(b.roll) |
+------+-------------+
| 1 | 1.0000 |
| 2 | 1.5000 |
| 3 | 2.0000 |

| 4 | 2.5000 |
| 5 | 3.0000 |
| 6 | 3.5000 |
+------+-------------+
6 rows in set (0.00 sec)


Regards,

Mike Chirico

Reference (TIP 23)

http://osdn.dl.sourceforge.net/sourceforge/souptonuts/README_mysql.txt

[Siemel Naran]

Re: Virtuel-Counting-Row

"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:VwCmc.2716 7[color=blue]
> "Mike Chirico" <mchirico@comca st.net> wrote in message[/color]
[color=blue][color=green]
> > select a.name,sum(1) as mc
> > from student a, student b
> > where a.s_id <= b.s_id
> > group by a.s_id, a.name order by mc;
> >
> > Reference (TIP 22)
> > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]
>
> That's pretty cool![/color]

Instead of sum(1) you could use count(*).

What's the running time of the algorithm? Because it selects from 2 tables
it seems a O(N^2). If the system uses the index on s_id it can eliminate
the inner loop and immediately find the records of interest -- for example,
if driving by alias 'a', it can immediately find the records in alias 'b'
meeting the condition in the where clause. But it still has to loop through
these records in order to determine the count(*) or sum(1), because this
informations is (probably) not available in the index. Which makes it
O(N^2) still. Of course, if N is small as in the examples in this thread,
then it doesn't matter.

[Siemel Naran]

Re: Virtuel-Counting-Row

"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:VwCmc.2716 7[color=blue]
> "Mike Chirico" <mchirico@comca st.net> wrote in message[/color]
[color=blue][color=green]
> > select a.name,sum(1) as mc
> > from student a, student b
> > where a.s_id <= b.s_id
> > group by a.s_id, a.name order by mc;
> >
> > Reference (TIP 22)
> > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]
>
> That's pretty cool![/color]

Instead of sum(1) you could use count(*).

What's the running time of the algorithm? Because it selects from 2 tables
it seems a O(N^2). If the system uses the index on s_id it can eliminate
the inner loop and immediately find the records of interest -- for example,
if driving by alias 'a', it can immediately find the records in alias 'b'
meeting the condition in the where clause. But it still has to loop through
these records in order to determine the count(*) or sum(1), because this
informations is (probably) not available in the index. Which makes it
O(N^2) still. Of course, if N is small as in the examples in this thread,
then it doesn't matter.

[Mike Chirico]

Re: Virtuel-Counting-Row


"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:o1Pmc.5254 2$Xj6.884478@bg tnsc04-news.ops.worldn et.att.net...[color=blue]
> "Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
> news:VwCmc.2716 7[color=green]
> > "Mike Chirico" <mchirico@comca st.net> wrote in message[/color]
>[color=green][color=darkred]
> > > select a.name,sum(1) as mc
> > > from student a, student b
> > > where a.s_id <= b.s_id
> > > group by a.s_id, a.name order by mc;
> > >
> > > Reference (TIP 22)
> > > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]
> >
> > That's pretty cool![/color]
>
> Instead of sum(1) you could use count(*).
>
> What's the running time of the algorithm? Because it selects from 2[/color]
tables[color=blue]
> it seems a O(N^2). If the system uses the index on s_id it can eliminate
> the inner loop and immediately find the records of interest -- for[/color]
example,[color=blue]
> if driving by alias 'a', it can immediately find the records in alias 'b'
> meeting the condition in the where clause. But it still has to loop[/color]
through[color=blue]
> these records in order to determine the count(*) or sum(1), because this
> informations is (probably) not available in the index. Which makes it
> O(N^2) still. Of course, if N is small as in the examples in this thread,
> then it doesn't matter.
>[/color]
If I add 2,000,000 records into the dice table and take the sum of the last
10 records, which appears to be the worst case, it takes apx 47 seconds.
That's without indexes, and I agree it might not make a difference. For
some reason it doesn't seem to grow O(N^2); but, more like O(n) Log(n). I'm
not sure why.



mysql> select a.roll, sum(b.roll)
from dice a, dice b
where b.d_id <= a.d_id and a.roll > 1999990
and a.roll <= 2000000 group by a.d_id, a.roll;


+---------+---------------+
| roll | sum(b.roll) |
+---------+---------------+
| 1999991 | 1999983000036 |
| 1999992 | 1999985000028 |
| 1999993 | 1999987000021 |
| 1999994 | 1999989000015 |
| 1999995 | 1999991000010 |
| 1999996 | 1999993000006 |
| 1999997 | 1999995000003 |
| 1999998 | 1999997000001 |
| 1999999 | 1999999000000 |
| 2000000 | 2000001000000 |
+---------+---------------+
10 rows in set (46.93 sec)

Or, with count it's about the same.

select a.roll, count(b.roll) from dice a, dice b
where b.d_id <= a.d_id
and a.roll > 1999990 and a.roll <= 2000000 group by a.d_id, a.roll;

+---------+---------------+
| roll | count(b.roll) |
+---------+---------------+
| 1999991 | 1999991 |
| 1999992 | 1999992 |
| 1999993 | 1999993 |
| 1999994 | 1999994 |
| 1999995 | 1999995 |
| 1999996 | 1999996 |
| 1999997 | 1999997 |
| 1999998 | 1999998 |
| 1999999 | 1999999 |
| 2000000 | 2000000 |
+---------+---------------+
10 rows in set (47.51 sec)


Still with 2 million records in the table; but, only selecting between 500
and 510 it takes < 1 sec.

select a.roll, count(b.roll) from dice a, dice b
where b.d_id <= a.d_id
and a.roll > 500 and a.roll <= 510 group by a.d_id, a.roll;
+------+---------------+
| roll | count(b.roll) |
+------+---------------+
| 501 | 501 |
| 502 | 502 |
| 503 | 503 |
| 504 | 504 |
| 505 | 505 |
| 506 | 506 |
| 507 | 507 |
| 508 | 508 |
| 509 | 509 |
| 510 | 510 |
+------+---------------+
10 rows in set (0.80 sec)



Interesting note...creating the text file of insert statements took too long
with a "for loop in a bash script".. I had to use a C program, which took
only 3 seconds

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>

#include <string.h>/* for strerror(int errno) */
#include <errno.h>


int main()
{
long int i;
char buf[50+1];
int fd;

if ((fd = open ("data.sql", O_RDWR | O_CREAT, 0600)) == -1)
{
fprintf (stderr, "Can't open data: %s\n", strerror (errno));
return 1;
}


for(i=1; i <= 2000000; ++i)
{
snprintf(buf,50 ,"insert into dice (roll) values (%ld);\n",i);
write (fd, buf, strlen (buf));
}

close(fd);
return 0;
}


Regards,

Mike Chirico

[Mike Chirico]

Re: Virtuel-Counting-Row


"Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
news:o1Pmc.5254 2$Xj6.884478@bg tnsc04-news.ops.worldn et.att.net...[color=blue]
> "Siemel Naran" <SiemelNaran@RE MOVE.att.net> wrote in message
> news:VwCmc.2716 7[color=green]
> > "Mike Chirico" <mchirico@comca st.net> wrote in message[/color]
>[color=green][color=darkred]
> > > select a.name,sum(1) as mc
> > > from student a, student b
> > > where a.s_id <= b.s_id
> > > group by a.s_id, a.name order by mc;
> > >
> > > Reference (TIP 22)
> > > http://osdn.dl.sourceforge.net/sourc...ADME_mysql.txt[/color]
> >
> > That's pretty cool![/color]
>
> Instead of sum(1) you could use count(*).
>
> What's the running time of the algorithm? Because it selects from 2[/color]
tables[color=blue]
> it seems a O(N^2). If the system uses the index on s_id it can eliminate
> the inner loop and immediately find the records of interest -- for[/color]
example,[color=blue]
> if driving by alias 'a', it can immediately find the records in alias 'b'
> meeting the condition in the where clause. But it still has to loop[/color]
through[color=blue]
> these records in order to determine the count(*) or sum(1), because this
> informations is (probably) not available in the index. Which makes it
> O(N^2) still. Of course, if N is small as in the examples in this thread,
> then it doesn't matter.
>[/color]
If I add 2,000,000 records into the dice table and take the sum of the last
10 records, which appears to be the worst case, it takes apx 47 seconds.
That's without indexes, and I agree it might not make a difference. For
some reason it doesn't seem to grow O(N^2); but, more like O(n) Log(n). I'm
not sure why.



mysql> select a.roll, sum(b.roll)
from dice a, dice b
where b.d_id <= a.d_id and a.roll > 1999990
and a.roll <= 2000000 group by a.d_id, a.roll;


+---------+---------------+
| roll | sum(b.roll) |
+---------+---------------+
| 1999991 | 1999983000036 |
| 1999992 | 1999985000028 |
| 1999993 | 1999987000021 |
| 1999994 | 1999989000015 |
| 1999995 | 1999991000010 |
| 1999996 | 1999993000006 |
| 1999997 | 1999995000003 |
| 1999998 | 1999997000001 |
| 1999999 | 1999999000000 |
| 2000000 | 2000001000000 |
+---------+---------------+
10 rows in set (46.93 sec)

Or, with count it's about the same.

select a.roll, count(b.roll) from dice a, dice b
where b.d_id <= a.d_id
and a.roll > 1999990 and a.roll <= 2000000 group by a.d_id, a.roll;

+---------+---------------+
| roll | count(b.roll) |
+---------+---------------+
| 1999991 | 1999991 |
| 1999992 | 1999992 |
| 1999993 | 1999993 |
| 1999994 | 1999994 |
| 1999995 | 1999995 |
| 1999996 | 1999996 |
| 1999997 | 1999997 |
| 1999998 | 1999998 |
| 1999999 | 1999999 |
| 2000000 | 2000000 |
+---------+---------------+
10 rows in set (47.51 sec)


Still with 2 million records in the table; but, only selecting between 500
and 510 it takes < 1 sec.

select a.roll, count(b.roll) from dice a, dice b
where b.d_id <= a.d_id
and a.roll > 500 and a.roll <= 510 group by a.d_id, a.roll;
+------+---------------+
| roll | count(b.roll) |
+------+---------------+
| 501 | 501 |
| 502 | 502 |
| 503 | 503 |
| 504 | 504 |
| 505 | 505 |
| 506 | 506 |
| 507 | 507 |
| 508 | 508 |
| 509 | 509 |
| 510 | 510 |
+------+---------------+
10 rows in set (0.80 sec)



Interesting note...creating the text file of insert statements took too long
with a "for loop in a bash script".. I had to use a C program, which took
only 3 seconds

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>

#include <string.h>/* for strerror(int errno) */
#include <errno.h>


int main()
{
long int i;
char buf[50+1];
int fd;

if ((fd = open ("data.sql", O_RDWR | O_CREAT, 0600)) == -1)
{
fprintf (stderr, "Can't open data: %s\n", strerror (errno));
return 1;
}


for(i=1; i <= 2000000; ++i)
{
snprintf(buf,50 ,"insert into dice (roll) values (%ld);\n",i);
write (fd, buf, strlen (buf));
}

close(fd);
return 0;
}


Regards,

Mike Chirico

[Siemel Naran]

Re: Virtuel-Counting-Row

"Mike Chirico" <mchirico@comca st.net> wrote in message
news:vr2dnefdF_ XNUQbdRVn-
[color=blue]
> If I add 2,000,000 records into the dice table and take the sum of the[/color]
last[color=blue]
> 10 records, which appears to be the worst case, it takes apx 47 seconds.
> That's without indexes, and I agree it might not make a difference. For
> some reason it doesn't seem to grow O(N^2); but, more like O(n) Log(n).[/color]
I'm[color=blue]
> not sure why.[/color]

Maybe the running time is A*N^2+B*N*lg(N) , and only for really large N, like
2 trillion it might be N^2. Just guessing.

Anyway, thanks for the long reply. I am curious as to how you got these SQL
timings. Is there some kind of clock function in MySql?
[color=blue]
> mysql> select a.roll, sum(b.roll)
> from dice a, dice b
> where b.d_id <= a.d_id and a.roll > 1999990
> and a.roll <= 2000000 group by a.d_id, a.roll;[/color]

We should compare the running time to the O(N) algorithm, which probably
means SQL cursors or the temporary table idea, but SQL cursors are only in
in MySql 5.0.

Anyway, it's clear that for most reasonable values, the method is fast.

[color=blue]
> #include <fcntl.h>[/color]

[OT] Is the above UNIX specific, and defines the open function?

[Siemel Naran]

Re: Virtuel-Counting-Row

"Mike Chirico" <mchirico@comca st.net> wrote in message
news:vr2dnefdF_ XNUQbdRVn-
[color=blue]
> If I add 2,000,000 records into the dice table and take the sum of the[/color]
last[color=blue]
> 10 records, which appears to be the worst case, it takes apx 47 seconds.
> That's without indexes, and I agree it might not make a difference. For
> some reason it doesn't seem to grow O(N^2); but, more like O(n) Log(n).[/color]
I'm[color=blue]
> not sure why.[/color]

Maybe the running time is A*N^2+B*N*lg(N) , and only for really large N, like
2 trillion it might be N^2. Just guessing.

Anyway, thanks for the long reply. I am curious as to how you got these SQL
timings. Is there some kind of clock function in MySql?
[color=blue]
> mysql> select a.roll, sum(b.roll)
> from dice a, dice b
> where b.d_id <= a.d_id and a.roll > 1999990
> and a.roll <= 2000000 group by a.d_id, a.roll;[/color]

We should compare the running time to the O(N) algorithm, which probably
means SQL cursors or the temporary table idea, but SQL cursors are only in
in MySql 5.0.

Anyway, it's clear that for most reasonable values, the method is fast.

[color=blue]
> #include <fcntl.h>[/color]

[OT] Is the above UNIX specific, and defines the open function?