Andy,
First, sorry for moving this discussion but I accidentally sent the original from the old list and I don't seem to be getting any email from it so I am reposting the entire discussion here with new comments. I am thinking more of high contention environments with large data sets. For example a SPARQL server where users can update the data. Under the current environment all the queries have to create copies of the triples they are working with or block the updates. Similarly updates block the reads. From what I have seen in the Jena code, much of the query engine is designed to work with iterators and "streaming" data. However, the current solution to the issues of graph modification while iterating is to lock out all updates until the query is complete. In high volume update environments this effectively leads to single threading the application. Here are a couple of use cases: == simultaneous update via polling threads == I have a smaller scale use case at DERI where we are monitoring multiple devices via web calls. The application spawns threads to periodically poll the devices and updates the graph accordingly. Our SPARQL server uses that data in virtually every query -- and some of our queries take several minutes to execute. So at times all our queries are held up while the device data is updated. In our application would would be perfectly happy executing against old data and we would deal with disappearing nodes in the same way we deal with any other missing data. == security model == A second use case would be a graph authorization system. (I am working on one) where the access authorization to the graphs are maintained in a single model. That model would have to be quickly readable to support queries on the front end and updatable to support addition of information about new graphs (and potentially triples or nodes) as they are added. == current iteration error messages == A third use case is any of the several messages a week dealing with the issue of modification of the graph while iterating. Finally, I think that most of these use cases fall outside of the data interactions defined by relational database transaction isolation levels and is more in line with the nosql concept of eventual consistency. I suppose that if the model transactions supported the standard RMDB isolation levels this could be faked. But that would require that all queries and graph dumps create duplicate local data for processing. (my assumption here is that there is only a model level lock and that locks are not pushed down to the triple level -- node level locking would bring up an entirely new set of issues as I think I would involve multiple triple level locks) By duplicate local data I mean that internally the queries have to build collections of triples that answer some part of the query and then merge those collections in some way (union, join, etc). While it is possible to put many of those collections in memory, streaming them to disk is necessary for large data sets, and for very large data sets handling all that data multiple times introduces huge overhead. === Implementation Note === If you think back several versions of Java, before the dawn of iterators everybody used enumerators. The enumerator does not have the same restriction on concurrent update that the iterator does -- it also does not do the delete. So a quick implementation of the quantum collection is to create an Enumerator on a collection and then drive the iterator from that. I hope this hasn't been too rambling a response. Perhaps I should put it all down in one place, in one cohesive presentation. -- Claude Start of quote >>> Claude, The problem you are highlighting is that wanting to process (query) results in a way that needs updates to the data? ARQ does now have various support classes for streaming intermediate results to and from disk - this may be a way to effectively take a copy and not run out of system resources (streaming to disk and back isn't nearly as bad as random I/O to disk). Another possibility is the transaction mechanism for TDB allows multiple readers AND a single concurrent writer. In transactions, the single writer can be a thread thread receiving changes from other thread currently doing a read transactions (think actors). The readers will see a consistent view of the data - no missed or non-deterministic results. The transaction mechanism uses write-ahead-logging - the changes are made to a copy, and flushed back later. A in-memory dataset with those transactional characteristics would be nice. In-memory TDB is not scalable - it exactly follwos the disk versions, just swaps in a RAM disk. It's there for testing in the first instance. That new class of Collection is interesting, do you know of any libraries to look at using? Hwover, it does not pass as particularly "modest" :-) to me. Jena uses java.util Collections for general purpose datastructures and has it's own, specialised (and more compact) hash maps for graphs. Replacing them all would be a significant undertaking, if that is what your proposal would entail. Getting a bug-free, performant implementation of hash maps and arrays isn't completely trivial. I'd want to know it did indeed lead to benefits, not just look better. I believe that such a collection and set of iterators would make streaming queries of large data sets much easier and faster. Can we take this as a scenario to discuss? Do you have a concrete use case we can use to see if the current system is having as best it might? Andy On 28/08/12 09:47, Claude Warren wrote: It seems that one of the major stumbling blocks in building Jena based applications is that iterators is found in the iterator documentation: “The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this [remove()] method.” For Jena applications this means that updates to the underlying graph are prohibited while an iterator is in operation. Iterators are commonly used in query operations. One work around for this has been to create a copy of the results of a query operation into a local collection and then iterate across that. The net result of this work around is excessive consumption of resources to store the data in flight as it is being iterated over. A second work around has been to use read and write locks and/or transactions to prohibit writing to a graph while the graph is being queried. This solution works well when the number of updates to the graph is small in comparison to the number of queries. When the number of updates increases the data store effectively becomes single threaded. I propose a third work around, a new class of Collection, be considered. I call this a quantum collection as the items in the collection do not exist until they are examined. Conceptually, the collection is defined in terms of constraints on the objects within it. The iterator simply retrieves one of the objects and presents it. Since the collection does not exist in the classical sense there is no modification of the collection – save for the modification of the constraints that define it. In a Java implementation of the Iterator interface on such a collection makes the following contract: hasNext(): Locates an element in the collection to return and returns true if one was found, false otherwise. This method identifies the element as part of the collection. The iterator guarantees that the element was in the collection when the collection was examined. It makes no guarantees that the element is still in the collection or even that the collection contains any elements at all. next(): returns the element located by hasNext() or throws a NoSuchElementException if there are no more elements. If hasNext() was not called, next will call hasNext() to locate the object or determine that none exists. remove(): not implemented always throws UnsupportedOperationException Notice that the collection makes no assumptions about the order or uniqueness of the objects presented by the iterator. The iterator may be constructed so as to return unique objects, or the constraint on the collection may introduce ordering or uniqueness. I believe that such a collection and set of iterators would make streaming queries of large data sets much easier and faster. The trade off is that items that are added or removed over the course of the iteration may or may not be included in the iterator. That is, the number of elements returned by the iterator is indeterminate until all elements have been returned. Thoughts? Claude Warren << end of quote -- I like: Like Like - The likeliest place on the web<http://like-like.xenei.com> Identity: https://www.identify.nu/[email protected] LinkedIn: http://www.linkedin.com/in/claudewarren
