Hi Bryan,
About DERBY-3892: The problem i faced while testing is because, in Netbeans i did not add the jdbc library before testing it.I used the attachment you gave Main_Updated.java .So now i got good results. I like to show you some of my results i got during my analysis,
  Rows         Insertion time(s)      Querying time(s)
     100             2.281                       2.346
    1000            3.31                         3.388
    1500            4.497                       4.575
    2000            7.717                       7.807
    5000          16.064                     16.143
  10000           23.711                     23.797
  20000           37.76                       37.926
  50000           91.748                     92.086
100000          185.492                   185.98   

I check  the 2  two insertion separately (Messaged User,Values )
When only data inserted to Messaged_user(insert to values table removed from the code) table only it took 80.926s to insertion and 80.992s for querying.
When only data inserted to Values(insert to Messaged_User table removed from the code) table only it took 77.054s to insertion and 77.16s for querying.
sum of the two in separate insertions=157.98s
sum of the two in separate querying=157.98s 

Thats 30s different from what i got when the two insertions are in same coding.
I try another time with two insertion at the same time.  Amazingly i got 141.721s for insertion and 142.21s for querying. Try for another gave 161.523s for insertion and 162.014s for querying.
So i decided that bug must be on the "insertion"
Next i include the Statement class for execution inside the loop
Insted of ,
PreparedStatement ps = con.prepareStatement
                ("INSERT INTO Messaged_Users VALUES (?, ?, DEFAULT, DEFAULT)");
            for (i=0; i<100000; i++) {
                ps.setString(1, ""+i);
                ps.setString(2, "User" + i);
I used,
Statement stmt=con.createStatement();               
            for (i=0; i<100000; i++) {
                stmt.executeUpdate("INSERT INTO Users VALUES ('"+i+"', 'Eranda')");
as a test,  But i waited 15s for over the insertion and querying and stopped the process.

Can you show me a path that i can go on further? Thanks