1

I'm new here so I'm not entirely sure what tags to use so please notify/edit if this should be changed, thanks!

Background
I have a graph with ~4 billion nodes and ~1 trillion edges that I want to store in a database (like sqlite) as in this way data can be inserted on the hard disk rather than in RAM as many other graph data structures require.

Data format
This graph format looks like:

accession node position orientation 
23101.1   1    1        plus
23101.1   100  2        plus
...
23101.1   100  1        min
...
~1trillion

The plan
I think of creating TABLES for accession, node, and orientation that I will refer to using foreign keys. So then the "main" table will be

accession node  position orientation 
<FK1>     <FK2> 1        <FK3>

(P.s. not sure if I should do if for the position too, but this will simply be 1 till graph-path-length).

The question
I only have little knowledge of SQL but based on code like this I would have to execute something like the code below for each line in the graph file:

    INSERT INTO main (accession, node, position, orientation) VALUES
        ( SELECT id from accessions WHERE accession=23101.1,
          SELECT id from nodes WHERE node=1,
          1,
          1
);

and also catch an error when the node/accession does not exist and insert it. However, I wonder whether obtaining the foreign keys with the SELECT .. WHERE will not get really slow when they are billions of rows in the table? So overall, what would be a proper way to store this information in the database (if at all)?

Improve this question
  • I'd suggest looking at graph databases for what is the dominate aspect of your application. They have a specific syntax that is more applicable to the problem domain of graphs. While it can be done in SQL (recursive CTEs) it won't be as good a more relevant product. – danblack Jan 12 at 22:41
  • The syntax you have won't work. A trillion edges won't fit in RAM unless you have a many terabytes of RAM. Show more than 3 samples. What queries will you perform on the data? If it involves walking through a trillion edges, that will take days. Even a billion edges won't be "fast". – Rick James Jan 13 at 0:49
  • 1
    @danblack thanks! are you referring to something like Neo4J? – CodeNoob Jan 13 at 8:38
  • @RickJames Wouldn't it be written to the hard disk when I would commit after every X rows, or does it need to load in RAM anyway? Queries will be 1) Select all accessions where node = X and 2) indeed a walk type of thing where we start from a specified node, so e.g. first query (1) and then Select all where accession in (1) and position within range(X) – CodeNoob Jan 13 at 8:44
  • What exactly are you storing? I'm not seeing anything here that screams "graph!", and whenever I see "I have X billion of this and Y trillion of this" I immediately default to: "The data probably isn't stored properly". – bbaird Jan 13 at 15:27
1

Column < Row < Block < Table

One column had a number, date, string, or a small number of other possibilities. It takes a few bytes or many bytes.

One row like you described (4 columns each taking a few bytes) will take perhaps 40 bytes when you add in some overhead.

One block is 16KB and holds (in your case) a few hundred rows. I mention a block because it is the unit of caching in InnoDB tables. All activity is done on blocks in RAM. If an operation needs to work on the rows in a block but that block is not in RAM, it will be brought into RAM, possibly pushing out some other block. (Read about "caching".)

One table is composed of as many blocks as are needed -- billions in your case!

So,... because of caching those billions of blocks can be handled. But with a lot of I/O.

I am assuming you need one row to describe one edge. And probably another table with nodes -- and 4 billion rows in that table.

These are huge numbers. Am I misinterpreting the number of edges and nodes? What do you expect to walk through all the edges for some operation? If so, let's see...

  • 40TB in edge table;
  • 2.5 billion blocks, each needing to be read at least once;
  • SSD drive that can handle 1K reads/second;
  • 2.5 million seconds to read all edges once;
  • That's about 1 month.

Somethin's gotta give!

Improve this answer
  • Spot on, indeed a "row" should be an edge that indeed should be linked to a "node" table. The "main" question, for which we would walk the graph, is finding paths (i.e. node1>node2>node3) present for multiple accessions. We would do this using matrix operations but terabytes of matrix also are not easy to work with hahah. Thanks for the insight! – CodeNoob Jan 14 at 8:30
  • @CodeNoob - A matrix with one bit per pair of nodes -- That adds up to 2 exabytes for 4 billion nodes. You will not find a machine with that much RAM or even that much disk. Focus on the algorithm. And good luck. – Rick James Jan 14 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.