{"thread":{"id":"10108","subject":"what's a useful definition of full text index on a repository?","startedAt":"2007-10-01T16:33:47Z","lastAt":"2007-10-02T15:48:53Z","messageCount":4,"participants":["David Tweed","Jon Smirl"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"54496","messageId":"e1dab3980710010933u6a7324f0wa8230d67ee0846e2@mail.gmail.com","threadId":"10108","inReplyTo":null,"subject":"what's a useful definition of full text index on a repository?","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2007-10-01T16:33:47Z","receivedAt":"2007-10-01T16:33:47Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"Basically a \"blue sky\" question about full-text indexing git repositories.\n\nA while back, whilst talking about overall git structure\n(see\n\nhttp://marc.info/?l=git&m=118891945402778&w=2\n\n), Jon Smirl raised the question of putting a full-text index on a\nrepository. I doubt I full text index is of much use on a code\nrepository because the question tends to be focussed around either\nreleased versions or immediate git-blame stuff. However, for\nrepositories of things like evolving documents/presentations/notes\nwhere content is deleted because it doesn't fit the context rather\nthan being superceded by better stuff, it might be more natural to\nsearch for \"where's that paragraph I wrote on 'human' 'vision' and\n'kinematic' 'feedback' ?\". So I got to thinking about experimenting\nwith a full text index and even started writing some code. However, I\nthen realised that it's not obvious what the most useful definition of\na full text index is on evolving files. (To be clear, I'm _not_\nthinking about changing the database fundamentals as discussed in the\nreferenced thread and indeed would put the full-text index into a\ndifferent file that just references the existing git db stuff\nprecisely because I doubt the text index will be of use to most\npeople.)\n\nA \"classical\" full-text index seems inappropriate because, if I've got\na long text document that in a blob in commit n1 uses word 'x' in one\nsection and the corresponding file in descendant commit n2 has the\nsame text using word 'x' but has changes to a different section of the\ndocument, there's probably no point showing me both documents (and I\ncan always track through the history once I've got one (commit-id,file\npair)). So in the case of a single word, a \"useful\" definition would\nbe the entry for word w in the full-text index should consist of those\n(commit-id,file) pairs whose diff with their parent contains an\naddition of text containing word w. (This will catch the creation of\nthe text containing w and then precisely those files which are close\nmodifications of it but ignore changes to other areas.) This seems to\nmake sense for a single word. Let's call this the \"appearance diff\"\ndefinition of a full text index.\n\nHowever, things become unclear if you consider a query with multiple\nwords. Consider the simplest case of a linear history where commit n0\nadds word \"vision\" to file p1.tex (with respect to its single parent),\nthere are some intermediate commits and then commit n7 adds word\n\"feedback\" to p1.tex. Then there's no commit whose diff with its\nsingle parent contains both words \"vision\" and \"feedback\". In the\nlinear history case you could imagine trying to find the first commit\nwhich is a child of _all_ the commits under the \"appearance diff\"\ndefinition. However, that clearly doesn't \"obviously\" extend to\ngeneral full DAG histories, and in any case it's probably not fully\ncorrect even in the linear case. So maybe a different definition would\nbe better. So I'm just throwing the question out to the list in case\nanyone has any better ideas for what a full-text index on an evolving\nset of files ought to be.\n\n(One question is \"why do you want to build a table rather than\nactively search the full git repo for each query (ie, combination of\nwords) as you make it?\" My primary motivation is that I might in the\nfuture like to do queries on some sort of low processor power\nUMPC-type thing, having built the file containing a \"full text index\"\ndata structure for the index on a quite beefy desktop. The other point\nis that searching natural language text based on a fallible memory\nyou're more likely to try different combinations of search terms\niteratively to try and hit the right one, so there might be some point\nin trying to build an index.)\n\nAnyway, it's currently an idle speculation,\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"we had no idea that when we added templates we were adding a Turing-\ncomplete compile-time language.\" -- C++ standardisation committee\n"},{"id":"54498","messageId":"9e4733910710011025y790800b5s4e8cf65409bc2cce@mail.gmail.com","threadId":"10108","inReplyTo":"e1dab3980710010933u6a7324f0wa8230d67ee0846e2@mail.gmail.com","subject":"Re: what's a useful definition of full text index on a repository?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-10-01T17:25:24Z","receivedAt":"2007-10-01T17:25:24Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 10/1/07, David Tweed <david.tweed@gmail.com> wrote:\n> Basically a \"blue sky\" question about full-text indexing git repositories.\n>\n> A while back, whilst talking about overall git structure\n> (see\n>\n> http://marc.info/?l=git&m=118891945402778&w=2\n>\n> ), Jon Smirl raised the question of putting a full-text index on a\n> repository. I doubt I full text index is of much use on a code\n> repository because the question tends to be focussed around either\n> released versions or immediate git-blame stuff. However, for\n> repositories of things like evolving documents/presentations/notes\n> where content is deleted because it doesn't fit the context rather\n> than being superceded by better stuff, it might be more natural to\n> search for \"where's that paragraph I wrote on 'human' 'vision' and\n> 'kinematic' 'feedback' ?\". So I got to thinking about experimenting\n> with a full text index and even started writing some code. However, I\n> then realised that it's not obvious what the most useful definition of\n> a full text index is on evolving files. (To be clear, I'm _not_\n> thinking about changing the database fundamentals as discussed in the\n> referenced thread and indeed would put the full-text index into a\n> different file that just references the existing git db stuff\n> precisely because I doubt the text index will be of use to most\n> people.)\n\nThis is what full text is used for with code:\nhttp://lxr.mozilla.org/\n\nIt makes grep instant.\n\nFor source code you can take the full text concept further and store\nparse trees. This lets you instantly find the callers of a function,\nor all users of a variable.\n\nOnce you have parse trees in the database you can offer refactoring\ntoo. I have used powerful proprietary system that used parse trees to\nmake complicated refactoring quite easy.\n\nNote that a parse tree database doesn't have to be generated for all\nthe old revisions, it is mainly usefully for the current HEAD. Same\nfor the full text index. When you generate this data you end up with\nlots of tiny files that need to be kept in sync with the current HEAD.\ngit is good for holding those files.\n\nYou want all this analysis coordinated with git so that when you\ncommit a change the right parts get regenerated. Linux seems to be\nmissing good, automated refactoring assistance. Instead the kernel\njanitorial work is being done manually.\n\nAn example I noticed today. Use of pr_debug() is chaotic in the kernel\nsource. Many drivers have #if DEBUG their own versions of pr_debug().\nFixing everything to have consistent use of pr_debug is a refactoring\nthat could probably be mostly automated.\n\nMozilla is undergoing some massive automated rewrites.\nhttp://blog.mozilla.com/tglek/category/decomtamination/\n\nFull text indexing can also achieve high levels of compression as\nstated in the earlier threads. It is full scale dictionary\ncompression. When it is being used for compression you want to apply\nit to all revisions.\n\n> A \"classical\" full-text index seems inappropriate because, if I've got\n> a long text document that in a blob in commit n1 uses word 'x' in one\n> section and the corresponding file in descendant commit n2 has the\n> same text using word 'x' but has changes to a different section of the\n> document, there's probably no point showing me both documents (and I\n> can always track through the history once I've got one (commit-id,file\n> pair)). So in the case of a single word, a \"useful\" definition would\n> be the entry for word w in the full-text index should consist of those\n> (commit-id,file) pairs whose diff with their parent contains an\n> addition of text containing word w. (This will catch the creation of\n> the text containing w and then precisely those files which are close\n> modifications of it but ignore changes to other areas.) This seems to\n> make sense for a single word. Let's call this the \"appearance diff\"\n> definition of a full text index.\n\nYou would full text index the expanded source text for each revision,\nnot the delta. There are forms of full text indexes that record the\nwords position in the document. They let you search for \"vision NEAR\nfeedback\"\n\nA good feature of this is finding when a variable or function was first added.\n\n>\n> However, things become unclear if you consider a query with multiple\n> words. Consider the simplest case of a linear history where commit n0\n> adds word \"vision\" to file p1.tex (with respect to its single parent),\n> there are some intermediate commits and then commit n7 adds word\n> \"feedback\" to p1.tex. Then there's no commit whose diff with its\n> single parent contains both words \"vision\" and \"feedback\". In the\n> linear history case you could imagine trying to find the first commit\n> which is a child of _all_ the commits under the \"appearance diff\"\n> definition. However, that clearly doesn't \"obviously\" extend to\n> general full DAG histories, and in any case it's probably not fully\n> correct even in the linear case. So maybe a different definition would\n> be better. So I'm just throwing the question out to the list in case\n> anyone has any better ideas for what a full-text index on an evolving\n> set of files ought to be.\n>\n> (One question is \"why do you want to build a table rather than\n> actively search the full git repo for each query (ie, combination of\n> words) as you make it?\" My primary motivation is that I might in the\n> future like to do queries on some sort of low processor power\n> UMPC-type thing, having built the file containing a \"full text index\"\n> data structure for the index on a quite beefy desktop. The other point\n> is that searching natural language text based on a fallible memory\n> you're more likely to try different combinations of search terms\n> iteratively to try and hit the right one, so there might be some point\n> in trying to build an index.)\n\nI do admit that these indexes are used to make functions that can be\ndone with brute force faster. As computers get faster the need for\nthese decrease. Right now the size of the kernel repo is not growing\nfaster than the progress of hardware. If you went back are tried to do\nthese things on a 386 you'd be shouting for indexes tomorrow.\n\n>\n> Anyway, it's currently an idle speculation,\n>\n> --\n> cheers, dave tweed__________________________\n> david.tweed@gmail.com\n> Rm 124, School of Systems Engineering, University of Reading.\n> \"we had no idea that when we added templates we were adding a Turing-\n> complete compile-time language.\" -- C++ standardisation committee\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"54546","messageId":"e1dab3980710020234l1951349r38657c68aa7ef5@mail.gmail.com","threadId":"10108","inReplyTo":"9e4733910710011025y790800b5s4e8cf65409bc2cce@mail.gmail.com","subject":"Re: what's a useful definition of full text index on a repository?","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2007-10-02T09:34:19Z","receivedAt":"2007-10-02T09:34:19Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On 10/1/07, Jon Smirl <jonsmirl@gmail.com> wrote:\n> This is what full text is used for with code:\n> http://lxr.mozilla.org/\n>\n> It makes grep instant.\n\nI'd thought that keeping a full-text index of all my program files was\nmy dirty little secret that shows I'm not a \"pro\" programmer ;-)\n\n> For source code you can take the full text concept further and store\n> parse trees.\n[details snipped]\n\nThis sounds interesting in principle but is beyond what I'm thinking\nin practice (particularly since I'm not in the \"C is the only language\nworth ever using\" camp).\n\n> Full text indexing can also achieve high levels of compression as\n> stated in the earlier threads. It is full scale dictionary\n> compression. When it is being used for compression you want to apply\n> it to all revisions.\n\nWell, as I say I'm not convinced it makes sense to integrate this with\nexisting pack stuff precisely because I don't think it's universally\nuseful. So you seem to end up with all the usual tricks, eg, Golomb\ncoding inverted indexes, etc, _if_ you treat each blob as completely\nindependent. I was wondering if there was anything else you can do\ngiven the special structure that might be both more useful and more\ncompact?\n\n> You would full text index the expanded source text for each revision,\n> not the delta. There are forms of full text indexes that record the\n> words position in the document. They let you search for \"vision NEAR\n> feedback\"\n\nWell, the kind of question I was thinking was \"clearly you can use the\nexisting sort of full text indexing (eg, the stuff covered in Cleary,\nWitten & Bell's covered Managing Gigabytes), but is that the most\nuseful way of doing things in the context of an evolving database?\" If\nyou treat every blob as essentially a different document there are\nindexing tools out there already you can use. What I was wondering was\nif it's really that useful to a human user to report every revision of\na document containing those keywords even if the differences are in\nother parts of the text far removed from the text containing the\nkeywords. I don't know the answer.\n\n> > (One question is \"why do you want to build a table rather than\n> > actively search the full git repo for each query (ie, combination of\n> > words) as you make it?\" My primary motivation is that I might in the\n> > future like to do queries on some sort of low processor power\n> > UMPC-type thing, having built the file containing a \"full text index\"\n> > data structure for the index on a quite beefy desktop. The other point\n> > is that searching natural language text based on a fallible memory\n> > you're more likely to try different combinations of search terms\n> > iteratively to try and hit the right one, so there might be some point\n> > in trying to build an index.)\n>\n> I do admit that these indexes are used to make functions that can be\n> done with brute force faster. As computers get faster the need for\n> these decrease. Right now the size of the kernel repo is not growing\n> faster than the progress of hardware. If you went back are tried to do\n> these things on a 386 you'd be shouting for indexes tomorrow.\n\nThe other point is that direct searching is easier because you know\nexactly what the query is at the point you have access to the full\ntext, whereas building an index you want to extract no more and no\nless information to be able to answer all allowed queries. But I still\nlike the idea of getting a UMPC type thing if they become affordable.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"we had no idea that when we added templates we were adding a Turing-\ncomplete compile-time language.\" -- C++ standardisation committee\n"},{"id":"54565","messageId":"9e4733910710020848l496ee49ej4c243b5f62bca6c0@mail.gmail.com","threadId":"10108","inReplyTo":"e1dab3980710020234l1951349r38657c68aa7ef5@mail.gmail.com","subject":"Re: what's a useful definition of full text index on a repository?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-10-02T15:48:53Z","receivedAt":"2007-10-02T15:48:53Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 10/2/07, David Tweed <david.tweed@gmail.com> wrote:\n> > Full text indexing can also achieve high levels of compression as\n> > stated in the earlier threads. It is full scale dictionary\n> > compression. When it is being used for compression you want to apply\n> > it to all revisions.\n>\n> Well, as I say I'm not convinced it makes sense to integrate this with\n> existing pack stuff precisely because I don't think it's universally\n> useful. So you seem to end up with all the usual tricks, eg, Golomb\n> coding inverted indexes, etc, _if_ you treat each blob as completely\n> independent. I was wondering if there was anything else you can do\n> given the special structure that might be both more useful and more\n> compact?\n\nDictionary compression can be used without full-text indexes. It is\njust really easy to build the full-text index if the data is already\ndictionary compressed. Dictionary compression works for everything\nexcept binary or random data.\n\nGit is already using a small scale dictionary compressor via zip. I\nsuspect doing a full scale dictionary for a pack file and then using\narithmetic encoding of the tokens would provide substantially more\ncompression. The big win is having a single dictionary instead of a\nnew dictionary each time zip is used.\n\nWhen we were working on Mozilla, Mozilla changed licenses three times.\nThe license text ended up taking about 30MB in the current scheme.\nWith full dictionary compression this would reduce down to a few kb.\n\nMore compression is good for git. It means we can keep more data in\nRAM and reduce download times. With current hardware it is almost\nalways better to trade off CPU to reduce IO.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"}]}