Tag Archives: php-mysql

MySQL query with ORDER BY,GROUP BY to remove duplicate rows after ordering

Apparently this is a widely discussed issue with MySQL; many newbies (like me) wanting to SELECT rows from a table, where they know there are duplicates of some field ‘a’ which they want unique, but making sure that the selected row has the field ‘b’ with the lower, highest, longest or shortest (whatever) value among the duplicates… well, these newbies first try and make a query like:

SELECT a, b, c FROM table WHERE <conditions> ORDER BY b DESC GROUP BY a

and they get errors and realize it’s not possible, because MySQL syntax wants the GROUP BY clause to come before the ORDER BY one, like:

SELECT a, b, c FROM table WHERE <conditions> GROUP BY a ORDER BY b DESC

In this case though, rows first get grouped, and only after duplicates are removed, they get ordered (pretty much useless for what we need).

How to go about first ordering duplicates the way we need, and then remove the rest?

To cut to the chase, this is how:

SELECT t.a, t.b, t.c 
  FROM table t
  JOIN (SELECT MIN(b) as b
    FROM table
    GROUP BY a) t2 ON t2.b = t.b
  WHERE <conditions>
  GROUP BY a
  ORDER BY NULL

What this “query skeleton” does, is ordering the rows by the field ‘b’ (ASC order, since MIN() function is used, otherwise you would be using MAX(), or anyway the function that better suits your needs) inside the JOIN operator, and then grouping these rows by field ‘a’ in the outer query; the ORDER BY NULL clause at the end is to avoid MySQL doing unnecessary ordering steps as the rows have already been ordered by the GROUP BY clause. Effective, sure, but incredibly slow query.

I thought I could go on by just using this, yet I wasn’t satisfied, as I became a performance optimization junkie during my PHP/MySQL learning curve. So I thought, what if I just get the raw rows, and order them later as I need in a PHP array?

So, let’s examine this approach instead:

$results=doquery("
  SELECT a, b, c
    FROM table
    WHERE <conditions>
  ");
$datagrid=array();
while ($slot=mysql_fetch_array($results)) $datagrid[]=$slot;
sort($datagrid);
$compare="";
foreach ($datagrid as $k=>$row)
  if ($row[0]==$compare)
    unset($datagrid[$k]);
  else
    $compare=$row[0];

After this, the multidimensional array $datagrid contains the data that you need. Some explaining is in order:

  • the SQL query returns the unprocessed rows corresponding to the WHERE conditions you specified, so you will get duplicate rows, in an arbitrary order
  • after inserting the rows data inside a multidimensional array, the sort() PHP function takes care of sorting this array depending on the sub-arrays in it, first by subarray[0], then by subarray[1] and so on (let’s open a parenthesis here: if you search for “php sort multidimensional array” on the internet, you will find all sorts of hand-made custom scripts to do this, as if sort() alone wasn’t enough; well, I have PHP5 on my hosting, and I threw a multidimensional array at it… it got splendidly sorted just as I needed, so it worked for me; in case it doesn’t for you, look on php.net function_sort user comments, there are all kinds of custom multi-sorting scripts in there, even if nothing is as fast as just sort() which is a builtin function)
  • a $compare string is initialized, and used on the following foreach loop to unset() all the subarrays where the element [0] (our ‘a’ field) is the same as the previous subarray’s [0], thus effectively pruning duplicates after the first occurrence

After this you can pass the resulting array to another routine which will process it as needed.

To take performance even further, in case you need to do a simple processing on the resulting ordered&grouped array, you can change the last foreach of the previous routine into:

foreach ($datagrid as $row)
  if ($row[0]!=$compare) {
    $compare=$row[0];
    <processing routine in here>
  }

Again, to explain, this foreach loop doesn’t care about unsetting the duplicated subarrays, but just runs your processing code on the first occurence of a subarray, ignoring the others; with this approach, you are cutting several times on the excecution time:

  1. you presumably save time as you don’t need another foreach loop to process the pruned multidimensional array, since you do everything in the first and only foreach
  2. you avoid issuing as many unset()‘s as the duplicate rows are
  3. you save on cycles and memory needed to define a new array to store the pruned data, as you only work on the very first array you built on the SQL results
  4. you simplify the foreach because you are not requesting an associative result anymore ($k=>$row) but only request the element value

With my benchmark (on a VERY reduced sets of rows, I must admit), I measured a performance increase of a whopping one hundred times (yes, exactly 100X faster) for the PHP ordering/pruning, if compared to MySQL “double-GROUP BY” approach (0.08 seconds for MySQL/PHP, against 8 seconds for MySQL only, for 100 iterations). Your results may vary on very large, or of a different kind, data sets, anyway testing will not hurt. From my 100x speed experience, there’s still plenty of leeway space.

PHP search string functions performance is “needle” dependent

I was playing with some templating benchmarks in my post before this one, and bumped into an interesting find regarding the way strpos works, and consequently all similar “search (and replace)” functions like str_replace, strrpos, stripos, str_ireplace, substr_replace, even preg_match and preg_replace (I tested only str_replace and preg_match out of these, but I assume they will all bear the same results).

  1. From here on  am using the php.net convention, and will call “needle” the string you’re searching for, and “haystack” the string inside of which you’re executing the search.
  2. Knowing these results will only be useful if you can choose which “needles” to put in the “haystack” to be searched for in a later time, hence only if you’re building a template.
  3. I serched if someone else found this already, but this doesn’t appear to be the case, so if I am selling for new already known things just don’t bash me.

So let’s say you’re creating a template scheme, where you insert several tags that need to be replaced by the dynamically generated content of your website. You can call them whatever you want as long as they are unique strings inside the template, so for example %tag% or {tag} or <!–tag–> or ~tag~ (or just whatever). Maybe you think that choosing which delimiting chars to use for the tag name is only up to your personal tastes, and I did too before discovering this by accident, but I am going to guess that if the template contains well formed HTML code, then using ~tag~ is going to be much faster than using <!–tag–>.

The general principle is, searching for a needle beginning with a “rare” character is much faster than searching for a needle starting with a commonly used character inside the haystack.

For example, if your haystack is an excerpt from an ebook, searching for “%hello” (if present) will be way faster than searching for “hello”. The reason for this? The function in C that searches for the string, starts by searching for its first character, if found checks if the following one matches, and so on; so if you’re searching for “hello” the function will pause at every “h” to see if after that there’s an “e”, and if yes then checks if there’s and “l” and then another “l”, yet if the word is “hellish”, the function will not find the ending “o”, and will have to discard the work and time spent and go on with the search. The “%” character on the other hand is pretty rare inside of a “normal text”, if not unique, so the function will have to “pause” way less times before hitting a full match.

Let’s put it to the test, this is the routine:

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"malesuarda");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "malesuarda $testpos: ".$creationtime."<br />";

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"%malesuada");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "%malesuada $testpos: ".$creationtime."<br />";

Let’s do some explaining: $test is a fairly long string that I previously defined inside the code (it is made of a lorem ipsum kind of text, several paragraphs amounting to almost 13kb), inside of which I took a random word, “malesuada“, which is repeated several times, and I made two occurrences of this word slightly different, to render them unique; they were both towards the end of the string, I changed one into malesuarda adding a”r”, and another one (further away in the string) into %malesuada, then just loaded the PHP script; I echoed the value of $testpos as well, to confirm that the strings were actually found.

As expected, here are the results:

malesuarda 10970: 3.5609
%malesuada 11514: 0.7632

Replacing strpos with any other functions listed at the beginning of this article will deal similar results.

  This article has been Digiproved

PHP templating, preg_match, file_get_contents and strpos, the fastest

While working on the website of reecycle.it, il frecycling italiano per il riciclo degli oggetti, I am spending my resources also on reducing at most the load on the Apache server of my italian shared hosting, Tophost, so i decided to make some benchmarks to see which was the best speed I could load the templates at, using different methods (a template is a “model” of a page -or part of-  written in HTML code, inside which the dynamic values loaded by the website engine are inserted).

All the templates used by reecycle.it were initially created as several .html files (one per each template) with several %tags% substituted by the str_replace() function before the output, but I thought that maybe there were different, faster ways to obtain the same result; a page can contain up to 5 or more different templates (general layout, login panel, simple search widget, search results table, and single row of the search results table), so each page could tell the server to access and load 5 different files on the hard disk (we are ignoring the disk cache for simplicity); maybe reading a single, bigger file containing all of the templates, loading it into memory, and later extracting the needed parts, is faster? This path can be taken in two ways, either by writing two “clean” lines of code using preg_match() and a regular expression, or by using a rather less “elegant” but strictly more performant combo of strpos() and substr() which instead needs several more lines of code.

In other words, I needed to know which one of the three (separate template files, single big template with regexp extraction, and single big template with strpos/substr extraction) was faster. I already knew preg_match was heaps slower than strpos/substr, yet I included it in the test for the sake of completeness.

This is the routine I used:

<?php
$creationstart=strtok(microtime()," ")+strtok(" ");

for ($i=0;$i<1000;$i++) {
 $text=file_get_contents("full.html");
 for ($n=1;$n<=8;$n++) {
 preg_match("/<!--{$n}\(-->(.*)<!--\){$n}-->/s",$text,$matches);
 $html[$n]=$matches[1];
 }
}

$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "preg_match: ".$creationtime."<br />";

/////////////////
$creationstart=strtok(microtime()," ")+strtok(" ");

for ($i=0;$i<1000;$i++) {
 $text=file_get_contents("full.html");
 for ($n=1;$n<=8;$n++) {
 $start=strpos($text,"<!--$n(-->")+strlen("<!--$n(-->");
 $ending=strpos($text,"<!--)$n-->");
 $html[$n]=substr($text,$start,($ending-$start));
 }
}

$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "strpos/substr: ".$creationtime."<br />";

////////////////////
$creationstart=strtok(microtime()," ")+strtok(" ");

for ($i=0;$i<1000;$i++) {
 for ($n=1;$n<=8;$n++) {
 $html[$n]=file_get_contents($n.".html");
 }
}

$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "file_get_contents: ".$creationtime."<br />";

where full.html is the single HTML file containing all the templates (a total of 8, consisting in paragraphs in lorem ipsum style, of different length), identified by <!--templatenumber(--> and <!--)templatenumber--> between which was the code to extract, while the single template files were named from 1.html to 8.html.

What the code does is, for each method it repeats 1000 iterations in which every single template is loaded, from 1 to 8, and measures the needed time to complete. This usage is not very realistic, as the template code is actually several lines of HTML code instead of few long lines of text, and templates are never loaded all together, but only those which are actually needed to draw the page; anyway, better performance in this test means better performance in real-life use (WRONG! check bottom for more details).

So, this was the result:

preg_match: 1.8984
strpos/substr: 0.0681
file_get_contents: 0.1352

Final times were obviously different at each page refresh, from a minimum (for preg_match) of 1.4s up to a maximum of 3s, anyway the relationship between them remained the same, that is the strpos/substr combination was two times faster than file_get_contents called for each file, yet what surprised me is how preg_match method is almost 30 times slower than strpos/substr, and hence 15 times slower than asking the server to read several different files together (I suppose this was due to the disk cache in action).

On a side note, the tech support of my hosting, inquired about this, suggested me to drop reading separate files in favour of reading a single file and using preg_match… go figure.

UPDATE:

I just went and tested this benchmark with real templates off reecycle.it… oh how much I was wrong.
I made a function on reecycle.it to fetch the requested template, that when the template inside the big file is missing, loads the single file template, returns it, and adds the missing template to the big single file, so after a while I got a 37kb supertemplate.tpl containing all of the templates of the website. I just changed the routines in the example above, to use the real files of the templates… and behold, the results were inverted! Using file_get_contents() on several files was two times faster than using strpos/substr on a single big file. No matter how I changed it, several, separate small files were still much faster than a single big file.

I blame it on two things: the file is actually big, so string functions have to deal with a big chunk of data to process, and especially the tag formats, since the template delimiters, practically in HTML comment format, begin with the “less than” symbol which is bound to be repeated lots of times inside HTML code, maybe confusing the strpos function.

In fact, in the templates archive file I modified the delimiting tags so they were like {tag(} and {)tag} instead of using the html comment tags <!–…–>, and the results of the benchmark went back to normal, being faster for the strpos/substr combo on the single file archive than with file_get_contents on several separate files, and the more the template requests, the faster the strpos/strsub method if compared to file_get_contents… see results of my next post.

Se vuoi cambiare la tua password, o non la ricordi, inserisci qui l’indirizzo di posta elettronica con cui ti sei registrato<br />
<form method=”post” action=”index.php”>
<table>
<tr>
<td class=”dida”>
email
</td>
<td class=”dati”>
<input type=”text” name=”resetmail” />
</td>
</tr>
<tr>
<td colspan=”2″>
<input type=”hidden” value=”resetpassword” name=”action” />
<input type=”submit” value=”Invia mail di reset” name=”sendresetpassword” />
</td>
</tr>
</table>
</form>

  This article has been Digiproved