How To Choose The Right Database?

[davidktw]

@peterchan75

Let me show you how I traverse a 739MB data file

$ ls -alh data.txt
-rw-r--r--  1 davidktw  staff   739M Dec 23 21:47 data.txt

that is generated using the following perl script

perl -e '$i=10000000; while ($i-- > 0) { print "a","x"x(rand(50)+50),"z\n"}' > data.txt

Each line is randomly between 50 to 99 characters.
There are a total of 10M lines. I think should be way more than what you normally deal with.

Below is a sample of the data file

$ head data.txt
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz

You will notice all the lines start with 'a' and ends with 'z', for ease of reading to know we are
always reading line by line in the code

Lets show you the demonstration perl script that generate the index file as well as reading randomly from the data file using the index file

#!/usr/bin/env perl

use strict;
use warnings;

#########################################################
# THIS IS THE PERL COMMAND TO CREATE THE RANDOM DATA FILE
#########################################################
#perl -e '$i=10000000; while ($i-- > 0) { print "a","x"x(rand(50)+50),"z\n"}' > data.txt

my $datafh;
my $idxfh;

#######################################################
# THIS IS THE PART WHERE THE INDEX IS CREATED
#######################################################
open $datafh, "<data.txt";
open $idxfh, ">data.txt.index";
my $totallines = 1;
printf $idxfh "%20d\n",tell($datafh);
while (<$datafh>) {
  if (! eof $datafh) {
    printf $idxfh "%20d\n",tell($datafh);
    $totallines++;
  }
}
printf $idxfh "%20d\n",$totallines;
close($idxfh);
close($datafh);

#######################################################
# THIS IS THE PART THERE THE DATA FILE IS RANDOMLY READ
#######################################################
# open $datafh, "<data.txt";
# open $idxfh, "<data.txt.index";
# # first read the last field from the index file
# # because it contains the total number of index elements
# seek $idxfh, -21, 2;
# my $totalindices = <$idxfh>;
#
# for (my $i = 0; $i < 1000000; $i++) {
#   my $randomidx = int(rand($totalindices));
#   seek $idxfh, $randomidx * 21, 0;
#   my $dataidx;
#   read $idxfh, $dataidx, 20;
#   print $dataidx, " : ";
#   seek $datafh, $dataidx, 0;
#   print scalar(<$datafh>);
# }

In the code above, only the index generation part is uncommented.
Lets see how long it takes on my system to generate the index file

$ time ./indexfile.pl

real	0m6.819s
user	0m6.094s
sys	0m0.495s

Roughly 6.8s is all that is needed and this has to be done once for the data file only.
As long as your data file doesn't change, the index file doesn't need to change too,

Now lets comment away the index generation, uncomment the randomly reading of 1M random parts of the data file
and see how long it takes when the stdout is piped to /dev/null.
We need to do this so that the stdout latency wouldn't be counted into the timing.
We just want to know the how long 1M reading from index and then reading from the data file takes

$ time ./indexfile.pl >/dev/null

real	0m10.367s
user	0m4.276s
sys	0m5.907s

That's fast isn't it ? You can also see that the user time and sys time is kinda 50% split, that is roughly the weightage of seeking because
it is a system call and it is majority of the work here. Of course there are other I/Os like reading from the file, but you can see in earlier runs
of the perl script, the system calls are normally not dominating. Still consider we are dealing with a 700+MB file with 10M of lines,
this is not shabby at all.

Now lets just print out 10 random lines and see if it's working properly

$ time ./indexfile.pl
           235358649 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           487916858 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           574440216 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           499231466 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           715600555 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           428059905 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           525397232 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           163018405 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           298943851 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
           699295008 : axxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz

real	0m0.019s
user	0m0.007s
sys	0m0.005s

Notice all the lines printed start with 'a' and ends with 'z', so we are good.
The code is randomly jumping across the entire file, hence cache locality is least in play here unless the entire 700MB can fit into the memory which is possible for my 16GB system.

So there you go, a technique you can use to access records in a data file.
For your information, I learnt file indexing technique back in my JC days while studying computing. That's how I manage file base storage for an inventory system project written in Pascal.

Nowadays the new age "software developers" only know how to use databases which ain't too good at it too. I have so far hardly deal with software engineers that know how to manage
files other than reading/writing them using libraries like properties/configuration readers or other sort of libraries. So what I have shown is very raw way of accessing
unstructured file of arbitrary lengths like records using index.

In more sophisticated records management. Each record could be a C structure, or Pascal Record, or Java object, or Javascript JSON string. There are so many ways of playing with files
like just heap memory. You can just write a HEAP TREE, HASH TABLE, BINARY TREE into the file and manage it. That's how database are created, isn't it ?

UPDATED:
Code using 8 bytes (64bits) binary for the indices file. This will shrink down the index file from 21 bytes per index to 8 bytes per index meaning roughly 38% in size vs the original index file.

#!/usr/bin/env perl

use strict;
use warnings;

#########################################################
# THIS IS THE PERL COMMAND TO CREATE THE RANDOM DATA FILE
#########################################################
#perl -e '$i=10000000; while ($i-- > 0) { print "a","x"x(rand(50)+50),"z\n"}' > data.txt

my $datafh;
my $idxfh;

#######################################################
# THIS IS THE PART WHERE THE INDEX IS CREATED
#######################################################
# open $datafh, "<data.txt";
# open $idxfh, ">data.txt.index";
# my $totallines = 1;
# print $idxfh pack('Q', tell($datafh));
# while (<$datafh>) {
#   if (! eof $datafh) {
#     print $idxfh pack('Q', tell($datafh));
#     $totallines++;
#   }
# }
# print $idxfh pack('Q', $totallines);
# close($idxfh);
# close($datafh);

#######################################################
# THIS IS THE PART THERE THE DATA FILE IS RANDOMLY READ
#######################################################
open $datafh, "<data.txt";
open $idxfh, "<data.txt.index";
# first read the last field from the index file
# because it contains the total number of index elements
seek $idxfh, -8, 2;
my $totalindices;
read $idxfh, $totalindices, 8;
$totalindices = unpack('Q', $totalindices);

for (my $i = 0; $i < 1000000; $i++) {
  my $randomidx = int(rand($totalindices));
  seek $idxfh, $randomidx * 8, 0;
  my $dataidx;
  read $idxfh, $dataidx, 8;
  $dataidx = unpack('Q', $dataidx);
  print $dataidx, " : ";
  seek $datafh, $dataidx, 0;
  print scalar(<$datafh>);
}

Fun for you ?