<commit_before><commit_msg>* schema-tradeoffs.txt:  new file discussing the fs schema's impact on users.<commit_after>
The Tradeoff
============

CVS indexes data in a certain way.  When you create a CVS tag, a label
must be applied to every single file in the repository.  It takes O(N)
time, where N is the size of the tree you're tagging.  The tradeoff,
however, is that someone can look at a specific version of a file, and
see *all* the tag-labels attached to it.

Subversion's repository has the data indexed in the other direction.
When you create an SVN tag, it makes a single new directory node that
points to an existing tree.  It takes O(1) (constant) time.  The
tradeoff, however, is that a version of a file is 'shared' by any
number of directory paths.  That means it takes O(N) time to find
every tag that contains the the specific file.


Why?
===

Why does Subversion index data this way?  There are two reasons the
designers chose to do this.

First, it's very nice to have branches and tags in normal directory
space.  It makes them more "browseable" to users, and allows
branch-level access control.

Second, the designers believe that it will result in less waiting time
overall.  Organizations tend to create branches and tags quite
frequently -- much, much more frequently than asking the question
"which tags contain a specific file?"  So if you have to wait a while
for either one operation or the other, it's preferable to make tagging
the instantaneous action.



Questions that Users Ask
========================

Here are some questions subversion users might ask, and how subversion
deals with each question.


1. "What version of foo.c is in tag X?"

This is the easiest question to answer.  Go into the tag-tree, and
look at the version of foo.c it contains.

(This can be done with a simple "svn ls -v URL", where URL is a path
to the specific tag directory.  Look at the first column of numbers.)



2.  "Does tag X contain the latest version of foo.c?"

This is a bit harder to answer.  From question 1, it's easy to see
that tag X contains version N of foo.c.  But how do we know if that's
the *latest* foo.c?  

Running 'svn log' on version N of foo.c won't help, because it only
goes backwards in time.  That is, it only shows predecessor nodes, not
successor nodes.

Subversion-1.0 uses BerkeleyDB.  The only reason 'svn log' shows
predecessor nodes easily is because each node contains a back-pointer
to its predecessor.  It would be extremely painful to search BDB for
successors;  BDB is mostly a glorified hashtable with transactions.

Post-1.0 Subversion, however, will be able to use a SQL backend, and
then it will be very quick and easy to query for node successors.  At
that point, Subversion could make nice "complete history" graphs of
nodes, just like Clearcase does.



3.  "Which tags contain version N of foo.c?"

This is the killer question, and the crux of the Tradeoff mentioned at
the beginning of this document.  Because Subversion has O(1) tagging,
the only way to answer this question is by brute-force searching.  

But there are two consolations to this tradeoff:

   A) "Rethink your work habits"

      From experience, when users ask question #3, it can very often
      be rephrased as a question about a *specific* tag.  Very often,
      the manager doesn't really want to see the exhaustive list of
      every tag containing the file; instead, they simply want to know
      if a *certain* tag has the file.  ("Did we give that file to a
      particular customer?")  It turns into a "type-1" question.

      If you're used to CVS, it's very easy to instantly get the list
      of all tags attached to a file-version.  And therefore you
      habituate to that, and use the tags-list as your main means of
      answering all your type-1 questions.  But it's certainly not
      *required* to answer type-1 questions.

   B) "Build a cache"

      If a brute-force search is ever performed, it shouldn't be too
      difficult to cache the results of the search, because repository
      trees are immutable.  That means the next time somebody runs the
      search, the search becomes *much* smaller.  Eventually, the
      search can dwindle down into what feels like O(1) time, at least
      when viewed from a distance.  :-)

{'fraction_non_alphanumeric': 0.05600743667208924, 'fraction_numerical': 0.0034859400418312805, 'mean_word_length': 3.511530398322851, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3596170', 'n_tokens_mistral': 1182, 'n_tokens_neox': 1134, 'n_words': 702}