very common attribute values/custom indexing

On Mon, Oct 31, 2011 at 3:50 AM, Ross Judson <rossjudson at gmail.com> wrote: > I have a database with the following characteristics: > > Database Properties > Name: merge > Size: 1165 MB > Nodes: 45217101 > Resources: 9 > Timestamp: 30.10.2011 18:15:04 > > On my database, executing a query such as > count(//summary[@totalDirs=0]) executes in about 30 seconds, returning > a count of about 777,000 items. Executing count(//file[@length=0] also > takes about 30 seconds, returning about 12,000. > > The query plans look like: > > <FNAggr name="count(item)"> > <AxisPath> > <RangeAccess data="merge" min="0" max="0" type="ATTRIBUTE"/> > <IterStep axis="self" test="*:totalDirs"/> > <IterStep axis="parent" test="*:summary"/> > </AxisPath> > </FNAggr> > > It's clear that BaseX goes to the attribute index, scans every entry > there for the 0-0 range, then checks for the appropriate attribute and > parent types. What this means is that very common attribute values can > take a much longer time to run, even when the number of results, when > discriminated by attribute name, is relatively small. > > The keys for the attribute index are simple values. Since this is an > ordered/balanced structure, you can compound the key for free (sort > of). Instead of using the attribute value as the key, use the index as > a prefix map by compounding attribute value+attribute name (something > like index.index(Token.concat(data.text(pre, text), data.name(pre)), > pre);). I'm wondering if you've tried and rejected compounding the > indexes like this. It's a common technique to use when indexing in > triple stores (a few compound indexes allow you to have complete > one-step indexing). With the additional discrimination provided you'd > probably get a big jump in speed for the vast majority of queries, > which won't be searching for an unknown attribute with a certain > value. > > The query plan would become something like this: > > <FNAggr name="count(item)"> > <AxisPath> > <RangeAccess data="merge" min="0.self" max="0.self" type="ATTRIBUTE"/> > <IterStep axis="parent" test="*:summary"/> > </AxisPath> > </FNAggr> > > where 0.self is the binary compound key. There's no reason to stop at > compounding in the attribute name. You could also compound in the name > of the element that owns the attribute, resulting in: > > <FNAggr name="count(item)"> > <AxisPath> > <RangeAccess data="merge" min="0.self.summary" > max="0.self.summary" type="ATTRIBUTE"/> > </AxisPath> > </FNAggr> > > The down side to such an index would be increased key sizes in the > attribute index, increased complexity handling numeric data, and some > additional processing time. The up side would be an index with much > more ability to discriminate across common attribute values. > > > -- > RJ > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >

> The DSI Utilities (http://dsiutils.dsi.unimi.it/) are a very> interesting set of classes.

On Wed, Nov 2, 2011 at 11:29 PM, Ross Judson <rossjudson at gmail.com> wrote: > You guys are wizards at making the JVM run fast, without a doubt. I > haven't looked to see how namespaces are handled right now, within the > indexing scheme. In my particular case I do not have namespaces, but > clearly they need to be handled, generally. > > The DSI Utilities (http://dsiutils.dsi.unimi.it/) are a very > interesting set of classes. I have previously used these to construct > indexes of RDF-type triples. They are _extremely_ high performance, > able to process at average rates of hundreds of thousands of tuples > per second. > > The ImmutableExternalPrefixMap was very useful. I created compound > strings (subject-property-object) and stored them. I could then do a > very fast lookup on any prefix, like subject, or subject-property. The > prefix map would supply the applicable interval. By creating another > index compounding (object-property-subject), I could lookup all usages > of a given property value (object), restricting by property name, or > all the way to a specific subject. > > The ImmutableExternalPrefixMap uses an in-memory structure to compute > approximate intervals on any given query; it then reads disk to refine > and answer the query. The net result is that you generally have access > to the results of any given query in one sector read (more or less > like a hash structure), but the data is _ordered_, which means you can > perform range queries, at the cost of reading additional sectors as > necessary. > > Within BaseX you have already converted tokens to byte arrays. > ImmutableExternalPrefixMap does this as well. > > A useful experiment would be to add a new type of index to BaseX that > incorporates one of these prefix maps. > > Creating the compound index looks something like this (altering > ValueBuilder.build()). Replace: > > index.index(data.text(pre, text), pre); > > with: > > byte [] attrName = data.name(pre, Data.ATTR); > int parentElement = data.parent(pre, Data.ATTR); > byte [] elementName = data.name(parentElement, Data.ELEM); > TokenBuilder tb = new TokenBuilder(data.text(pre, text)); > tb.add(';'); > tb.add(attrName); > tb.add(';'); > tb.add(elementName); > index.index(tb.finish(), pre); > > Not sure if I have all of that right, but it shows the idea. When I > run with this the indexes on my data do expand a little, but not too > much (may a 10% growth?). Of course, it will be different for > everyone, depending on their content. > > By checking the database properties you can see that the index has > more keys in it. Next step would be to add a prefix-scanning mode to > the index iteration, in addition to equality scanning. In the example > above I use the ';' character to separate the composite token; (byte)0 > might be more appropriate.

On Fri, Nov 4, 2011 at 12:16 AM, Christian Grün <christian.gruen at gmail.com> wrote: > Just some quick feedback, regarding the extension of index entries: > we'd get even better results by extending the index entries with id's > to the unique location paths.. e.g.: > > <a> > <b>dig</b> > <c>dig</c> > <c>diz</c> > </a> > > Path Index: > 0: a/b > 1: a/c > > Value Index: > dig.0 -> /a/b/text() > dig.1 -> /a/c/text()[.='bla'] > diz.1 -> /a/c/text()[.='blu']