title: multi-line search with back reference in large file
body: <p>Suppose I've got a large text file from which I want to get entries based on the following sample:</p>
  
  <pre><code>DATE TIME some uninteresting text,IDENTIFIER,COMMAND,ADDRESS,some uninteresting text
  ... some other lines in between ...
  DATE TIME some uninteresting text DBCALL some uninteresting text IDENTIFIER some uninteresting text
  ... some other lines in between ...
  DATE TIME some uninteresting text PARAM[1]=PARAM1 some uninteresting text IDENTIFIER some uninteresting text
  ...
  </code></pre>
  
  <p>sample with 2 entries:</p>
  
  <pre><code>2014-02-25 09:13:57.765 CET [----s-d] [TL]  [DETAILS:22,6,W1OOKol6IF2DImfgVgJikUb,action_login1,10.1.1.1,n/a,n/a,Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0; .NET4.0C; .NET CLR 2.0.50727; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729; .NET4.0E)]
  2014-02-25 09:13:57.819 CET [------d] [DB] execute {call PKG1.Proc1(?,?,?,?,?,?) } [DETAILS:W1OOKol6IF2DImfgVgJikUb]
  2014-02-25 09:13:57.819 CET [------d] [DB] param[1]=loginname1 [DETAILS:W1OOKol6IF2DImfgVgJikUb]
  
  2014-02-25 09:17:17.086 CET [----s-d] [TL]  [DETAILS:22,13,l3Na0H2bNOTv4AiaelSOS97,action_login1,10.1.1.1,n/a,n/a,Mozilla/5.0 (Windows NT 5.1; rv:27.0) Gecko/20100101 Firefox/27.0]
  2014-02-25 09:17:17.087 CET [------d] [DB] execute {call PKG1.Proc1(?,?,?,?,?,?) } [DETAILS:l3Na0H2bNOTv4AiaelSOS97]
  2014-02-25 09:17:17.087 CET [------d] [DB] param[1]=loginname1 [DETAILS:l3Na0H2bNOTv4AiaelSOS97]
  </code></pre>
  
  <p><strong>Known variables</strong></p>
  
  <ul>
  <li><p>COMMAND = "action_login1"</p></li>
  <li><p>DBCALL = "call PKG1.Proc1"</p></li>
  <li><p>PARAM1 (e.g. value of param[1]) = "loginname1"</p></li>
  </ul>
  
  <p><strong>Variables determined at runtime</strong></p>
  
  <ul>
  <li><p>IDENTIFIER (e.g. session id) = "W1OOKol6IF2DImfgVgJikUb" (example)</p></li>
  <li><p>ADDRESS (e.g. IP address)  = "10.1.1.1" (example)</p></li>
  <li><p>DATE = "2014-02-25" (example)</p></li>
  <li><p>TIME = "09:13:57.765" (example)</p></li>
  </ul>
  
  <p><strong>Variable used to locate related lines</strong></p>
  
  <ul>
  <li>IDENTIFIER (e.g. session id) = "W1OOKol6IF2DImfgVgJikUb" (example) </li>
  </ul>
  
  <p><strong>Expected output</strong></p>
  
  <p>for each group of those 3 lines:</p>
  
  <ul>
  <li>DATE TIME ADDRESS PARAM1 IDENTIFIER COMMAND</li>
  </ul>
  
  <p>sample of the expected output (for the 2 sample records shown above:</p>
  
  <pre><code>2014-02-25 09:13:57.765 10.1.1.1 loginname1 W1OOKol6IF2DImfgVgJikUb action_login1
  2014-02-25 09:17:17.086 10.1.1.1 loginname1 l3Na0H2bNOTv4AiaelSOS97 action_login1
  </code></pre>
  
  <p><strong>Ordering and complexity</strong></p>
  
  <ul>
  <li><p>the shown order of these 3 lines is guaranteed</p></li>
  <li><p>there are another lines between these 3, these 3 are just the ones important here</p></li>
  <li><p>these 3 lines aren't usually very far from each other, usually they all fit into the 2-4kB block (e.g. no need to search until the end of the file when no other related line is found within few kB)</p></li>
  <li><p>the input file can be very large, can't be fully read into the memory</p></li>
  <li><p>it isn't guaranteed that there will be no other entries (or even just their parts - only 1 or 2 lines) of the same type located within each entry (block between the 1st and 3rd line), something like in the simple example below can happen.</p></li>
  </ul>
  
  <p><br/></p>
  
  <pre><code>2014-02-25 09:13:57.765 CET [----s-d] [TL]  [DETAILS:22,6,W1OOKol6IF2DImfgVgJikUb,action_login1,10.1.1.1,n/a,n/a,Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0; .NET4.0C; .NET CLR 2.0.50727; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729; .NET4.0E)]
  2014-02-25 09:17:17.086 CET [----s-d] [TL]  [DETAILS:22,13,l3Na0H2bNOTv4AiaelSOS97,action_login1,10.1.1.1,n/a,n/a,Mozilla/5.0 (Windows NT 5.1; rv:27.0) Gecko/20100101 Firefox/27.0]
  2014-02-25 09:17:17.087 CET [------d] [DB] execute {call PKG1.Proc1(?,?,?,?,?,?) } [DETAILS:l3Na0H2bNOTv4AiaelSOS97]
  2014-02-25 09:17:17.087 CET [------d] [DB] param[1]=loginname1 [DETAILS:l3Na0H2bNOTv4AiaelSOS97]
  2014-02-25 09:13:57.819 CET [------d] [DB] execute {call PKG1.Proc1(?,?,?,?,?,?) } [DETAILS:W1OOKol6IF2DImfgVgJikUb]
  2014-02-25 09:13:57.819 CET [------d] [DB] param[1]=loginname1 [DETAILS:W1OOKol6IF2DImfgVgJikUb]
  </code></pre>
  
  <p><strong>Quantity</strong></p>
  
  <ul>
  <li><p>1st line: lots (all such operations for all users have such entry)</p></li>
  <li><p>2nd line: lots (same as 1st)</p></li>
  <li><p>3rd line: few (only small part of all db calls will match)</p></li>
  <li><p>the complete output can be also very large, we can't rely on the possibility to keep it fully in memory</p></li>
  </ul>
  
  <p><strong>Goal</strong></p>
  
  <ol>
  <li>Search for the line with the appropriate DBCALL value (2nd line in the example), get its IDENTIFIER</li>
  <li>For that IDENTIFIER locate the nearest line (somewhere below, usually it's just the following line but not always) with the appropriate PARAM[1]=PARAM1 (3rd line in the example). If nothing is found then abort this cycle and continue searching the rest of the file at step 1.</li>
  <li>For that IDENTIFIER locate the nearest line (somewhere above) with the appropriate COMMAND (1st line in the example). If nothing is found then abort this cycle and continue searching the rest of the file at step 1.</li>
  <li>Print DATE, TIME, ADDRESS, IDENTIFIER, COMMAND for that line (1st line from the example)</li>
  </ol>
  
  <p>In the worst case it can be perhaps simplified to involve just 2 lines instead of all 3, for better reliability the order would be slightly different:</p>
  
  <ol>
  <li>Search for the line with the appropriate COMMAND (1st line in the example), get its IDENTIFIER.</li>
  <li>For that IDENTIFIER locate the nearest line (somewhere below) with the appropriate PARAM[1]=PARAM1 value (2nd line in the example). If nothing is found then abort this cycle and continue searching the rest of the file at step 1.</li>
  <li>Print DATE, TIME, ADDRESS, IDENTIFIER, COMMAND for that line (1st line from the example).</li>
  </ol>
  
  <p>I managed to get it (more or less) to work (the more simple 2nd scenario) in perl by reading the file by blocks and then doing multi-line regex search using back reference, e.g. with something like:</p>
  
  <pre><code># read 4kB at a time
  local $/ = \4096;
  ...
  my $searchpattern = qr/(\d*-\d*-\d*\s\d*:\d*:\d*\.\d*).*?,(\w*?),$command,.*?param\[1\]=$param1.*?\[ID:(\2)\]/ms;
  ...
  </code></pre>
  
  <p>However the problem is that there are some missed matches - the ones that don't completely fit inside single block that perl reads and processes at a time.
  And as the file is very large, I can't read it whole into the memory.
  Increasing the size of the block isn't solution as there will always be some cases which can span over multiple blocks because of the positioning of block beginning/end.</p>
  
  <p>Does anyone have any idea for how this can be effectively solved (especially speed and memory wise)?</p>
  
  <p>I also tried awk or sed, but couldn't get them to work properly because of the back reference (to reference the same IDENTIFIER) limitations for multi-line processing etc, e.g. something based on this didn't work:</p>
  
  <pre><code>sed -n '/1st line pattern(match-group-1).../,/3rd line pattern\1.../p'
  </code></pre>
  
  <p>Because the back reference from the 1st pattern can't be used in the 2nd one.
  Moreover the sed would print even the entries I'm not interested in - once it finds the 1st matching line for the beginning pattern, it will print everything until the ending pattern is found and if the ending pattern isn't found at all (yes that can happen), it will print everything until the end of the file. That's also something I don't want to happen.</p>
  
  <p><strong>EDIT:</strong>
  added better input sample, clarified description</p>
  
  <p>Notes:</p>
  
  <ul>
  <li>the AWK solution shown by glenn jackman is very nice and works quite well (big thanks for that), however it doesn't cover the possible complexity issues (multiple mixed entries within one block etc). It works only if there are clean blocks of these 3 lines every time. Thus unfortunately it can miss some entries. Example of this solution below, it's supposed to be executed with 2 arguments: 1. PARAM1 (loginname1), 2. input-file</li>
  </ul>
  
  <p><br/></p>
  
  <pre><code>#!/bin/sh
  if [ "$#" -ne 2 ]; then
    echo "Usage: $0 loginname logfile" &gt;&amp;2
    exit 1
  fi
  
  awk -v dbparam="$1" -v cmd="action_login1" -v dbcall="call PKG1.Proc1" '
      $0 ~ ","cmd"," {
          match($0, /^([0-9]+-[0-9]+-[0-9]+)\ ([0-9]+:[0-9]+:[0-9]+.[0-9]+)/, matches);
          date = matches[1];
          time = matches[2];
          match($0, "DETAILS:[0-9]+,[0-9]+,(.*?),"cmd",([0-9]+.[0-9]+.[0-9]+.[0-9]+),", matches);
          sessionid = matches[1];
          ipaddress = matches[2];
          seen_command = 1;
          seen_dbcall = 0;
      }
      seen_command &amp;&amp; $0 ~ dbcall &amp;&amp; $0 ~ "\\[DETAILS:"sessionid {
          seen_dbcall = 1;
      }
      seen_dbcall &amp;&amp; $0 ~ "param\\[1\\]="dbparam &amp;&amp; $0 ~ "\\[DETAILS:"sessionid {
          print date, time, ipaddress, sessionid, cmd;
          seen_command = 0;
          seen_dbcall = 0;
      }
  ' $2
  </code></pre>
  
  <ul>
  <li>the sgauria's proposal might be the way, however how to do it effectively when I can't rely on storing all the intermediate data into the memory? </li>
  </ul>