songjinghe / temporal-storage Goto Github PK
View Code? Open in Web Editor NEWThis project forked from tgraphdb/temporal-storage
This project forked from tgraphdb/temporal-storage
现在系统通过多维R树实现建立多属性索引,但是对于查询,只能是,例如:对3个属性建立索引,查询必须同时指定这3个属性的查询条件。
可扩展支持:
能不能在对多维属性建立索引以后,支持对这几个属性的任意组合的条件查询。
这样的好处在于:只需维护一个多维索引,就可以支持任意属性条件查询;而不是对两个属性查询,就建立二维属性缩印,三个属性查询件三维属性索引,即要维护两层的不同R树索引。
问题在于:实现可行性及代价未知,可能需要对比试验才能了解效果。
目前的测试是对于每个index查出来的entry都用range查询再查一遍。这样已经通过了测试(在真实数据集上),但有点不太完全,还应该加一个:对每个range查到的entry找有无对应的indexEntry。
参考STR那篇论文。不过这篇论文是在不同的索引方法之间相互比较。
其度量的主要指标是disk access count,还用了一个LRU的策略来缓存。他说之所以不度量时间,主要就是因为怕在其他平台测试结果不一致的情况出现。
第二个度量指标是:sum of the area and perimeter of the MBRs of the R-tree nodes.据说这个可反应一个query访问的node节点数。
用了模拟和真实两种数据。为了方便对比,他把所有数据都归一化了。模拟数据用的是均匀分布。
我总觉得这里有问题,但如果是以block为单位那就没问题。不过我们block块的大小是可变的~现在因为没有变长属性所以block大小是一定的。
另外关于LRU的问题,我们这里貌似用FileMapping就自带了?我觉得第二个指标好像和上面那个重复了?
这是一个很好的机会来测量我们实际数据的分布情况:一个是不同更新频率的id的分布,另一个是更新频率随时间的变化?尚不清楚是否存在这样的变化~
在考虑一下我们的问题,其实第一步要测的是索引和非索引之间有无差别(包括用内存存储的和磁盘存储的)这个可以用时间来度量。然后是索引的磁盘访问特点?(说白了就是要找出索引查询时间和什么有关系,目前猜测应该和数据总量及查询结果集的大小有关)其他的暂时没想到,先做做再说。
RT,出现start>end的情况
这种情况可能存在,比如AB两个属性,A为3的时候B为invalid,这种情况目前无法处理。主要是索引的值必须是可比较的,而invalid的比较一直是个问题。
现在的问题是,如果在Neo4j里面删掉了节点,但是这个节点之前的某个时态属性建立过索引的话,那么查询entity时还是能找出这个entity。
RT,尚未测试
@Test
public void test2fail0() throws Throwable {
StoreBuilder stBuilder = new StoreBuilder(dbDir, true);
store = stBuilder.store();
for(int time=10; time<Integer.MAX_VALUE/100-6; time+=5){
for(long entityId=1; entityId<5; entityId++){
StoreBuilder.setIntProperty(store, time, entityId, 0, time);
}
}
Slice val = store.getPointValue(1, 0, 9); // 1:entityid,0:proId,9:time
if(val!=null) log.debug("{}", val.getInt(0));// val should be null, but can get 10
store.shutDown();
}
这个问题是在解决 #1 的时候发现的。测试代码:
@Test
public void test2fail2() throws Throwable {
StoreBuilder stBuilder = new StoreBuilder(dbDir, true);
store = stBuilder.store();
for(long entityId=1; entityId<5; entityId++){
for(int proId=0; proId<Integer.MAX_VALUE/1000-6; proId+=5){
StoreBuilder.setIntProperty(store, 0, entityId, proId, 0); // time为0
}
for(int proId=0; proId<Integer.MAX_VALUE/1000-6; proId+=3){
StoreBuilder.setIntProperty(store, 10, entityId, proId, 10); // time为10
}
log.debug("version {} write finish", entityId);
}
Slice val = store.getPointValue(1, 3, 4); //1为entityid,3为proId,4为time
log.debug("{}", val.getInt(0));
}
错误信息:
java.util.NoSuchElementException
at java.util.TreeMap.key(TreeMap.java:1327)
at java.util.TreeMap.lastKey(TreeMap.java:297)
at org.act.temporalProperty.impl.StableLevel.getPointValue(StableLevel.java:203)
at org.act.temporalProperty.impl.TemporalPropertyStoreImpl.getPointValue(TemporalPropertyStoreImpl.java:167)
at org.act.temporalProperty.impl.query.range.FloorQueryTest.test2fail2(FloorQueryTest.java:46)
存储文件夹里只有000001.un
、000001.buf
和两个meta文件
RT,这个问题仅在windows下存在。请 @SkyeFan 构造一个可以复现该bug的最小代码示例(现在这个代码太复杂,不方便定位问题)。谢谢!
有时候,同一个entity,在range查询时,给定时间的范围如果较小则有结果,较大则无结果!
@Test
public void test2fail() throws Throwable {
this.store.getRangeValue(62254,1,0,Integer.MAX_VALUE-6, new CustomCallBack(62254){
public void onCall(int time, Slice value) { log.info("{} {}", time, value.getInt(0));}
public Object onReturn() { log.info("onReturn of test"); return null;}
});
log.info("=================");
this.store.getRangeValue(62254,1,18360,18959, new CustomCallBack(62254){
public void onCall(int time, Slice value) { log.info("{} {}", time, value.getInt(0));}
public Object onReturn() { log.info("onReturn of test"); return null;}
});
}
上面无输出,下面有一个输出(当然这个也是有问题的,因为从索引的结果来看至少有两个吧?)
如要搜索所有start time<300, end time>600的entry,则目前无法做。
目前来看,除了实现了一个支持floor操作的kv查询外,并不支持时间区间的操作。包括删除某个区间段的时间点的值。更糟糕的是连正常的覆盖也不支持(eid0,pid0,time从0到100万,写一遍1,然后重复再写一遍2以此类推3和4,最后发现居然还能查到前面的1和3(没有2)什么的~不知道是怎么搞的。
测试重现代码如下:
@Test
public void test2fail() throws Throwable {
StoreBuilder stBuilder = new StoreBuilder(dbDir, true);
this.store = stBuilder.store();
for(int version=1; version<5; version++){
for(int time=0; time<Integer.MAX_VALUE/1000-6; time+=1){
StoreBuilder.setIntProperty(store, time, 0, 0, version);
}
log.debug("version {} write finish", version);
}
EntityIdCallBack callback = new EntityIdCallBack();
this.store.getRangeValue(0,0,0,Integer.MAX_VALUE/1000-6, callback);
}
private class EntityIdCallBack extends RangeQueryCallBack {
public void onCall(int time, Slice value) {
int val = value.getInt(0);
if(val!=4){ // 这里会出现1,3但是没有2,不知道什么情况
log.info("value not latest, get "+ val+" at time "+ time);
}
}
public void setValueType(String valueType) {}
public void onCallBatch(Slice batchValue) {}
public Object onReturn() {
return null;
}
public RangeQueryCallBack.CallBackType getType() {
log.info("getType called");
return RangeQueryCallBack.CallBackType.USER;
}
}
RT,在indexInfoReader里面发现的。下面是level0(即root节点)和level1的11个节点的情况,可以看出这个level1之间是相交的。
level 0 contains 1 nodes
RTreeNode[bound=RTreeRange{min=IndexEntity(start=0,end=299,val0=1), max=IndexEntity(start=27360,end=27360,val0=148975)}]
level 1 contains 11 nodes
RTreeNode[bound=RTreeRange{min=IndexEntity(start=0,end=299,val0=1), max=IndexEntity(start=1860,end=27360,val0=33705)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=1860,end=2159,val0=1), max=IndexEntity(start=3660,end=27360,val0=83611)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=3660,end=3959,val0=1), max=IndexEntity(start=6060,end=27360,val0=30492)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=6060,end=6359,val0=1), max=IndexEntity(start=9060,end=27360,val0=32040)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=9060,end=9359,val0=1), max=IndexEntity(start=13560,end=27360,val0=48452)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=13560,end=13859,val0=1), max=IndexEntity(start=18960,end=27360,val0=86580)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=18960,end=19259,val0=1), max=IndexEntity(start=21960,end=27360,val0=33180)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=21960,end=22259,val0=1), max=IndexEntity(start=23760,end=27360,val0=20400)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=23760,end=24059,val0=1), max=IndexEntity(start=25260,end=27360,val0=40317)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=25260,end=25559,val0=1), max=IndexEntity(start=26760,end=27360,val0=24328)}]
RTreeNode[bound=RTreeRange{min=IndexEntity(start=26760,end=27059,val0=1), max=IndexEntity(start=27360,end=27360,val0=148975)}]
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.