find() cost unreasonable time!

Joined on 2011-05-17

Hi, I make a full binary tree of 4095 node, I check the first 9 node, but the root cost 24 seconds, why?

Result:

===========
find time @ 24.125000
getSons time @ 0.000000
1 : type:Nodes, sons:2
child : 2
child : 3
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
2 : type:Nodes, sons:2
child : 4
child : 5
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
3 : type:Nodes, sons:2
child : 6
child : 7
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
4 : type:Nodes, sons:2
child : 8
child : 9
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
5 : type:Nodes, sons:2
child : 10
child : 11
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
6 : type:Nodes, sons:2
child : 12
child : 13
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
7 : type:Nodes, sons:2
child : 14
child : 15
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
8 : type:Nodes, sons:2
child : 16
child : 17
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
9 : type:Nodes, sons:2
child : 18
child : 19
Iterator time @ 0.000000
The sum : 18

Class of Nodes:

@Entity
@Inheritance(strategy=InheritanceType.JOINED)
// Success for Inheritance Sonsection
//@Cache(size=10000)
@DiscriminatorColumn(discriminatorType=DiscriminatorType.INTEGER,name="type")
@DiscriminatorValue(value="0")
public class Nodes {
@Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
private int id;
@ManyToOne
@JoinColumn(name="parent")
protected Nodes parent;

@OneToMany(mappedBy="parent",fetch=FetchType.EAGER)
protected List<Nodes> Sons;

function of checking:

private static void getSons0() {
  System.out.printf("===========%n");
  int iSum = 0;
  for (int i=0;i<3*iBlock;i++){
   long start = System.currentTimeMillis();
   Nodes o = em.find(Nodes.class, i+1);
   System.out.printf("find time @ %f %n", (System.currentTimeMillis()-start)/1000f);
   if (null== o){
    System.out.printf("%s is not Nodes %n", o);
    continue;
   }
   em.refresh(o);
   start = System.currentTimeMillis();
   List<Nodes> sons = o.getSons();
   System.out.printf("getSons time @ %f %n", (System.currentTimeMillis()-start)/1000f);
   if (null==sons) continue;
   int iCnt = sons.size();
   System.out.printf("%d : type:Nodes, sons:%d %n",i+1, iCnt);
   iSum += iCnt;
   start = System.currentTimeMillis();
   Iterator<Nodes> it = sons.iterator();
   while (it.hasNext()){
    Nodes en = it.next();
    System.out.printf("child : %d %n", en.getId());
   }
   System.out.printf("Iterator time @ %f %n", (System.currentTimeMillis()-start)/1000f);
  }
  System.out.printf("The sum : %d %n", iSum);
  System.out.println();
}

Institute of Computer Technologies

Joined on 2010-05-03

Please post a full runnable program, as explained in these instructions.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

Joined on 2011-05-17

I do read your Instructions "Keep the test as simple as possible - remove unnecessary code"!

Ok, Class of Nodes:

package fpg;

import java.util.List;

import javax.persistence.DiscriminatorColumn;
import javax.persistence.DiscriminatorType;
import javax.persistence.DiscriminatorValue;
import javax.persistence.Entity;
import javax.persistence.FetchType;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.Inheritance;
import javax.persistence.InheritanceType;
import javax.persistence.JoinColumn;
import javax.persistence.ManyToOne;
import javax.persistence.OneToMany;

@Entity
@Inheritance(strategy=InheritanceType.JOINED)
@DiscriminatorColumn(discriminatorType=DiscriminatorType.INTEGER,name="type")
@DiscriminatorValue(value="0")
public class Nodes {
@Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
private int id;
@ManyToOne
@JoinColumn(name="parent")
protected Nodes parent;

@OneToMany(mappedBy="parent",fetch=FetchType.EAGER)
protected List<Nodes> Sons;

public int getId() {
  return id;
}
public Nodes getParent() {
  return parent;
}

public List<Nodes> getSons() {
  return Sons;
}

public void setId(int id) {
  this.id = id;
}

public void setParent(Nodes parent) {
  this.parent = parent;
}

public void setSons(List<Nodes> Sons) {
  this.Sons = Sons;
}
@Override
public String toString() {
  return getId()+"";
}
}

test codes:

package src.run;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Map.Entry;

import javax.persistence.EntityManager;
import javax.persistence.EntityTransaction;
import javax.persistence.Query;

import fpg.Nodes;

/**
* @author dillony@gmail.com
*
*/
public class testNodes {

private static EntityManager em = SingleManager.getEntityManager();
private static int iBlock;
private static Random rd;
private static EntityTransaction trans = SingleManager.getTrans();
private static int iBegin = 0;

private static void generateBtree(final int iLevel) {
  long start = System.currentTimeMillis();
  LinkedList<Nodes> queue = new LinkedList<Nodes>();
  trans.begin();
  Nodes parent = new Nodes();
  em.persist(parent);
  queue.add(parent);
  int iNum = 0;
  int iCnt = 0;
  while (queue.size()>0){
   Nodes cur = queue.pop();

   Nodes left = new Nodes();
   left.setParent(cur);
   em.persist(left);
++iNum;
   Nodes right = new Nodes();
   right.setParent(cur);
   em.persist(right);
++iNum;
   if (iLevel>iCnt ){
    queue.add(left);
    queue.add(right);
    iCnt += 2;
   }
   if ( (iNum & 0xFFF) ==0){
    System.out.printf("%d @ %s %n", iNum, (System.currentTimeMillis()-start)/1000f);
    trans.commit();
    em.clear();
    trans.begin();
   }
  }
  trans.commit();
  System.out.printf("Total: %d, Level:%d %n", iNum, iLevel);
  float timecost = (System.currentTimeMillis()-start)/1000f;
  System.out.printf("Insert: %f objects per second %n", iNum/timecost);
}

private static void getSons0() {
  System.out.printf("===========%n");
  int iSum = 0;
  for (int i=0;i<3*iBlock;i++){
   long start = System.currentTimeMillis();
   Nodes o = em.find(Nodes.class, i+1);
   System.out.printf("find time @ %f %n", (System.currentTimeMillis()-start)/1000f);
   if (null== o){
    System.out.printf("%s is not Nodes %n", o);
    continue;
   }
   em.refresh(o);
   start = System.currentTimeMillis();
   List<Nodes> sons = o.getSons();
   System.out.printf("getSons time @ %f %n", (System.currentTimeMillis()-start)/1000f);
   if (null==sons) continue;
   int iCnt = sons.size();
   System.out.printf("%d : type:Nodes, sons:%d %n",i+1, iCnt);
   iSum += iCnt;
   start = System.currentTimeMillis();
   Iterator<Nodes> it = sons.iterator();
   while (it.hasNext()){
    Nodes en = it.next();
    System.out.printf("child : %d %n", en.getId());
   }
   System.out.printf("Iterator time @ %f %n", (System.currentTimeMillis()-start)/1000f);
  }
  System.out.printf("The sum : %d %n", iSum);
  System.out.println();
}
public static void main(String[] args) {
  rd = new Random();
  iBlock = 3;
  generateBtree(1<<11);
  getSons0();
  SingleManager.close();
}
}

Results:

4096 @ 0.204
8192 @ 0.329
12288 @ 0.391
16384 @ 0.422
Total: 16386, Level:8192
Insert: 36092.511719 objects per second
===========
find time @ 213.406006
getSons time @ 0.000000
1 : type:Nodes, sons:2
child : 2
child : 3
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
2 : type:Nodes, sons:2
child : 4
child : 5
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
3 : type:Nodes, sons:2
child : 6
child : 7
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
4 : type:Nodes, sons:2
child : 8
child : 9
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
5 : type:Nodes, sons:2
child : 10
child : 11
Iterator time @ 2.219000
find time @ 0.000000
getSons time @ 0.000000
6 : type:Nodes, sons:2
child : 12
child : 13
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
7 : type:Nodes, sons:2
child : 14
child : 15
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
8 : type:Nodes, sons:2
child : 16
child : 17
Iterator time @ 0.000000
find time @ 0.000000
getSons time @ 0.000000
9 : type:Nodes, sons:2
child : 18
child : 19
Iterator time @ 0.000000
The sum : 18


Error opening zip file or JAR manifest missing: /E:/projects/ObjectDB/bin/objectdb.jar

Institute of Computer Technologies

Joined on 2011-05-17

I have to mention that for the parameter "1<< y"

y=13, 16384 nodes, 213.406006 seconds
y=12, 8192 nodes, 40.235001 seconds
y=11, 4096 nodes, 10.625000 seconds

For each 'y', I delete the .odb file.

Institute of Computer Technologies

Joined on 2010-05-03

> I do read your Instructions "Keep the test as simple as possible - remove unnecessary code"!

Anything that is required for the sample application to be runnable is not considered unnecessary (by the way the last posted source required also some changes to become runnable, since the class SingleManager was missing).

Anyway, your test application demonstrates a very important issue:

Inverse (mapped by) relationships are inefficient for navigation in the inverse direction.

ObjectDB supports bidirectional relationships because this is part of JPA. But navigation in the inverse direction from the owned to the owner - requires running queries, so you lose the main benefit of using an object database.

Try the following changes to your code:

Remove mappedBy="parent" from the definition of Sons:

    @OneToMany(fetch=FetchType.EAGER)

Initialize the Sons collection:

    protected List<Nodes> Sons = new ArrayList<Nodes>(2);

Let setParent update both sides:

    public void setParent(Nodes parent) {
        parent.Sons.add(this);
        this.parent = parent;
    }

You may also remove the refresh:

    // em.refresh(o);

Now that the bidirectional relationship was converted to 2 unidirectional relationships - the performance is incomparable.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

Joined on 2011-05-17

I have not test your plan even it sounds good. However, my situation is multiple clients maintaining a tree, each will make CRUD operations independently, so one have to refresh the status of a node since other clients will change it. A List in memory is just for the current client, which is unknown to the other clients.

Would you please give another advices?

TIA

BTW, without mappedBy="parent", @OneToMany is unnecessary, right?

Institute of Computer Technologies

Joined on 2010-05-03

> Would you please give another advices?

You can keep the refresh and also use locking. This is not related to moving from one bidirectional relationship to two unidirectional relationships to improve performance.

> BTW, without mappedBy="parent", @OneToMany is unnecessary, right?

Yes this is unnecessary, unless you want to set fetch type to EAGER.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

Joined on 2011-05-17

Without @OneToMany, each client can not find all the sons of a node, that is a big problem.

Institute of Computer Technologies

Joined on 2010-05-03

After commit everyone can see the changes.

Sometimes a refresh is needed to bypass the cache.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

#10

Joined on 2011-05-17

Sorry, I'm confused.

Without mappedBy="parent", what function is "fetch type to EAGER"?

TIA

Institute of Computer Technologies

#11

Joined on 2010-05-03

It means loading the graph eagerly (see Retrieval by Eager Fetch in the manual).

the effect of EAGER is similar in ordinary and inverse fields.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

#12

Joined on 2011-05-17

I put 524290 nodes in a binary tree, each node has two subtrees. I visit the nodes one by one using "Nodes1 o = em.find(Nodes1.class, i+1);", I get the two children for each node. I believe the find() has to be optimized.

The result shows:

Total GetSons time @ 241.078003

Total finding time @ 235.171005

Is there a better way replacing find()?

Institute of Computer Technologies

#13

Joined on 2010-05-03

Find is very efficient in retrieving a single entity object but less efficient when you need to retrieve many entity objects (524,290 in your test). In that case - you should use a query.

Eager navigation is also expected to be faster than find since entities are retrieved in bulk.

ObjectDB Support
ObjectDB - Fast Object Database for Java (JPA/JDO)

✂

edit

delete