From: jik@athena.mit.edu (Jonathan I. Kamens)
Subject: ENHANCEMENT: (8 b5) do merging during indexing, rather than after
Organization: Massachusetts Institute of Technology
Date: Thu, 13 Aug 1992 22:52:44 GMT

This patch to irinv.c causes the indexing process to do the merging of
index files *during* the indexing process, rather than doing all the
merging at the end of the indexing.  The advantage of this is a
reduced amount of temporary disk usage, without any increase in the
amount of time used by the program.

I think I've adequately documented how my changes work in the comments
in the changed code.

*** 1.1	1992/08/12 14:51:35
--- irinv.c	1992/08/13 22:49:12
***************
*** 730,735 ****
--- 730,736 ----
  }
  
  
+ #if 0
  /* only works on positive, non-zero numbers, and is slow to boot, yippie */
  static long logcount _AP((long number));
  static long logcount(number)
***************
*** 740,747 ****
--- 741,908 ----
      answer++;
    return(answer);
  }
+ #endif
+ 
+ /*
+  * Originally, the index files produced while building an index were
+  * merged together using a normal binary merge sort.  For example, if
+  * there were 8 files (0 through 7) to be merged, they were merged
+  * in the following order, after all the indexing was finished:
+  *
+  * 0+1 -> 0  2+3 -> 2  4+5 -> 4  6+7 -> 6
+  * 0+2 -> 0  4+6 -> 4
+  * 0+4 -> 0
+  *
+  * The only problem with this is that it means that all of the index
+  * files have to stay around until the entire database has been
+  * indexed.  This means that the amount of disk space needs
+  * temporarily during the indexing grows linearly with the amount of
+  * data being indexed.
+  *
+  * The idea of this routine is to reduce the amount of temporary disk
+  * space used by doing whatever merging it can, DURING the indexing
+  * rather than after it.  The routine gets called whenever an index
+  * file has just been flushed, and it figures out what merging needs
+  * to be performed and does it.
+  *
+  * The merging done by this routine ends up being the same as the
+  * merging done by the old routine at the end of indexing.  However,
+  * it happens in a different order.  For example, once again, if the
+  * total number of index files were 8, this is what would happen (a
+  * number by itself means that it was flushed; number+number->number
+  * refers to a merge):
+  * 
+  * 0 1 0+1->0
+  * 2 3 2+3->2 0+2->0
+  * 4 5 4+5->4
+  * 6 7 6+7->6 4+6->4 0+4->0
+  *
+  * You should be able to convince yourself relatively quickly that the
+  * result of this is that the amount of space needed temporarily
+  * during indexing grows logarithmically with the amount of data being
+  * indexed, rather than linearly.  What's more, no extra time is required.
+  *
+  * There is one complication.  When the total number of files being
+  * indexed is an even power of two, the pattern of merging is regular,
+  * as demonstrated above.  However, if the total number of files is
+  * not an even power of two, things are a bit complicated.  For
+  * example, if there were 11 files instead of 8, we'd have to add this
+  * to the end of the list given above:
+  *
+  * 8 9 8+9->8
+  * 10 8+10->8 0+8->0
+  * 
+  * The algorithm for determining what merges to perform after every
+  * second index file, when the index file just flushed is not the last
+  * one, is simple.  However, the algorithm for determining what to do
+  * on the last file flushed, whether or not it's a power of two, is a
+  * bit more complicated.
+  *
+  * The first algorithm:
+  *
+  * splitter := the number of the file just indexed (starting from 1)
+  * if splitter is odd
+  *   then return
+  * low = splitter - 2  // counting index files from 0
+  * high = splitter - 1 // ditto
+  * twotothe = 1
+  * while splitter is even do
+  *   merge files low and high into low
+  *   high := high - twotothe
+  *   twotothe := twotothe * 2
+  *   low := low - twotothe
+  *   splitter := splitter / 2
+  * done
+  *
+  * The translation from this into the code below should be somewhat
+  * obvious.  What is NOT obvious, however, is all the stuff with
+  * "target", "realhigh" and "where_to_stop", and with the extra loop
+  * wrapped around the code above.  The point of all that is to handle
+  * the second case mentioned above, when we're done indexing and need
+  * to merge everything together.  It works by pretending doing a
+  * series of merges of the first type described above, from the actual
+  * last index file until the next power of two higher than it.  At
+  * each pretended series, only those merges for which the low and high
+  * index files actually still exist are performed.
+  *
+  * In the degenerate case of the second algorithm, when the last index
+  * file being flushed is an even power of two, the outer loop only
+  * runs once and the behavior is the same as in the first algorithm
+  * described above.
+  *
+  * I hope that explains things adequately :-).
+  */
+ 
+ static void do_intermediate_merging _AP((database *db, boolean completely));
+ 
+ static void do_intermediate_merging(db, completely)
+ database *db;
+ boolean completely;
+ {
+   int last = db->index_file_number - 1;
+   int twotothe, low, high, where_to_stop, target, realhigh = last, splitter;
+   char filename[MAX_FILENAME_LEN];
+   char filename2[MAX_FILENAME_LEN];
+ 
+   if (last % 2 == 0) {
+     if (! completely) {
+       return;
+     }
+     else {
+       for (where_to_stop = 1; where_to_stop < last + 1;
+ 	   where_to_stop *= 2) /* empty */;
+     }
+   }
+   else {
+     if (completely) {
+       for (where_to_stop = 1; where_to_stop < last + 1;
+ 	   where_to_stop *= 2) /* empty */;
+     }
+     else {
+       where_to_stop = last + 1;
+     }
+   }
+ 
+   for (target = ((last % 2) == 0) ? last + 2 : last + 1;
+        target <= where_to_stop; target += 2) {
+ 
+     low = target - 2;
+     high = target - 1;
+     twotothe = 1;
+     splitter = target;
      
+     while (((splitter % 2) == 0) && (low >= 0)) {
+       if (low < realhigh) {
+ 	if (! merge_index_file(low, (high > realhigh) ? realhigh : high, db,
+ 			       completely && (! low) &&
+ 			       !probe_file(index_filename(filename, db)))) {
+ 	  panic("Error in merging file %ld into %ld", low,
+ 		(high > last) ? last : high);
+ 	}
+ 	realhigh = low;
+       }
+       high -= twotothe;
+       twotothe *= 2;
+       low -= twotothe;
+       splitter /= 2;
+     }
+   }
+ 
+   if (completely) {
+     if (probe_file(index_filename(filename, db))) {
+       merge_index_file(-2L, 0L, db, true);
+     }
+     else if (last == 0) {
+       touch_file(index_filename_with_version(1, filename, db));
+       merge_index_file(0L, 1, db, true);
+       /* rename 0 into the final name */
+       rename(index_filename_with_version(0L, filename2, db),
+ 	     index_filename(filename, db));
+     }
+   }
+ }
  
+ #if 0
  static void merge_index_files _AP((database* db));
  
  static void merge_index_files(db)
***************
*** 810,815 ****
--- 971,977 ----
  	   index_filename(filename, db));
    }
  }    
+ #endif
  
  /* ============================================ */
  /* ===  Flushing the memory version of the  === */
***************
*** 933,941 ****
    add_stop_words(db->the_word_memory_hashtable);
  
    waislog(WLOG_MEDIUM, WLOG_INDEX,
! 	  "Done flushing");
    /* scan_index_blocks(filename); */
  
    if(completely){
      waislog(WLOG_MEDIUM, WLOG_INDEX,
  	    "Merging %ld files",
--- 1095,1104 ----
    add_stop_words(db->the_word_memory_hashtable);
  
    waislog(WLOG_MEDIUM, WLOG_INDEX,
! 	  "Done flushing version %ld", db->index_file_number - 1);
    /* scan_index_blocks(filename); */
  
+ #if 0
    if(completely){
      waislog(WLOG_MEDIUM, WLOG_INDEX,
  	    "Merging %ld files",
***************
*** 944,949 ****
--- 1107,1115 ----
      waislog(WLOG_MEDIUM, WLOG_INDEX,
  	    "Done merging.");
    }
+ #else
+   do_intermediate_merging(db, completely);
+ #endif
  }
  
  long finished_add_word(db)

Jonathan Kamens                                         jik@MIT.Edu
MIT Information Systems/Athena              Moderator, news.answers
    (Send correspondence related to the news.answers newsgroup
        {and ONLY correspondence related to the newsgroup}
                 to news-answers-request@MIT.Edu.)
Xref: sparky comp.infosystems.wais:376 comp.lang.postscript:4327 alt.security:4169