Wednesday, December 19, 2007

Pop quiz (with prize): generate 4 billion records

My latest quiz was quite popular, and some interesting ideas were submitted.
There was an interesting development. A colleague called and asked me for advice on how to insert 4 billion rows in a table with a simple structure.
create table t1 (
id tinyint not null
);
Very simple. No primary key, no indexes. It is needed to perform some specific tests.
Actually, not 4 billion, but 2^32 records are needed, i.e. 4,294,967,296.
The classical method used in these cases is doubling the table contents:

insert into t1 values (1),(1),(1),(1),(1),(1),(1),(1);
insert into t1 select * from t1;
insert into t1 select * from t1; # and so on
My solution was similar to the one from my quiz.
CREATE VIEW `v4` AS
select NULL
union all select NULL
union all select NULL
union all select NULL;

CREATE VIEW v1024 AS
select null from v4 a, v4 b, v4 c, v4 d, v4 e;

INSERT INTO t1 select 1 from v1024 a, v1024 b, v1024 c, v4 ;
This one is faster than the doubling method, but it still requires from 40 to 65 minutes, depending on how fast is your server.
So, the challenge, for which we will give away 1 MySQL T-shirt to the winner, is as following:
  • Generate 2^32 records for table t1;
  • no limits to the length of code to use;
  • you can use stored routines, temporary tables, views, events, whatever makes the insertion fast;
  • the method must be portable across operating systems. If it is not portable, a Unix-only method may be accepted if it is exceptionally faster than SQL-only solutions;
  • methods relying on external applications cannot be accepted;
  • If an programming language is needed, for compatibility with the test suite we can only accept Bash shell or Perl scripts;
  • If you devise a fast method to insert data using MySQL Proxy, a Lua script can be accepted.
  • what matters is the final insertion speed and ease of use.
  • If a method uses an external script, its speed must be more than 20% faster than the fastest method using only SQL.
  • The speed will be calculated on my server, using MySQL 5.1.23.

Solutions so far

  • Dpin. 20 minutes for a portable solution is very good.
  • Jedy. Very nice, but not that fast. 32 minutes.
  • Todd. Brilliant solution (10 minutes for 4 billion rows!), but really impractical. We need something that works for any engine. This one is a dirty trick that is fun to use once, but in the long run it won't stand.

10 comments:

Todd said...

Here's a Perl script to generate a big table -- usage example:

mysql> create table t1 (id tinyint not null);
mysql> flush tables;


then run the following script with the first argument being 2^32 and the second argument being the path to mysql/data/t1.frm.

After it completes, the table will have 2^32 "1"s in it, and it should be essentially limited by IO speed. Changing the CHUNK_REPEAT variable may result in increased performance - I didn't tune it.

#!/usr/bin/perl
use strict;
use warnings;
use Math::BigInt qw/:constant/;
use bignum;

my $SIZE_PER_ROW = 7;
my $CHUNK_REPEAT = 1024;
my $MYI_DATA = "
0000000 fefe 0701 0000 0122 00b0 0064 00b0 0000
0000010 0000 0000 0800 0000 0000 19ff {COUNT}
0000020 0000 0000 0000 0000 {COUNT}
0000030 ffff ffff ffff ffff 0000 0000
0000040 0000 0400 {MYD_SIZE} 0000 0000
0000050 0000 0000 0000 0000 0000 0000 0000 0000
0000060 0000 0000 0000 0000 0000 0000 0000 022d
0000070 0000 0016 0000 0000 0000 0038 0000 0000
0000080 0000 0000 4769 466d 0000 0000 0000 0000
0000090 0000 0000 4769 466d 0000 0000 0000 0000
00000a0 0000 0000 0000 0000 0000 0000 0000 0000
00000b0 0000 0000 0000 0400 0000 0000 0000 0000
00000c0 0000 0000 0000 0000 0000 0000 0000 0000
00000d0 0000 0000 0000 0000 0000 0000 0000 0002
00000e0 0000 0007 0000 0002 0000 0002 0000 0014
00000f0 0000 0002 0000 0000 0603 0000 0000 0000
0000100 0000 0008 0000 0000 0000 0000 0000 0000
0000110 0000 0000 0000 0001 0000 0000 0000 0100
0000120 0000 0000 0000 0000 0000 0000 0000 0000
0000130 0000 0000 0000 0000 0000 0000 0000 0000
0000140 0000 0000 0000 0000 0000 0000 0000 0000
0000150 0000 0000 0000 0000 0000 0000 0000 0000
0000160 0000 0000 0000 0000 0000 0000 0000 0000
0000170 0000 0000 0000 0000 0000 0000 0000 0000
0000180 0000 0000 0000 0000 0000 0000 0000 0000
0000190 0000 0000 0000 0000 0000 0000 0000 0000
00001a0 0000 0000 0000 0000 0000 0000 0000 0000
00001b0 0000 0000 0000 0000 0000 0000 0000 0000
00001c0 0000 0000 0000 0000 0000 0000 0000 0000
00001d0 0000 0000 0000 0000 0000 0000 0000 0000
00001e0 0000 0000 0000 0000 0000 0000 0000 0000
00001f0 0000 0000 0000 0000 0000 0000 0000 0000
0000200 0000 0000 0000 0000 0000 0000 0000 0000
0000210 0000 0000 0000 0000 0000 0000 0000 0000
0000220 0000 0000 0000 0000 0000 0000 0000 0000
0000230 0000 0000 0000 0000 0000 0000 0000 0000
0000240 0000 0000 0000 0000 0000 0000 0000 0000
0000250 0000 0000 0000 0000 0000 0000 0000 0000
0000260 0000 0000 0000 0000 0000 0000 0000 0000
0000270 0000 0000 0000 0000 0000 0000 0000 0000
0000280 0000 0000 0000 0000 0000 0000 0000 0000
0000290 0000 0000 0000 0000 0000 0000 0000 0000
00002a0 0000 0000 0000 0000 0000 0000 0000 0000
00002b0 0000 0000 0000 0000 0000 0000 0000 0000
00002c0 0000 0000 0000 0000 0000 0000 0000 0000
00002d0 0000 0000 0000 0000 0000 0000 0000 0000
00002e0 0000 0000 0000 0000 0000 0000 0000 0000
00002f0 0000 0000 0000 0000 0000 0000 0000 0000
0000300 0000 0000 0000 0000 0000 0000 0000 0000
0000310 0000 0000 0000 0000 0000 0000 0000 0000
0000320 0000 0000 0000 0000 0000 0000 0000 0000
0000330 0000 0000 0000 0000 0000 0000 0000 0000
0000340 0000 0000 0000 0000 0000 0000 0000 0000
0000350 0000 0000 0000 0000 0000 0000 0000 0000
0000360 0000 0000 0000 0000 0000 0000 0000 0000
0000370 0000 0000 0000 0000 0000 0000 0000 0000
0000380 0000 0000 0000 0000 0000 0000 0000 0000
0000390 0000 0000 0000 0000 0000 0000 0000 0000
00003a0 0000 0000 0000 0000 0000 0000 0000 0000
00003b0 0000 0000 0000 0000 0000 0000 0000 0000
00003c0 0000 0000 0000 0000 0000 0000 0000 0000
00003d0 0000 0000 0000 0000 0000 0000 0000 0000
00003e0 0000 0000 0000 0000 0000 0000 0000 0000
00003f0 0000 0000 0000 0000 0000 0000 0000 0000
0000400
";

my $MYD_DATA = "ff010000000000";

if (scalar @ARGV != 2) {
die "usage: $0 num frmpath";
}

my ($num_str, $frm_path) = @ARGV;

my $num = Math::BigInt->new($num_str);

die "frm not found" unless -e $frm_path;
die "bad extension on $frm_path" unless $frm_path =~ /\.frm$/;

my $myd_path = $frm_path;
$myd_path =~ s/frm$/MYD/;
die "myd not found" unless -e $myd_path;

my $myi_path = $frm_path;
$myi_path =~ s/frm$/MYI/;
die "myi not found" unless -e $myi_path;

&make_myd($myd_path, $num);
&make_myi($myi_path, $num);

sub make_myi {
my ($out, $num_records) = @_;

open(OUT, ">$out") or die "Couldnt open $out: $!";
binmode OUT;

my $num_hex = $num_records->as_hex();
$num_hex =~ s/^0x//;
$num_hex = sprintf("%016s", $num_hex);

my $size_hex = ($num_records * $SIZE_PER_ROW)->as_hex();
$size_hex =~ s/^0x//;
$size_hex = sprintf("%016s", $size_hex);

my @lines = split("\n", $MYI_DATA);
s/^\S+// for @lines;
chomp(@lines);
s/\s//g for @lines;
my $data = join("", @lines);

$data =~ s/{COUNT}/$num_hex/g;
$data =~ s/{MYD_SIZE}/$size_hex/g;
print OUT pack("H*", $data);
close(OUT);
}

sub make_myd {
my ($out, $num_records) = @_;
open(OUT, ">$out") or die "Couldnt open $out: $!";
binmode OUT;

my ($chunks, $remainder) = $num_records->bdiv($CHUNK_REPEAT);
$chunks = $chunks->bfloor();
print STDERR "chunks: $chunks rem: $remainder\n";

my $chunk = pack("H*", $MYD_DATA) x $CHUNK_REPEAT;

for (1..$chunks) { print OUT $chunk; }
for (1..$remainder) { print OUT pack("H*", $MYD_DATA); }
close(OUT);
}

Dirk1231 said...

Is the table InnoDb or MyIsam?

Giuseppe Maxia said...

The table is MyISAM in this particular case, but the test should be available for any engine.

Giuseppe Maxia said...

Todd,
Thanks.
Your solution is amazing, because it fills a table in 1 fourth of the time. However, this is not really useful for me. The fact that it is performed outside the server makes this solution difficult to integrate with the rest of the work that requires this task.
Moreover, this is only applicable to MyISAM tables, while I would need to insert these records in different engines.
Can you find a more general method?

Unknown said...

I suspect that generating a large input file then using "load data infile" to import it is going to be the fastest method.

If you want pure SQL (well, pure MySQL anyway), stored function performing a bulk insert seems to be fairly quick, but it then becomes a trade off between generating such a function, and time to run it.

Something like:
CREATE FUNCTION `repeats`(x int) RETURNS int(11)
begin
set @i = 0;
repeat
insert into t1(id) values (1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4),(1),(2),(3),(4);
set @i = @i+1;
until @i >= x
end repeat;
return 0;
end

(256 values being inserted for each iteration) managed 256000 values in between 2 and 3 seconds (my MySQL install is in a virtual machine with limited memory, so I didn't want to go for the full 4billion!).

Of course, you could combine that with inserting a cross product: insert into t1(id) select a.id from t2 as a, t2 as b, t2 as c, t2 as d after a single 256 element insert to t2 (identical structure to t1) should give you the right number of records, but I'm not running that on my server...

Todd said...

More general method: my above method + "ALTER TABLE"?

Or is that also cheating? :)

Another idea is to use a script to write into a fifo and use LOAD DATA INFILE on the fifo, but I bet it's not as fast.

jedy said...

It need to create temporary table to insert from view. We can create a table to avoid this. It may save about half of the time.

create table t2 (
id tinyint not null
) engine=memory;
insert into t2 select 1 from v1024 a, v1024 b;
delimiter //
create procedure insert_t1 (n int)
begin declare i int default 0;
prepare sth from "insert into t1 select * from t2";
while i < n do
execute sth;
set i = i + 1;
end while;
end//
delimiter ;
call insert_t1(1024);

On my server, this took about 6.5 minutes to insert 1 billion records. So maybe half an hour for 4 billion.

Unknown said...

Your sample solution takes about 1 hour and 18 minutes on my machine.

The following takes about 22 minutes on the same machine.

-Dipin

create table t2 (
id tinyint not null
) engine=memory;

insert into t2 values (1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1);

insert into t2 select 1 from t2 a, t2 b, t2 c, t2 d limit 65520;

insert into t1 select 1 from t2 a, t2 b;

drop table t2;

Dirk1231 said...

I think the fastest way is going to be to create the MYD file using the dd command to repeat a hex pattern. Then take the existing MYI file and modify the needed pieces in a hex editor. I have part of the solution for this, but not enough time to complete it this week.

Giuseppe Maxia said...

dirk1231,
Don't bother with the dd solution.
It is only valid for MyISAM tables, and thus not very valuable.
Besides, as for Todd's solution, there is risk of data corruption.
So, I must rule out this one.