JPA – The Cartesian Product Problem

Hvad er problemet?

Nærværende artikel tager udgangspunkt i den anden ende af fetch-strategi-skalaen og handler om det modsatte problem: The Cartesian Product Problem. Her hentes for mange data med deraf følgende unødvendig netværkstrafik og memoryforbrug på såvel database- som JavaEE-server. The Cartesian Product Problem opstår når to eller flere collections hentes eagerly. Vi tager udgangspunkt i følgende entity:

@Entity
public class Hobbit {

    @Id
    @GeneratedValue
    private Integer id;
    private String name;

    @OneToMany (fetch=FetchType.EAGER, mappedBy=”itemOwner”)
    private Set<Item> belongings; 

    @OneToMany (fetch=FetchType.EAGER, mappedBy=”foodOwner”)
    private Set<Food> favoriteFood; 

    public Hobbit() {
    }

    // getters and setters etc.
}

Bemærk, at den globale fetch strategi for både belongings og favoriteFood er sat til EAGER. Følgende kodelinie henter en hobbit (med id = 1) op fra databasen ved brug af metoden find på EntityManageren em:

Hobbit h = em.find(Hobbit.class, new Integer(1));

Kaldet til find-metoden genererer følgende SQL:

select hobbit.*, belongings.*, favoritefood.*
from Hobbit hobbit 
left outer join Item belongings on hobbit.id=belongings.itemOwner_id 
left outer join Food favoritefood on hobbit.id=favoritefood.foodOwner_id

Eksekveres ovenstående query i en SQL-klient fås et resultatet som vist i tabellen nedenfor. Forespørgslen udføres i ét select statement, hvilket medfører mange redundante rækker i søgeresultatet, idet data hentes som et kartetisk product. Hvis de to collections indeholder n og m elementer, udgør det kartetiske produkt således n * m rækker. Og skal man eksempelvis hente 1000 hobbitter (som elsker god mad og har mange ejendele), kan søgeresultatet udgøre anseelige datamængder, som skal transporters over netværket.

Når JPA provideren opretter hobbit-objekter fjernes duplikerede redundante rækker, hvilket ses ved udskrivning af Hobbit-klassens toString-metode:

Hobbit[id=1, Baggins, 
belongings=[Item[id=32768, Ring of Power], Item[id=32769, Hicking boots], 
Item[id=32770, Back Pack], Item[id=32771, Walking stick]], 
favoriteFood=[Food[id=65536, Lembas bread], Food[id=65537, Rabbit stowe], 
Food[id=65538, Mushrooms]]]

Som sidebemærkning kan nævnes, at det kun virker fordi favoriteFood og belongings er Sets, hvor elementerne er unikke. Anvendes andre collections hvor duplikater er tilladt (fx Collection eller List), kan persistence provideren ikke identificere, hvilke rækker i det kartetiske produkt som er redundante. Forsøger man alligevel udstedes en javax.persistence.PersistenceException med beskeden: cannot simultaneously fetch multiple bags.

Hvordan løses problemet?

Nu er vi så fremme ved sagens kerne: For hvordan kan hobbitter og deres collections af items og favoriteFood hentes eagerly uden at vi løber ind i The Cartesian Product Problem?

Som omtalt i forrige JPA-artikel er det ikke tilstrækkeligt, at bestemme hvornår data hentes ved fastlæggelsen af en lazy/eager fetch-strategi. Man må ligeledes tage stilling til hvordan de hentes. Desværre indgår denne ekstra dimension ikke i JPA specifikationen, hvorfor man er nødt til at benytte sin persistence providers proprietære faciliteter.

Løsningen, i Hibernate, er at anvende en annotation (eller en tilsvarende facillitet for en anden persistence provider), der angiver, at data skal hentes i flere subselects. Det gøres således:

@Entity
public class Hobbit {

    @Id
    @GeneratedValue
    private Integer id;
    private String name;

    @OneToMany (fetch=FetchType.EAGER, mappedBy=”itemOwner”)
    @org.hibernate.annotations.Fetch
            (org.hibernate.annotations.FetchMode.SELECT)
    private Set<Item> belongings; 

    @OneToMany (fetch=FetchType.EAGER mappedBy=”foodOwner”)
    @org.hibernate.annotations.Fetch
                (org.hibernate.annotations.FetchMode.SELECT)
    private Set<Food> favoriteFood; 

    public Hobbit() {
    }

    // getters and setters etc
}

Samme kald til entitymanagerens find-metode,

Hobbit h = em.find(Hobbit.class, new Integer(1));

resulterer nu i følgende tre SQL select statements:

select hobbit.* from Hobbit hobbit where hobbit.id = 1

select favoritefood.* from Food favoritefood 
                   where favoritefood.foodOwner_id = 1

select belongings.* from Item belongings 
                     where belongings.itemOwner_id = 1

Dvs. data hentes nu i tre separate select statements i stedet for ét og collectionerne favoriteFood og belongings populeres med hver deres subselect. Størrelsen af det samlede resultSet er nu reduceret fra (n * m) rækker til (n + m).

Bemærk, at det ikke kun er i forbindelse med en global EAGER fetch-strategi, at data kan hentes som et kartetisk produkt. Problemet opstår fx også ved følgende query:

String jpaql = "select h from Hobbit h LEFT JOIN FETCH h.belongings 
                                       LEFT JOIN FETCH h.favoriteFood";
Query query = em.createQuery(jpaql);

Her er løsningen blot at udelade FETCH og blot foretage LEFT JOINs. Herved vil den genererede SQL indeholde tre selects som vist ovenfor.

Perspektivering

Bemærk at det ikke kun er i forbindelse med The Cartesian Product Problem, at det er interessant at overveje, hvordan data skal hentes. Persistence providers stiller generelt flere muligheder til rådighed. Eksempelvis er det muligt at anvende batch fetching når collections hentes. Her vil Hibernate, fx i forbindelse med populering af en hobbits favoriteFood-collection, hente flere hobbitters collection samtidigt. Populeringen foretages i batch, hvor batch-størrelsen er konfigurerbar. Hobbitterne, der får populeret deres favoriteFood-collection i batch, udvælges blandt de hobbit-objekter som allerede findes i persistence context’en.

Det er også muligt at hente en collection extra lazy, hvor hvert element hentes når det tilgås.
Og endelig anvender Hibernate pr. default proxy fetching, hvor @OneToMany og @ManyToMany hentes som proxies, der kun er populeret med ID.

Konklusion

N+1 select-problemets modstykke, The Cartesian Product problem, opstår når mere end to collections hentes eagerly i samme select. De to problemer udgør fetch-strategiens modpoler, hvor det gælder om at finde en gylden middelvej.

For at opnå acceptabel performance, er det således ikke tilstrækkeligt blot at angive hvornår data hentes. Man må ligeledes tage stilling til hvordan.

Under normale omstændigheder er det ønskværdigt at reducere antallet af forespørgsler mod databasen så meget som muligt, idet hvert round-trip udgør et overhead. Men i forbindelse med The Cartesian Product Problem er det bedre at hente data i flere subselects, idet søgeresultatets størrelse herved reduceres væsentligt. Artiklen nævnte endvidere, at det generelt er interessant at overveje, hvordan data hentes herunder mulighederne for subselects samt batch og extra lazy fetching.