Please optimise my MySQL queries

<?
		
	include("includes/global.php");
	include("includes/static_con.php");
	include("db_config.php");
	include("includes/countries_list.php");
	include("templates/template_inner_top.php");

	/*
		The code below works fine for few records but fails to execute completely for large records
		For fewer records you can see it working at http://dssln.info/search_logistic_providers.php
		For large records you can see its behaviour at http://216.14.120.171/search_logistic_providers.php
		
		Basically this code depends on three tables
		1) transport
		2) services
		3) servinv
		
		transport table contains detail of different transport companies and has about 20,000 records
		services table stores different services which can be provided by transporters and has 235 records
		servinv maps each transporter to each service and tells whether a specific transporter offer this service 
		or not and it has about 4,233,841 records.
		
		My code completely fails to handle such a large number of records so I need some one to help me optimize 
		my queries to make it work
	*/
	
	$search_output="";
	$p="SELECT memid FROM transport";
	if(isset($_REQUEST['action']) && $_REQUEST['action']==search)
	{
		/*
		Please ignore this block for a while
		This block is executed when user performs advance search 
		*/
		$com=$_REQUEST['inp_comp'];
		$q="SELECT DISTINCT transport.memid FROM transport, servinv WHERE tname LIKE '%".$com."%' AND transport.memid=servinv.memid ";
		if($_REQUEST['country']!='any')
		$q.=" AND tcountry LIKE '%".$_REQUEST['country']."%'";
		if($_REQUEST['inp_state']!='')
		$q.=" AND tstate LIKE '%".$_REQUEST['inp_state']."%'";
		$qs="SELECT * FROM services";
		$rs=mysql_query($qs);
		if($rs && mysql_num_rows($rs)>0)
		{
			$xs=0; $not_f=true; $close_brack=false; $any_checked=false;
			
			while($xs<mysql_num_rows($rs))
			{
				//echo $_POST[2];
				$c=mysql_result($rs,$xs,'servid');
				if($_REQUEST[$c]=='on')
				{
					if($not_f){$q.=" AND ( "; $close_brack=true;}
					if(!$not_f){$q.=" OR ";}// else{$q.=" AND ";}
					$q.=" (  ynflag='yes' and servinv.servid=".mysql_result($rs,$xs,'servid').")";
					if($not_f) { $not_f=false; } 
					$any_checked=true;
				}
				if($_REQUEST[mysql_result($rs,$xs,'servid')]!='on')
				{
					
					//$q.=" AND ( ynflag<>'gggg' and servinv.servid=".mysql_result($rs,$xs,'servid').")";
					
					
				}
				
				$xs++;
			}
			if($close_brack){$q.=")";}
		}
	}
		if($_REQUEST[adv]=='true' && $any_checked)
		{
			/*
			This block could also be ignored for a while,
			This block is also only executed incase user performs advance search
			*/
		$p="SELECT DISTINCT transport.memid,tname FROM transport WHERE transport.memid IN (";
		$p.=$q;
		$p.=") ";
		$p2="SELECT DISTINCT transport.memid,tname FROM transport,sponsoredservices,services WHERE transport.memid IN(";
		$p2.=$p;
		$p2.=")";
		$p2.=" OR (transport.memid=sponsoredservices.transporterid AND services.servid=sponsoredservices.serviceid)  ORDER BY sponsoredservices.bidamount DESC";
		//echo $p=$p2;
		}
		else
		{
			//if($com==null) $com=" ";
			/*
			Start From here
			*/
			$p="SELECT * FROM transport WHERE tname LIKE '%".$com."%'";
			if(isset($_REQUEST['country']) && $_REQUEST['country']!='any')
				$p.=" AND tcountry LIKE '%".$_REQUEST['country']."%'";
			if($_REQUEST['inp_state']!='')
				$p.=" AND tstate LIKE '%".$_REQUEST['inp_state']."%'";
		}
		
		$allrecords = mysql_query($p);
		$totalRecords = mysql_num_rows($allrecords);
		$page = 1;
		$maxRec = 25;
		$initRow = 0;
		if(isset($_REQUEST['page']))
		{
			$page = $_REQUEST['page'];
			$initRow = ($page-1)*$maxRec;
		}
		$p.=" LIMIT $initRow, $maxRec";
		$r=mysql_query($p);
		if($r)
		{
			if(mysql_num_rows($r)>0)
			{
				
				$search_output="<p>";
				$search_output.="<table width=90% align=center><tr><td colspan=4><b>Total results found: $totalRecords </td></tr>";
				$search_output.="<tr><th width=4>Index</th><th>Company</th>";

				/*
				Here I am simply getting first 5 services records and saving them in arrays
				*/
				$s="SELECT * FROM services LIMIT 0,5";
				$sr=mysql_query($s);
				$srr_serviceid=array();
				$srr_servicename=array();
				if($sr && mysql_num_rows($sr)>0)
				{
					$sx=0;
					while($sx<mysql_num_rows($sr) && $sx<=5)
					{
					$srr_serviceid[$sx]=mysql_result($sr,$sx,'servid');
					$srr_servicename[$sx]=mysql_result($sr,$sx,'servname');
					$search_output.="<th width=4>".$srr_servicename[$sx]."</th>";
					$sx++;
					}
				}
				/**/
				$search_output.="</tr>";

				$x=0;
				$row=1;
				$max_rec=25;
				$t_pages=ceil($totalRecords/$max_rec);
				if(isset($_REQUEST['page']))
				{
					$index=($_REQUEST['page']-1)*$max_rec;
				}
				$index=$index+1;
				while($x<mysql_num_rows($r))
				{
					$search_output.="<form action=detail_service_provider.php method=post>";
					$search_output.="<input type=hidden name=hdn_id value=".mysql_result($r,$x,'memid').">";
					$search_output.="<tr class=light_tr><td align=center>".$index."</td><td><a href=detail_service_provider.php?hdn_id=".mysql_result($r,$x,'memid').">".mysql_result($r,$x,'tname')."</a></td></td>";
					
					/*
					From here the real problem starts, loop inside loop
					*/
					$lx=0;
					while($lx<count($srr_serviceid))
					{	$ynvalue="<img src=images/icons/no.gif>";
						echo $l="SELECT * FROM servinv WHERE memid=".mysql_result($r,$x,'memid')." AND servid=".$srr_serviceid[$lx]."";
						$lr=mysql_query($l);
						if($lr && mysql_num_rows($lr)>0)
						{
							if(mysql_result($lr,0,'ynflag')=='yes') $ynvalue="<img src=images/icons/yes3.gif>";
						}
						$search_output.="<td align=center>$ynvalue</td>";
						$lx++;
					}
					/**/
					$search_output.="</tr>";
					$search_output.="</form>";
					if($row==$max_rec) break;
					$x++;$row++;$index++;
					
				}
				$search_output.="<tr><td colspan=100 align=right>";
				for($i=1;$i<=$t_pages;$i++)
				{
					$search_output.="<a href=search_logistic_providers.php?action=search&inp_comp=".$com."&page=".$i.">";
					$search_output.=$i;
					$search_output.="</a> ";
				}
				$search_output.="</table></p>";
			}
			else
			{
				$search_output="<div class=error>No Company found</div>";
			}
		}
		else
		{
			$search_output="<div class=\"error\">Error: Their was some error while searching  ".mysql_error()."</div>";
		}

		/**/
		//This is now implemented on serch_logistic_providers_advance.php
		$services_output="";
		$q="SELECT * FROM services LIMIT 0,5";
		$r=mysql_query($q);
		if($r)
		{
			if(mysql_num_rows($r)>0)
			{
			$z=0;$rec=0;
			$services_output="<table width=100%><tr>";
			while($z<mysql_num_rows($r))
			{
				if($rec%4==0){ $services_output.="<tr>"; }
				$services_output.="<td width=15% class=light_td><input type=checkbox name=\"".mysql_result($r,$z,'servid')."\" />".mysql_result($r,$z,'servname')."</td>";

				$z++; $rec++;
			}
			$services_output.="</table>";
			}
			else
			{
			$services_output="<div class=\"error\">No service found! </div>";
			}
		}
		else
		{
			$services_output="<div class=\"error\">Error: Their was some error   ".mysql_error()."</div>";
		}
		/**/
	
?>


                <!--h2>SEARCH LOGISTIC SERVICE PROVIDERS</h2-->
				
                <p>Welcome to the DSSLN Logistics and Supply Chain search engine. This database is designed specifically for the logistics and transportation industry. Please enter your search criteria in the text form below, and click the search button when you are finished. Clicking on any company name from the search results page will give you access to all the data that we have on file about the company. If you have any questions or concerns then please send a note to the administrator from our <a href=contactus.php>contact us</a> page.</p>
                
                <!--<div id="features">-->
                  <!--h2>ADVANCED SEARCH</h2-->
		  <p>
		<fieldset>
		<legend>Search our registered Logistic Companies</legend>
		
		<p>
		<form action=search_logistic_providers.php?action=search&adv=true method=post name=form_search>
		<table width="90%" align="center">
			<tr><td class=dark_td>
                  <b>Company Name: 
			<td><input type="text" size="39" name=inp_comp></input> 
			</td>
			<td align=right><input type="submit" value="-=||Search||=-">
			</td></tr>
			<tr><td class=dark_td>
                  <b>Country: 
			<td><? echo $list_countries2; ?></input> 
			</td>
			<td align=right><input type="button" value="Advance Search" onclick="javascript: location.href=('search_logistic_providers_advance.php')"></td>
			<tr><td class=dark_td>
                  <b>State/Provience: 
			<td><input type="text" size="39" name=inp_state></input> 
			</td></tr>
			<tr><td colspan=3 class=dark_td>
<!--
		  <b>Services:
			<tr><td colspan=3>
			<?
				//This is now implemented on serch_logistic_providers_advance.php 
				echo $services_output; 
			?>
			</td></tr>
-->
		</table>
		</form>
		</fieldset>
		  </p>
                  <div class="clear"> </div>
                <!--</div>-->

                <p>
			<fieldset><legend>Search Results</legend>



			<? echo $search_output; ?>


			</fieldset>
		</p>
                <div class="clear"> </div>
                
              </div>
            </div>
            <div id="gbox-bot"> </div>
          </div>
<!--
          <div id="greybox">
            <div id="greybox-bot">
              <div id="greybox-top">
                <h2>MOST CONVINEIANT & RELIABLE TRANSPORT SERVICES</h2>
                <p><a href="#">Click here for details</a></p>
              </div>
            </div>
          </div>
-->

<?
	include("templates/template_inner_bot.php");

?>