Details

      Description

      SPARQL Update uses a MutableTupleQueryResult to store the result of the query body and then iterates over it to apply DELETE and INSERT clauses. The problem is that the MutableTupleQueryResult does not scale, it's internal data structure is a linked list and BindingSets.get() is implemented as a scan. This means, the larger the number of tuples, the longer it takes to get the next tuple. We need a random access list instead.

      package org.openrdf.query.impl;
      
      import java.util.ArrayList;
      import java.util.Arrays;
      import java.util.Collection;
      import java.util.HashSet;
      import java.util.LinkedHashSet;
      import java.util.LinkedList;
      import java.util.List;
      import java.util.NoSuchElementException;
      import java.util.Set;
      
      import info.aduna.iteration.Iteration;
      import info.aduna.iteration.Iterations;
      
      import org.openrdf.query.BindingSet;
      import org.openrdf.query.QueryEvaluationException;
      import org.openrdf.query.TupleQueryResult;
      
      /**
       * An implementation of the {@link TupleQueryResult} interface that stores the
       * complete query result in memory. The query results in a
       * MutableTupleQueryResult can be iterated over multiple times and can also be
       * iterated over in reverse order.
       * 
       * @author Arjohn Kampman
       */
      public class MutableTupleQueryResult implements TupleQueryResult, Cloneable {
      
      	/*-----------*
      	 * Variables *
      	 *-----------*/
      
      	private Set<String> bindingNames = new LinkedHashSet<String>();
      
      	private List<BindingSet> bindingSets = new LinkedList<BindingSet>();
      
      	/**
      	 * The index of the next element that will be returned by a call to
      	 * {@link #next()}.
      	 */
      	private int currentIndex = 0;
      
      	/**
      	 * The index of the last element that was returned by a call to
      	 * {@link #next()} or {@link #previous()}. Equal to -1 if there is no such
      	 * element.
      	 */
      	private int lastReturned = -1;
      
      	/*--------------*
      	 * Constructors *
      	 *--------------*/
      
      	public <E extends Exception> MutableTupleQueryResult(Collection<String> bindingNames,
      			BindingSet... bindingSets)
      	{
      		this(bindingNames, Arrays.asList(bindingSets));
      	}
      
      	/**
      	 * Creates a query result table with the supplied binding names.
      	 * <em>The supplied list of binding names is assumed to be constant</em>;
      	 * care should be taken that the contents of this list doesn't change after
      	 * supplying it to this solution.
      	 * 
      	 * @param bindingNames
      	 *        The binding names, in order of projection.
      	 */
      	public MutableTupleQueryResult(Collection<String> bindingNames,
      			Collection<? extends BindingSet> bindingSets)
      	{
      		this.bindingNames.addAll(bindingNames);
      		this.bindingSets.addAll(bindingSets);
      	}
      
      	public <E extends Exception> MutableTupleQueryResult(Collection<String> bindingNames,
      			Iteration<? extends BindingSet, E> bindingSetIter)
      		throws E
      	{
      		this.bindingNames.addAll(bindingNames);
      		Iterations.addAll(bindingSetIter, this.bindingSets);
      	}
      
      	public MutableTupleQueryResult(TupleQueryResult tqr)
      		throws QueryEvaluationException
      	{
      		this(tqr.getBindingNames(), tqr);
      	}
      
      	/*---------*
      	 * Methods *
      	 *---------*/
      
      	public List<String> getBindingNames() {
      		return new ArrayList<String>(bindingNames);
      	}
      
      	public int size() {
      		return bindingSets.size();
      	}
      
      	public BindingSet get(int index) {
      		return bindingSets.get(index);
      	}
      
      	public int getIndex() {
      		return currentIndex;
      	}
      
      	public void setIndex(int index) {
      		if (index < 0 || index > bindingSets.size() + 1) {
      			throw new IllegalArgumentException("Index out of range: " + index);
      		}
      
      		this.currentIndex = index;
      	}
      
      	public boolean hasNext() {
      		return currentIndex < bindingSets.size();
      	}
      
      	public BindingSet next() {
      		if (hasNext()) {
      			BindingSet result = get(currentIndex);
      			lastReturned = currentIndex;
      			currentIndex++;
      			return result;
      		}
      
      		throw new NoSuchElementException();
      	}
      
      	public boolean hasPrevious() {
      		return currentIndex > 0;
      	}
      
      	public BindingSet previous() {
      		if (hasPrevious()) {
      			BindingSet result = bindingSets.get(currentIndex - 1);
      			currentIndex--;
      			lastReturned = currentIndex;
      			return result;
      		}
      
      		throw new NoSuchElementException();
      	}
      
      	/**
      	 * Moves the cursor to the start of the query result, just before the first
      	 * binding set. After calling this method, the result can be iterated over
      	 * from scratch.
      	 */
      	public void beforeFirst() {
      		currentIndex = 0;
      	}
      
      	/**
      	 * Moves the cursor to the end of the query result, just after the last
      	 * binding set.
      	 */
      	public void afterLast() {
      		currentIndex = bindingSets.size() + 1;
      	}
      
      	/**
      	 * Inserts the specified binding set into the list. The binding set is
      	 * inserted immediately before the next element that would be returned by
      	 * {@link #next()}, if any, and after the next element that would be
      	 * returned by {@link #previous}, if any. (If the table contains no binding
      	 * sets, the new element becomes the sole element on the table.) The new
      	 * element is inserted before the implicit cursor: a subsequent call to
      	 * <tt>next()</tt> would be unaffected, and a subsequent call to
      	 * <tt>previous()</tt> would return the new binding set.
      	 * 
      	 * @param bindingSet
      	 *        The binding set to insert.
      	 */
      	public void insert(BindingSet bindingSet) {
      		insert(currentIndex, bindingSet);
      	}
      
      	public void insert(int index, BindingSet bindingSet) {
      		bindingSets.add(index, bindingSet);
      
      		if (currentIndex > index) {
      			currentIndex++;
      		}
      
      		lastReturned = -1;
      	}
      
      	public void append(BindingSet bindingSet) {
      		bindingSets.add(bindingSet);
      		lastReturned = -1;
      	}
      
      	public void set(BindingSet bindingSet) {
      		if (lastReturned == -1) {
      			throw new IllegalStateException();
      		}
      
      		set(lastReturned, bindingSet);
      	}
      
      	public BindingSet set(int index, BindingSet bindingSet) {
      		return bindingSets.set(index, bindingSet);
      	}
      
      	public void remove() {
      		if (lastReturned == -1) {
      			throw new IllegalStateException();
      		}
      
      		remove(lastReturned);
      
      		if (currentIndex > lastReturned) {
      			currentIndex--;
      		}
      
      		lastReturned = -1;
      	}
      
      	public BindingSet remove(int index) {
      		BindingSet result = bindingSets.remove(index);
      
      		if (currentIndex > index) {
      			currentIndex--;
      		}
      
      		lastReturned = -1;
      
      		return result;
      	}
      
      	public void clear() {
      		bindingNames.clear();
      		bindingSets.clear();
      		currentIndex = 0;
      		lastReturned = -1;
      	}
      
      	public void close() {
      		// no-opp
      	}
      
      	@Override
      	public MutableTupleQueryResult clone()
      		throws CloneNotSupportedException
      	{
      		MutableTupleQueryResult clone = (MutableTupleQueryResult)super.clone();
      		clone.bindingNames = new LinkedHashSet<String>(bindingNames);
      		clone.bindingSets = new LinkedList<BindingSet>(bindingSets);
      		return clone;
      	}
      
      }
      

        Activity

        Hide
        bryanthompson bryanthompson added a comment -

        Workaround:

        For the impatient, there is a very simple fix:

        1. Clone the MutableTupleQueryResult class in openrdf into a new namespace in blazegraph.
        2. Replace LinkedList with ArrayList (one line change);
        3. Import that modified version of the class in our AST2BOpUpdate class (one line change).

        Show
        bryanthompson bryanthompson added a comment - Workaround: For the impatient, there is a very simple fix: 1. Clone the MutableTupleQueryResult class in openrdf into a new namespace in blazegraph. 2. Replace LinkedList with ArrayList (one line change); 3. Import that modified version of the class in our AST2BOpUpdate class (one line change).
        Hide
        michaelschmidt michaelschmidt added a comment - - edited

        Here's the performance comparison for the DELETE clause (same impact expected for INSERT clause), as reported by the following code, which outputs the time for scheduling the latest 10k statements for deletion (executed on a 5M dataset and a DELETE .. INSERT ... WHERE query extracting about 500k triples in its WHERE clause (and DELETING all of them, while inserting some stuff):

        while (itr.hasNext()) {
        
        	final BigdataStatement stmt = itr.next();
        	addOrRemoveStatement(context.conn.getSailConnection(), stmt, false/* insert */);
        
        	// output time for last 10k statements
        	if (++i%10000==0) {
                	t3 = System.currentTimeMillis();
        		System.err.println(
        			"Added 10000 stmts for removal in " + (t3-t2)/1000 + 
        			" seconds (now " + i + " stmts in total)”);
        		t2=t3;                             
        	}
        }
        

        Here's the output before the patch:

             [java] Added 10000 stmts for removal in 3 seconds (now 10000 stmts in total)
             [java] Added 10000 stmts for removal in 3 seconds (now 20000 stmts in total)
             [java] Added 10000 stmts for removal in 4 seconds (now 30000 stmts in total)
             [java] Added 10000 stmts for removal in 9 seconds (now 40000 stmts in total)
             [java] Added 10000 stmts for removal in 9 seconds (now 50000 stmts in total)
             [java] Added 10000 stmts for removal in 12 seconds (now 60000 stmts in total)
             [java] Added 10000 stmts for removal in 20 seconds (now 70000 stmts in total)
             [java] Added 10000 stmts for removal in 26 seconds (now 80000 stmts in total)
             [java] Added 10000 stmts for removal in 32 seconds (now 90000 stmts in total)
             [java] Added 10000 stmts for removal in 39 seconds (now 100000 stmts in total)
             [java] Added 10000 stmts for removal in 46 seconds (now 110000 stmts in total)
             [java] Added 10000 stmts for removal in 53 seconds (now 120000 stmts in total)
             [java] Added 10000 stmts for removal in 65 seconds (now 130000 stmts in total)
             [java] Added 10000 stmts for removal in 74 seconds (now 140000 stmts in total)
             [java] Added 10000 stmts for removal in 83 seconds (now 150000 stmts in total)
             [java] Added 10000 stmts for removal in 90 seconds (now 160000 stmts in total)
             [java] Added 10000 stmts for removal in 97 seconds (now 170000 stmts in total)
             ...
        

        Here's the output after the patch:

             [java] Added 10000 stmts for removal in 3 seconds (now 10000 stmts in total)
             [java] Added 10000 stmts for removal in 3 seconds (now 20000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 30000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 40000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 50000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 60000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 70000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 80000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 90000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 100000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 110000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 120000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 130000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 140000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 150000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 160000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 170000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 180000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 190000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 200000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 210000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 220000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 230000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 240000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 250000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 260000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 270000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 280000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 290000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 300000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 310000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 320000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 330000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 340000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 350000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 360000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 370000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 380000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 390000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 400000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 410000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 420000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 430000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 440000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 450000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 460000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 470000 stmts in total)
             [java] Added 10000 stmts for removal in 0 seconds (now 480000 stmts in total)
             [java] Added 10000 stmts for removal in 1 seconds (now 490000 stmts in total)
        
        Show
        michaelschmidt michaelschmidt added a comment - - edited Here's the performance comparison for the DELETE clause (same impact expected for INSERT clause), as reported by the following code, which outputs the time for scheduling the latest 10k statements for deletion (executed on a 5M dataset and a DELETE .. INSERT ... WHERE query extracting about 500k triples in its WHERE clause (and DELETING all of them, while inserting some stuff): while (itr.hasNext()) { final BigdataStatement stmt = itr.next(); addOrRemoveStatement(context.conn.getSailConnection(), stmt, false /* insert */); // output time for last 10k statements if (++i%10000==0) { t3 = System .currentTimeMillis(); System .err.println( "Added 10000 stmts for removal in " + (t3-t2)/1000 + " seconds (now " + i + " stmts in total)”); t2=t3; } } Here's the output before the patch: [java] Added 10000 stmts for removal in 3 seconds (now 10000 stmts in total) [java] Added 10000 stmts for removal in 3 seconds (now 20000 stmts in total) [java] Added 10000 stmts for removal in 4 seconds (now 30000 stmts in total) [java] Added 10000 stmts for removal in 9 seconds (now 40000 stmts in total) [java] Added 10000 stmts for removal in 9 seconds (now 50000 stmts in total) [java] Added 10000 stmts for removal in 12 seconds (now 60000 stmts in total) [java] Added 10000 stmts for removal in 20 seconds (now 70000 stmts in total) [java] Added 10000 stmts for removal in 26 seconds (now 80000 stmts in total) [java] Added 10000 stmts for removal in 32 seconds (now 90000 stmts in total) [java] Added 10000 stmts for removal in 39 seconds (now 100000 stmts in total) [java] Added 10000 stmts for removal in 46 seconds (now 110000 stmts in total) [java] Added 10000 stmts for removal in 53 seconds (now 120000 stmts in total) [java] Added 10000 stmts for removal in 65 seconds (now 130000 stmts in total) [java] Added 10000 stmts for removal in 74 seconds (now 140000 stmts in total) [java] Added 10000 stmts for removal in 83 seconds (now 150000 stmts in total) [java] Added 10000 stmts for removal in 90 seconds (now 160000 stmts in total) [java] Added 10000 stmts for removal in 97 seconds (now 170000 stmts in total) ... Here's the output after the patch: [java] Added 10000 stmts for removal in 3 seconds (now 10000 stmts in total) [java] Added 10000 stmts for removal in 3 seconds (now 20000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 30000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 40000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 50000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 60000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 70000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 80000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 90000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 100000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 110000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 120000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 130000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 140000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 150000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 160000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 170000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 180000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 190000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 200000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 210000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 220000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 230000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 240000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 250000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 260000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 270000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 280000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 290000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 300000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 310000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 320000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 330000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 340000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 350000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 360000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 370000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 380000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 390000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 400000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 410000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 420000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 430000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 440000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 450000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 460000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 470000 stmts in total) [java] Added 10000 stmts for removal in 0 seconds (now 480000 stmts in total) [java] Added 10000 stmts for removal in 1 seconds (now 490000 stmts in total)
        Hide
        krosenvold Kristian Rosenvold added a comment -

        I'm really happy about this issue being fixed, but I can't seem to find the commit anywhere ? Is there a pull request or some other place I can pick the changes from ?

        Show
        krosenvold Kristian Rosenvold added a comment - I'm really happy about this issue being fixed, but I can't seem to find the commit anywhere ? Is there a pull request or some other place I can pick the changes from ?
        Hide
        beebs Brad Bebee added a comment -

        Excellent. See Bryan's first comment on how to patch it now. It will be included in the 1.5.3 release as part of the open source distribution.

        Show
        beebs Brad Bebee added a comment - Excellent. See Bryan's first comment on how to patch it now. It will be included in the 1.5.3 release as part of the open source distribution.

          People

          • Assignee:
            bryanthompson bryanthompson
            Reporter:
            michaelschmidt michaelschmidt
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: