[Bigdata-commit] Pagination consistency without ORDER BY

[Blaise de C. <bde...@gm...>]

Hi there,

I would like to expose a considiration that I find very annoying. I need to
do more tests but i would like to know your fellings about it.

Look for this exemple :

construct where {
 ?s <http://geovocab.org/geometry#geometry> ?event
} limit 5

It take avout 100ms to execute on my 3B dataset.

In 90% of time, this give me 5 results in the same order :

<http://linkedgeodata.org/triplify/node1003406722>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1003406722>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1003406722>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1003406722>>
<http://linkedgeodata.org/triplify/node1003749425>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1003749425>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1003749425>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1003749425>>
<http://linkedgeodata.org/triplify/node1011261499>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1011261499>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1011261499>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1011261499>>
<http://linkedgeodata.org/triplify/node1011261514>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1011261514>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1011261514>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1011261514>>
<http://linkedgeodata.org/triplify/node1011286717>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1011286717>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1011286717>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1011286717>>
But sometime, i get differents results :

<http://linkedgeodata.org/triplify/node1204787784>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1204787784>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1204787784>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1204787784>>
<http://linkedgeodata.org/triplify/node1206798938>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1206798938>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1206798938>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1206798938>>
<http://linkedgeodata.org/triplify/node12081506>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node12081506>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node12081506>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node12081506>>
<http://linkedgeodata.org/triplify/node1209197022>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1209197022>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1209197022>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1209197022>>
<http://linkedgeodata.org/triplify/node1212230478>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/triplify/node1212230478>>
<http://geovocab.org/geometry#geometry>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://geovocab.org/geometry#geometry>>
<http://linkedgeodata.org/geometry/node1212230478>
<http://ns3027589.ip-149-202-90.eu:9999/blazegraph/#explore:kb:<http://linkedgeodata.org/geometry/node1212230478>>
Conclusion : o*rder is not garantee without ORDER BY*. If i use an ORDER
BY, performance drop alarmingly.

Now take this fabulous project : Linked Data Fragments (
http://linkeddatafragments.org/), which provide a SparqlDatasource to
handle data from a SPARQL Endpoint. They use CONSTRUCT queries with LIMIT
and OFFSET to paginate the results, as they says in the comments :

// Even though the SPARQL spec indicates that
// LIMIT and OFFSET might be meaningless without ORDER BY,
// this doesn't seem a problem in practice.
// Furthermore, sorting can be slow. Therefore, don't sort.

But it's a problem in practice with Blazegraph, and i exeperimented it : a
Linked Data Fragments server configured over a Blazegraph SPARQL Endpoint
serve different pages in 5-10% of time.

In our project we really need to get consistent pagination, without ORDER
BY. Do you think that is possible with Blazegraph ?

Bests,
Blaise

PS : i don't see this behaviour with SELECT, but cache could be
responsible...
-- 
*Blaise de Carné*
bde...@gm...
06.73.67.28.38