1

The task:
I have a database with 4 tables with 200 rows, 800 rows, 50 rows and 30 rows respectively.
Just to simplify it, let's assume the tables are these sets:
A = [Ar1, Ar2, Ar3], B = [Br1, Br2], C = [Cr1, Cr2, Cr3], D = [Dr1, Dr2, Dr3, Dr4], where Ar1 means row1 of table A.

There is also a 5th table "E" with 250 rows which contains some information which is relevant to tables A, B, C and D.

For every combination of AB, ABC and ABCD, I'm required to check all rows of E to see if there is some information relevant to the combination, and store a count of the relevant info. The count will be eventually written into an SQL table.

Eg: The combinations of AB would be:
{Ar1, Br1}, {Ar1, Br2}, {Ar2, Br1}, {Ar2, Br2}, {Ar3, Br1}, {Ar3, Br2}
So I have to check

forAllRowsOfE
{    
if (row 1 of E == content of Ar1 and row1 of E <= content of Br1) then {var Ar1Br1++;}
}

and run the above for loop for all other combinations of A and B. Then also run it for combinations of ABC (for which it'd be {Ar1, Br1, Cr1}, {Ar2, Br1, Cr1}...and so on... and for combinations of ABCD).

The size:
The total number of combinations for the A,B,C and D tables itself comes upto 200*800*50*30 = 240 million.

The problem:
Running 240million * 5 queries, even if it takes 0.01s per query will take 138days to execute. The tables are small now. I'm expecting them to grow much much larger.

I've been advised to load these tables into the memory of a Java program and to do the computation in Java, because many of the count combinations of AB will be repeated in the combinations of ABC, so that much brute-force counting can be avoided. The other reason is that all this data might actually fit into 6GB RAM, and when the size increases, we could search for other techniques like temporarily writing to a database table etc.

The questions:

  • But the main question here is, is it really more viable/faster to perform such operations in Java memory?
  • Is the usage of nested loops really the better way to tackle this or are there other techniques/queries?
  • 5
    240 million isn't that big of a number... unless you are doing things one at a time. Given the database schema information, it may be more practical to look into writing the appropriate SQL query to let the database do all the work in one pass. – user40980 Feb 16 '16 at 16:39
  • Where are go going to store the results? In table E? Or in a table having 1 row for each combination ABCD? The interesting point here is how big is your result set? – Doc Brown Feb 16 '16 at 16:42
  • @MichaelT: In one pass? Really? I didn't picture that being possible. There is a variety of columns in table E. 240 million is just the start. There's plenty more data that's going to come in later, which is why I'm wondering if it really is better to do the counting in SQL or to take the data into Java and work on it there. – Nav Feb 16 '16 at 17:24
  • 2
    Hard to say from the information here, but the main problem may be the idea of running 240M * 5 queries. That suggests that you may be mostly searching for information which is not present. It seems that sorting and aggregating E may be all that's needed. But we don't know how large E will be, and we don't know if this is needed as a single batch process or a series of real-time requests. If the result can be achieved by sorting and aggregating counts from E, it may take quite some time to write java that does this as fast as a good database. Maybe this is another XY Problem. – joshp Feb 16 '16 at 17:38
  • 3
    To be honest, I strongly get the feeling that the solution to the larger problem you are solving here, has not been thought through very well. Why are there so many combinations between 4 tables and why is there another table that seems to contain metadata (E)? Before you go on, have you considered the actual problem that has to be solved rather than the task at hand? – MarioDS Feb 16 '16 at 18:29
4

"Is it viable to copy contents ... into a program's memory"

"Viable"? Of course, the technique is called caching and I am sure you have heard of it. However, you should invest some thoughts into things like

  • is the memory available in full, in the production environment, exclusively for your program?

  • what will happen when the table size is going to grow, as you said? For example, can you effectivly split the data into portions which can be processed in-memory at once?

Will it be faster than other approaches? There is no other good way than to try this out and measure, it depends on a bunch of things we do not know, and maybe some things even you don't know yet. Consider to start with a smaller dataset and extrapolate.

However, sending 1,2 billions of single queries does not look too promising, and as a rule of thumb, doing things "in memory" are typically much faster then doing "equivalent things" on an external storage medium, with a database management in between. Depending on the kind of queries, you can try to utilize the indexing capabilities of your database, which might improve things on that side. On the other hand, if indexing is possible in your database, using hashes/dictionaries might be possible in-memory, too.

After reading your comment, storing of the results looks to me like a candidate for a bottleneck. Even if you can query the full data from those five tables A-E in less than a second, do the main processing completely in memory, and it turns out to be faster then any other approach you come up with, you finally need to create these 240 millions rows, which will take some time. Things to consider here:

  • when you do things "in-memory", does that mean you will have to send the data back over a (potentially slow) network to the database server? Or do you use something like a local database, where the program + db reside on the same machine?

  • assumed network traffic becomes a problem: what about using stored procedures to reduce network traffic? What about using a huge JOIN over the tables A,B,C,D,E with some aggregate function? Did you try out how well this works?

  • when doing the processing not in-memory, does that mean you need 240 mio INSERT operations, followed by 240 mio * n UPDATE operations? That might become slow.

  • or will the in-memory preprocessing allow you to find the results first, and then transfer it "all-at-once" back to the database using some kind of bulk insert mechanism?

Nevertheless in the end, in-memory or not, it boils down to the specific database available, the network, the hardware, lots of details of the task, and the implementation you choose, nothing which can be evaluated here without knowing the "real thing".

0

For every combination of AB, ABC and ABCD, I'm required to check all rows of E to see if there is some information relevant to the combination, and store a count of the relevant info. The count will be eventually written into an SQL table.

Actually, this sounds (to me) more like a job for your database to do, without bringing anything back into the client application!

You're "every row combined with every other" is a Cartesian (or Cross-Product) Join and should generally be avoided because of the [hideously] huge numbers of tuples that it can generate but, in this case, you explicitly say that's what you want so give your database server lots (and lots) of memory and swap space (and a fresh cup of really hot tea) and let it go.

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.