Variantes d'écriture d'une requête SQL simple


28 octobre 2007

Présentation

Pendant la lecture du chapitre 6, pages 126 et 127, du livre de Joe Celko "Sql Programming Style", Elsevier, 2005, j'ai eu envie de vérifier un schéma et une requête qu'il exécute sur un certain type de données.

Les données sont des prêts pour lesquels on stocke des paiements successifs qui peuvent avoir chacun un status (S, U ou F) qui détermine, si on veut, un paiement a échéance, en retard ou envoyé (la signification de ce status n'a pas d'importance). Il cherche, étant donné ce schéma, la liste des prêts dont TOUS les paiements ont le status 'F'.

Simple ? Oui, mais on peut diverger quand à la construction des requêtes possibles pour trouver ce résultat.

Le schéma et la solution de Celko

Son schéma, que je reprend, est le suivant :

CREATE TABLE loans (
        loanId int not null,
        paymentId int not null,
        paymentStatus = ENUM('F', 'U', 'S'),
        primary key (loanId, paymentId)
    )

Sa solution est élégante et rapide (cf ci-dessous) et je voulais savoir si on pouvais faire mieux. Tout d'abord présentons sa solution :

select loanId, count(*) as nbPayments
        FROM loans
        GROUP BY loanId
        HAVING MAX(paymentStatus)='F' and MIN(paymentStatus)='F';

On parcourt donc la totalité de la table et on extrait bien les prêts dont les paiements n'ont pas d'autres statuts que 'F'.

Les alternatives

J'ai deux solutions alternatives. La première utilise deux sous-requêtes, une qui donne pour chaque prêts le nombre de paiements ayant le statuts 'F' et une autre qui donne le nombre de paiements total. Une clause WHERE est présente pour ne garder que les prêts pour lesquels ces décomptes sont égaux.

select GlobalStats.loanId, GlobalStats.nbPayments
        from
        (select loanId, count(*) as nbPayments from loans where paymentStatus='F' group by loanId) as FStats,
        (select loanId, count(*) as nbPayments from loans group by loanId) as GlobalStats
        where FStats.loanId=GlobalStats.loanId and FStats.nbPayments=GlobalStats.nbPayments;

La deuxième solution calcule directement pour chaque prêt le nombre de paiements et le nombre de paiements ayant le statut 'F', en utilisant la somme d'une valeur issue d'un IF.

select loanId, nbPayments
        from (
            select loanId, count(loanId) as nbPayments, sum(if(paymentStatus='F', 1, 0)) as nbFPayments from loans group by loanId
        ) as inter
        where inter.nbPayments=inter.nbFPayments;

Conclusion

Le résultat ? Déprimant ! Mes deux solutions peuvent être plus simples à comprendre au premier coup d'oeil mais sont jusqu'à 30% plus lente à l'exécution, alors que la solution de Celko qui peut surprendre au premier regard, est en fait très simple à comprendre, plus rapide et plus constante dans son temps d'exécution.

Pour tester ça j'ai utilisé un petit script PHP qui initialise la table, la remplit avec des milliers de données, règle certains prêts de manière à ce qu'ils apparaissent dans le résultat des requêtes de cette page et compare les temps d'exécution des trois variantes.

C'est moi ou Joe Celko ressemble drôlement à Anton Lavey ?

Le pays d'une adresse IP


19 août 2007

Obtenir le pays correspondant à une adresse IP

Vous vous souvenez de GeoIp, produit de la société MaxMind ? Ils ont un exécutable à installer sur un serveur pour obtenir le pays correspondant à une adresse IP.

J'avais deux soucis quand j'utilisais ce produit :

  • d'une part j'avais affaire à un binaire dont je n'avais pas les sources, et faire tourner quelque chose d'opaque sur un serveur est une invitation au hack pour des escrocs russes et
  • d'autre part j'étais tributaire de leurs mises à jour des données également opaques.

Tout peut se résoudre en utilisant le site ip-to-country. Leur méthode ? Faire que le pays d'une adresse IP soit obtenu par une simple requête SQL, ce qui donne :

  • qu'il n'y a plus de binaire douteux à installer sur mon précieux serveur de prod
  • et que je bénéficie de toutes les facilités du language SQL et de ses implémentations de mon choix (MySQL et PosgreSQL).

Pour fixer les idées la requête en question est presque aussi simple que celle-ci :

select countryName from ip2Country where \$MonIP<=highLimitIP and \$MonIP>=lowLimitIP;

Malheureusement les opérateurs <= et >= ne fonctionnent pas nativement sur les bases de données entre adresse IPs classiques. On va donc devoir les convertir en adresses IP numériques, c'est-à-dire en simples nombres entiers. Ainsi l'adresse 192.168.1.1 deviendra 3 136 235 777 = 192*2^24 + 168*2^16 + 1*2^8 + 1*2^0.

La source des données

C'est un simple fichier CSV téléchargeable depuis le site principal et régulièrement mis à jour. Voici un extrait pour examiner le format d'une ligne type :

...
"202385408","202385919","PR","PRI","PUERTO RICO"
"202385920","202706431","US","USA","UNITED STATES"
"202706432","202706943","PR","PRI","PUERTO RICO"
"202706944","203197063","US","USA","UNITED STATES"
...

Les deux premiers champs définissent un intervalle d'adresses IP au format numérique (par opposition au format séparé par des points) tel qu'une IP comprise dans cet intervalle est réputée représenter une machine installée dans le pays indiqué par les champs qui suivent. Les trois champs en question sont : le code ISO 3166-1 alpha 2 à deux lettres du pays, son code ISO 3166-1 alpha 3 à trois lettres et son nom complet.

Avant d'insérer les données dans le moteur de base de données, il faut nettoyer le fichier d'entrée pour que MySQL puisse le traiter sans complications :

cat ip-to-country.csv | sed 's/\"//g;s/\r//g' > ip2Country.csv
On élimine les guillemets et \\r

Ensuite, à partir d'un prompt MySQL et avec le fichier csv nettoyé et dans le path, on peut créer la table qui va héberger nos données :

create table ip2Country
    (
        lowIP int unsigned,
        highIP int unsigned,
        code2 varchar(2),
        code3 varchar(3),
        name varchar(60),
        INDEX(lowIP)
    ) ENGINE=INNODB;
Attention : un int ne suffit pas pour les IPs numériques, il faut des int non-signés

On peut terminer cette phase d'installation en important les données du fichier transformé dans la table MySQL que l'on vient de créer avec la commande suivante :

load data local infile './ip2Country.csv' into table ip2Country
    fields terminated by ","
    lines terminated by "\n"
    (lowIP, highIP, code2, code3, name);

Le résultat

Il reste donc l'essentiel et le plus simple à faire : interroger la base de données avec une IP quelconque pour en déduire le pays dans lequel la machine correspondante est installée.

Ainsi, si on utilise PHP on peut donc avoir la fonction suivante et triviale qui renvoie le pays correspondant à une adresse IP passée en paramètre :

function    IPToCountry($IP)
{
    $NumIP = ip2long($IP);      //PHP possède une fonction de conversion pour les adresses IP
    $Result = mysql_query("select * from ip2Country where lowIP<=$NumIP and highIP>=$NumIP;");
    $Result = mysql_fetch_array($Result);
    return $Result[0];
}

Tant qu'on y est, puisque j'aime le Bash, voici un oneliner qui fait la même chose depuis la ligne de commande :

mysql --silent --execute
     "SELECT name FROM ip2Country WHERE lowIP<=inet_aton('$IP') AND highIP>=inet_aton('$IP')"

L'intérêt de cette solution réside donc à la fois dans la simplicité de sa mise en oeuvre et dans son ouverture totale. On a vu qu'en quelques minutes on dispose d'une solution fonctionnelle, duplicable, d'un niveau demandant de faibles compétences techniques et à moindre coût.

Yep, I'm a geek !


14 juillet 2007

Extraction automatique de .torrents

Deux programmes (PHP et Bash) pour parcourir tout ThePirateBay et choper tous ses torrents sans s'embèter. Le principe étant que le script Shell/Bash commande un script PHP qui lui, se charge de tout le travail de reconnaissance de chaînes et d'extraction d'URLs. Ces deux scripts sont censés s'exécuter depuis la ligne de commande, un navigateur ne nous sert à rien ici.

#!/bin/bash

#"The Pirate Bay"-specific
BaseURL="http://thepiratebay.org"
ListPagePattern='/<a[ \n\r\t]*href="(.*tor\/[^">]*)[^>]*>(.*)<\/a>/'
TorrentPagePattern='/<a href="(.*\.torrent)">.*<\/a>/'
OtherPagePattern='/<a href="(\/brwsearch[^>"]*page=[0-9]+)"/'
FirstPage=brwsearch.php\?b\=1\&c\=501

./extract.php $BaseURL $FirstPage --get-pages "$OtherPagePattern" | sort | uniq > pages.list

pageIndex=0
for page in `cat pages.list`; do
    PageURL=page$pageIndex.html
    wget $BaseURL$page -O $PageURL      #Download de la page du site en question
    ./extract.php $BaseURL $PageURL --extract-torrents "$ListPagePattern" "$TorrentPagePattern" > page$pageIndex.list
    #
    for url in `cat page$pageIndex.list`; do
        grep $url torrents.list.done > /dev/null
        [[ $? == 0 ]] && echo "$url est déjà mis à télécharger" && continue;
        echo "On doit télécharger $url"
        dcop ktorrent KTorrent openTorrentSilently "$url";
        echo $url >> torrents.list.done
    done
    exit 12
    #
    ((pageIndex++))
done

Script shell qui appelle le PHP pour déterminer ce qui reste à télécharger
#!/usr/local/bin/php -q
<?
//Extrait d'une page toutes les sous-pages contenant un torrent et pour chaque sous-page, stocke l'URL du torrent dans un fichier local.
//
//Syntaxe :
//
//./extract.php <BaseURL> <FirstListPage> <ListPagePattern> <TorrentPagePattern> <OtherPagePattern>
//
//1 : BaseURL, l'URL de base du site visé, préfixe de toutes les adresses internes.
//2 : adresse d'une des pages contenant les liste d'éléments à extraire.
//3 : pattern repérant l'URL d'une page descriptive d'un torrent sur une page-liste.
//4 : pattern repérant l'URL d'un fichier torrent sur une page descriptive.
//5 : pattern repérant les URL des autres pages-listes à partir de celle passée en paramètre 2.
//
//Exemples d'utilisation :
//
//The Pirate Bay :
//./extract.php http://www.thepiratebay.org brwsearch.php\?b\=1\&c\=501 '/<a[ \n\r\t]*href="(.*tor\/[^">]*)[^>]*>(.*)<\/a>/' '/<a href="(.*\.torrent)">.*<\/a>/' '/<a href="(\/brwsearch[^>"]*page=[0-9]+)"/'

//TODO : penser à l'option --debug pour afficher des choses...
//DONE : faire deux options, --get-pages et --extract-torrents pour différencier les deux types d'appels de ce script

function    displayArray(&$arr)
{
    $Output = "<ul>\n";
    foreach($arr as $key=>$val)
        $Output .= "<li>$key : ".(is_array($val) ? displayArray($val) : $val)."</li>\n";
    return $Output."</ul>\n";
}
    
    $Args =& $_SERVER["argv"];
    if (count($Args) == 1)      die("Rien...");
    $BaseURL = isset($Args[1]) ? $Args[1] : "";
    $SrcFile = isset($Args[2]) ? $Args[2] : "";
    if (!strlen($SrcFile))      die("Pas d'URL de fichier source à analyser.\n");
    if (!file_exists($SrcFile))     die("Pas de fichier source à analyser.\n");
    $Contents = file_get_contents($SrcFile);
    if ($Debug) echo "Taille du fichier : ".strlen($Contents)."\n";
    //
    $Action = isset($Args[3]) ? $Args[3] : "";
    if (!strlen($Action))       die("Aucune action passée en paramètre.\n");
    switch ($Action)        {
        case    "--get-pages":
            $PatternPages = isset($Args[4]) ? $Args[4] : "";
            break;
        case    "--extract-torrents":
            $Pattern = isset($Args[4]) ? $Args[4] : "";
            $Pattern2 = isset($Args[5]) ? $Args[5] : "";
            if (!strlen($Pattern) || !strlen($Pattern2))    die("Extraction de torrents : il manque des patterns...\n");
            break;
        default:    die("Action inconnue : $Action.\n");
    }
    //Sous-pages
    if (strlen($PatternPages))      {
        $SubPages = array();
        $NbSubPages = preg_match_all($PatternPages, $Contents, $SubPages);
        //echo "Nb de matches : $NbSubPages\n";
        foreach($SubPages[1] as $PageURL)       echo $PageURL."\n";
        //echo displayArray($SubPages);
        die();
    }
    //Extraction de torrents
    $Matches = array();
    if ($Debug)     echo "Pattern = $Pattern\n";
    $NbMatches = preg_match_all($Pattern, $Contents, $Matches);
    if ($Debug)     echo "NbMatches = $NbMatches\n";
    //echo displayArray($Matches);
    $SubMatches = array();
    for($i=0; $i<$NbMatches; $i++)      {
//      echo $Matches[1][$i]."\n";
        if ($Debug) echo $Matches[2][$i]."\n";
        $DownloadPage = file_get_contents($BaseURL.$Matches[1][$i]);
        if (!$DownloadPage)     echo "Problème !\n";
        //Tentative de détection de pages erronées...
    if (strlen($DownloadPage) < 100)    {
        continue;
        echo "$DownloadPage\n";
    }
//      echo "Taille de la page téléchargée : ".strlen($DownloadPage)." octets\n";
        $Ret = preg_match($Pattern2, $DownloadPage, $SubMatches);
        $TorrentURL = $SubMatches[1];
        if ($Debug) echo "Torrent : ";
        echo (strlen($TorrentURL) ? $TorrentURL : "FALSE")."\n";
//      echo displayArray($SubMatches);
    }

?>
Moteur d'analyse de page qui extrait la hiérarchie liste-page-torrent

Aspirateur de site utilisant Fusker

Au départ était Fusker, qui agrégeait des sites épars et permettait leur consultation depuis un lieu unique. A partir d'un site de ce type on peut très facilement, en couplant Bash et PHP, rapatrier ces images localement. Voici :

#!/bin/bash

BaseURL="http://kladblog.funwithbabes.com/"
IndexURL=$BaseURL"index.php?offset=0"
for page in `wget -q -O- $IndexURL | grep "special=preview" | awk 'BEGIN{FS="<a href=\"[^\"]*\">.*</a>"} {URL=substr($0, index($0, $1)+length($1)+9); print substr(URL, 1, index(URL, "\"")-1)}'`; do
    page=$BaseURL$page
    pixList=$(wget -q -O- $page | php -r '$Contents=file_get_contents("php://stdin"); preg_match_all("@You are looking at <b>(http://[^<]*)</b>@", $Contents, $Matches); $Nb=count($Matches[1]); if ($Nb != 1) die("Oups"); $ToFusk=$Matches[1][0]; if (!preg_match("@(http://[^\[]*)\[[^\]]*\](.*)@", $ToFusk, $Matches)) die("Oups2\n"); $FP=$Matches[1]; $SP=$Matches[2]; $NbPix=preg_match_all("@(".$FP."[^<:]*).*<img src=\"\\1\"@", $Contents, $Matches); if (!$NbPix) die("Oups3"); $DirName=str_replace("/","",str_replace("http://","",$FP)); mkdir($DirName); echo $DirName."\n";  foreach($Matches[1] as $Item) echo $Item."\n";' 2>/dev/null)
    DirName=""
    for pix in $pixList; do
        if [[ ${#DirName} -eq 0 ]]; then
            DirName=$pix
            echo "Dossier : $DirName"
        else
            echo "Image : "$pix
            wget -P $DirName -nd -q $pix
        fi
     done
done

En changeant la déclaration de la variable IndexURL on peut rapatrier toutes les pages restantes. Ceci peut se faire automatiquement, mais je me suis arrêté là :).

C'est sûr que ça n'est pas ni du grand code ni du code propre mais ça fait le boulot. Il ne faut pas avoir envie de revenir dessus au bout de 6 mois c'est tout...

AJAX dans Konqueror / Safari


22 mai 2007

Du XML dans Konqueror

Pour charger un document XML dans Konqueror et le manipuler avec le DOM, il faut au préalable créer le document et charger le texte XML. Comme suit dans cet exemple JS :

    var Doc = "<"."?xml version='1.0' encoding='utf-8'?".">\
    <root2>\
        <child1>Contenu1</child1>\
        <child2>Contenu2\
            <child21>Contenu du 21</child21>\
        Fin du contenu 2\
        </child2>\
        <child3>Contenu3</child3>\
        <child4>Contenu4</child4>\
    </root2>"
    //
    var XMLDoc = document.implementation.createDocument();
    XMLDoc.loadXML(Doc);
    var Root = XMLDoc.documentElement;</code>

            <p>A partir de là on a un objet JS (Root) qui représente la version DOM de notre document XML. Si vous ne me croyez pas, essayez d'utiliser la fonction suivante qui parse le DOM en question :</p>
            <code legend='A appeler comme suit : getNodeHierarchy(Root, 0)'>function    getNodeHierarchy(node, level)
{
    var Output = typeof node+"-"+level+" : "+node.nodeName+", "+NodeTypesDisplay[node.nodeType]+", "+node.nodeValue+"\n";
    if (!node.childNodes.length)        return Output
    node = node.firstChild
    do { Output += getNodeHierarchy(node, level+1) } while (node = node.nextSibling);
    return Output
}

La fonction précédente avec notre XML d'exemple affichera :

object-0 : root, Node, null
object-1 : #text, Texte,

object-1 : child1, Node, null
object-2 : #text, Texte, On
object-1 : #text, Texte,

object-1 : child2, Node, null
object-2 : #text, Texte, Contenu2

object-2 : child21, Node, null
object-3 : #text, Texte, Contenu du 21
object-2 : #text, Texte,
Fin du contenu 2

object-1 : #text, Texte,

object-1 : child3, Node, null
object-2 : #text, Texte, Con
object-2 : b, Node, null
object-3 : #text, Texte, tenu3
object-1 : #text, Texte,

object-1 : child4, Node, null
object-2 : #text, Texte, Contenu4
object-1 : #text, Texte,

Jusque là tout va bien, mais comment nourrir un script avec un XML dynamique, i.e. que l'on ne peut pas hardcoder et que l'on peut même recharger plusieurs fois au cours du déroulement de l'application ? C'est très simple : on intègre une iframe dans la page web, on règle l'attribut src de cette iframe à une URL correspondant au fichier et en utilisant l'évènement onLoad de l'iframe on peut recopier peu ou prou les trois lignes qui crée le document XML et qui charge les données. Seul problème, si on essaye, Konqueror va transformer le XML en document HTML pour le rendre (c'est une IFrame après tout) alors plutôt que d'essayer tout de suite de faire des XSL pour pallier à ça, on construit une petite passerelle PHP qui va servir un fichier en transformant les < en &lt; et les > en &gt;. J'ai presque honte de faire ça mais ça fonctionne très bien, vous allez voir. Voici déjà la passerelle PHP qui sert les fichiers XML transformés :

<?
    if (!isset($_GET["file"]))      die("Pas de paramètre qui indique un fichier à servir");
    $FilePath = $_GET["file"];
    while (true)        {
        if (strpos("/", \$FilePath) !== false)      die("Interdit");
        if (file_exists($FilePath))     break;
        $Temp = rawurldecode($FilePath);
        if ($Temp == $FilePath)     die("Fichier introuvable");
    }
    $Contents = file_get_contents($FilePath);
    echo str_replace("<", "&lt;", str_replace(">", "&gt;", $Contents));
?"."></code>
            <p>Ainsi, en utilisant cette passerelle et en interceptant l'évènement onLoad de l'iframe avec la fonction JS suivante on obtient le même résultat que précédemment mais sans avoir hardcodé le XML :</p>
            <code>function ReceiveDatas()
{
    var Input = document.getElementById("inputXML")
    if (!Input.src.length)      return
    var XMLContent = Input.contentDocument.body.innerHTML
    XMLContent = XMLContent.replace(/&amp;lt;/g, "&lt;").replace(/&amp;gt;/g, "&gt;")
    //
    var XMLDoc = document.implementation.createDocument();
    XMLDoc.loadXML(XMLContent)
    var Root = XMLDoc.documentElement
    alert(getNodeHierarchy(Root, 0))
}?>

Et ça y est, Konqueror peut charger et manipuler du XML comme un grand. Maintenant qu'on a trouvé une méthode pour charger un XML "à la main", pour les navigateurs équipés passons à...

L'utilisation des xmlHttpRequest

Les expressions régulières


7 avril 2007

Expressions régulières

Une compilation de conseils et d'exemples sur les expressions régulières. Histoire de ne pas avoir de multiples sources de renseignements pour des choses simples et qui reviennent souvent. �videmment, ces regex d'exemples et ces conseils sont initialement tirés de ce site pour montrer qu'ils sont utilisables directement.

Regarder si l'expension des tabs pourrait se faire avec une simple regex.
global  $TabWidth, $Tabs, $TabLengths;
    $Tabs = array();    $TabLengths = array();
    for($j=0; $j<=$TabWidth; $j++)      $TabLengths[$j] = strlen($Tabs[$j] = $j ? ($Tabs[$j-1])."&nbsp;" : "");
    $Ln = strlen($snip);
    $Computed = 0;
    foreach(array(true, false) as $ComputeWidth)        {
        $PosInLine = 0;
        $i = 0;
        while ($i<$Ln)      {
            $c = $snip[$i++];
            if ($c == "\n")         $PosInLine = -1;
            if ($c != "\t")     {   $PosInLine++;   continue;   }
            //On étend les tabs
            $RealWidth = $TabWidth - $PosInLine%$TabWidth;
            $Offset = $TabLengths[$RealWidth] - 1;
            if (!$ComputeWidth)     {
                $snip = substr($snip, 0, $i-1).$Tabs[$RealWidth].substr($snip, $i);
                $Ln += $Offset;         $i += $Offset;
            }   else    $Computed += $Offset;
            $PosInLine += $RealWidth;
            if ($ComputeWidth)      $Computed++;
        }
    }

Boucle qui étend les tabs d'une chaîne, $snip, en 2 passes : calcul de la taille finale et transformation.

Une expression régulière tirée d'un commentaire de la doc PHP de preg_grep.

/((?:(?!BADWORD).)*)/s
Regexp pour éliminer BADWORD de l'entrée
Accueil1 2 3 4 5 6 7 8