Bonjour,
 
après avoir parcouru plusieurs forums et des docs, et n'ayant pas trouvé de réponse je viens poser ma question ici en espérant que quelqu'un entre vous arrivera à me renseigner.
 
Je voudrai savoir comment sont stockés les champs de type tableau dans les SGBD (PostgreSQL ou autres) et est-ce que la recherche sur ces champs est efficaces ?
 
La table qui comporte parmi tous ses champs le champs de type tableau d'entier, possèdera plusieurs centaines de milliers d'occurrences, chaque occurrence du champs tableau pouvant aller jusqu'à plusieurs centaines d'entrées.
Pensez-vous envisageable d'effectuer une série de requête sur cette table par rapport à une entrée du tableau (par exemple je veux toutes les occurrences de la table qui comportent le nombre xx dans le champs tableau) ?
(je précise que je ne connais pas à l'avance la taille des tableaux, ils seront donc dynamique : champs de type int[]).
 
 
J'espère que vous pourrez me renseigner

La performance des bases de données repose sur les index, et ceux-ci sont généralement des arbres équilibrés (B-Tree) ou des variantes de ces arbres. Donc, c'est rapide si on n'a pas oublié de choisir la clé primaire ou de créer un index de manière explicite. Et pour cela, il faut savoir à l'avance quel type de selection/insertion on sera amené à faire. Pour aider à cette conception, il est recommandé de connaître les "formes de normalisation" édictées initialement par E. Codd. Si vous ne les avez jamais vus, car elles sont peu enseignées hélas, essayez tout de même d'y jeter un oeil, cela vous éclairera. Or dans la théorie de Codd, il n'existe pas de champ de type tableau, sauf si on appelle par ce nom une chaîne de caractères, comme cela arrive en langage C. Alors, on peut considérer qu'un tableau d'entiers serait comme une chaîne de caractères Unicode, ayant 2 octets pour chaque représentation de caractère. Je crois que c'est dans ce but principal qu'a été créé le type tableau. Dans cette optique, la recherche que vous souhaitez entreprendre s'apparente à trouve une sous-chaîne dans une chaîne de "caractères" (Unicode ou autres). Et la recherche d'une sous-chaîne n'est pas une opération rapide, car les index n'ont pas été créés pour cela, sauf, éventuellement, dans le cas où la sous-chaîne se trouve au début de la chaîne. Mon avis personnel à deux centimes de vieil informaticien, est qu'il vaut mieux éviter les solutions exotiques, et rester dans les solutions classiques qui marchent, quand on utilise une base de données standard, ou bien on créé sa propre structure particulière sans passer par les bases de données standards et on fait une création artistique pour la satisfaction de son goût pour l'originalité. Si vous réfléchissez, je suis à peu près certain que vous pouvez utilisez les champs de type classique au lieu d'un champ de type tableau. Cela nécessitera peut-être de créer une autre table, mas il ne faut pas avoir peur de créer beaucoup de tables et de faire des jointures dans ses Select.

Ouahou merci pour cette réponse précise !
 
Je me doutai bien du fait qu'il valait mieux éviter ce genre de types de champs.
 
En faite il s'agira d'un base d'indexation, composée d'une table "Document", d'une table "Terme", chaque document en relation avec un terme via une table "Relation".
 
La table "Relation" comportera trois champs :  
--> id_terme
--> id_document
--> positions (le fameux champs de type tableau à éliminer)
 
Le champs position permet donc de connaitre la position (i-ième mot dans le document). La taille du champs position sera égale au nombre d'apparition du terme dans le document.
A partir d'un document et de ses relations, il est donc possible de recomposer le corps de texte grâces aux positions.
 
Ne connaissant pas à l'avance la taille du champs positions, je ne vois pas comment le remplacer par l'ajout d'une table ou d'autres champs de type standards...
 
La seule solution (non envisageable) à mes yeux, serait de créer une nouvelle table pour chaque relation... Sachant que la table relation comportera plusieurs millions d’occurrences : pas possible...

Pourquoi c'est pas possible J'ai bien développé un algorithme sémantique basé sur LSA et je me retrouve avec des tables où chacune contient plusieurs millions d'enregistrements. C'est vraiment pas un pb. En plus, la plupart des bons SGBD implémentent la notion de partition, utile dans le cas de très grosses tables...
 
+1 pour le coup d'éviter le stockage dans un champ de type tableau. Mysql n'a pas ça par ex, alors que Firebird, oui.

Il y a aussi les FullText index qui font ce genre de trucs la, pas besoin de réinventer l'eau chaude.
 
Sinon un champ de type tableau n'est jamais une bonne idée et peu toujours etre remplacé par une autre table.
 
Dans ton cas:
Table Relation:
--> id_terme
--> id_document
--> id_position
 
Table Position
--> id_position
--> Position
 
Et puis tu fais un join des 2 tables pour avoir tes resultats, ca peu etre correctement indexé et tout le tralala.
 
Ca fais bien longtemps qu'on utilise des DB et la techno est bien mature, si on en viens a utiliser un truc exotic c'est que le probleme se situe au niveau de l'architecte et pas niveau DB.

 
Moi j'aurai plutôt fait ça :
 
Table relation :
--> Document
--> Terme
--> Poids (je ne vous l'avieza pas donnée celle la, c'est le poids du mot pour le document, global à toutes les occurrences)
 
Table positions :
--> Document
--> Terme
--> Position
 
Du coup la taille de la table position sera égal à la somme du nombre de mot de toutes les pages indéxées. Hum ça me semble vraiment trop lourds non ? Je me suis trompé dans mon post précédent, cette table de positions fera certainement plusieurs milliards de lignes !
 
Sachant que la base sera hebergée sur un serveur de type dual core 2*2Ghz avec 2Go de ram.. Ca risque de demander plusieurs minutes pour reconstituer une portion d'un document.. Je pense qu'on va abandonner cette fonctionnalité, a moins que vous ayez des arguments qui arrivent à me convaincre ^^
 
En tout cas merci pour vos réponse

T'as une idée plus precise de la volumetrie?
Combien de docs, combien de mots par documents?
 
Si tu normalises un peu plus tes table il y a moyen de gagner pas mal de place:
 
Table Termes:
--> Terme_id
--> Terme
 
Table relation:
--> Document_id
--> Terme_id
--> Poids
--> Position_id
 
Table positions:
--> Position_id
--> Position
 
La table Termes va augmenter vite au debut, puis apres quelques documents tu auras deja quasi tout les differents mots possible.
Les 2 autres tables ont des champs de type int (4 bytes) voir meme smallint (2 bytes +- 64000 valeures).
 
J'utiliserai Position_id car la table positions sera toujours plus grande que la table relation (donc ca prendra moins de place que d'utiliser Document_id et Terme_id).
 
Point de vue taille, la table Termes ne sera pas tres grande, si on compte +- 14 bytes par enregistrement, ca t'en fais +- 70.000 par mega.
 
La table relation va prendre +- 16 bytes par mots unique dans un document et la table Positions +- 8 bytes par occurence.
 
Donc meme si tu as des milliards d'enregistrements, ca tiens dans moins de 10Go et c'est donc bon pour ton server.
 
Il faut tester evidement, c'est pas toujours faci lde savoir combien d'espace supplemantaire est utilisé par un SGBD pour la structure interne.

Pour la volumetrie, en faite ça dépendra de la configuration du robot d'exploration. Il faudrait que le système reste efficace (temps de recherche < 2sec) avec quelques millions de documents.
 
Chaque document comportera plusieurs milliers de termes, donc la table positions devrait faire plusieurs 10aines de milliards de lignes..

Avec autant de données, partir sur un SGBD n'est pas forcément la meilleure des solutions
Certains SGBD comme Oracle permettent de faire des tables partitionnées, mais si tu as juste un simple besoin de stocker beaucoup de lignes et de les retrouver rapidement, tu peux tenter des BDD non relationnelles, comme Cassandra (http://cassandra.apache.org/)
C'est notamment la base utilisée par Facebook (qui développe le projet) et twitter

Oui pour ca je suis du meme avis que couak sur ce coup la.
 
Mais si vous n'avez pas trop envie d'explorer le nosql, une indexation correcte des tables te permettra d'avoir des resultats tres rapide.
 
La volumetrie c'est important, tu devrais faire plusieurs scenario et calculer +- combien de references ca donne.
Ca te permet de voir si ton server va tenir le coup ou si il va te faloir quelque chose de plus gros.
 
Faut pas avoir peur des DB de plusieurs gigas, c'est dans la norme des DB comme ca de nos jours

Pour info, pour mon algo LSA, la table qui contient le tf-idf des termes/documents fait 15 millions de lignes pour 250 Mo. Ca, c'est pour environ 3050 termes et 5000 documents. En comptant les autres tables (temporaires) utiles pour l'algo, la base monte à 1.2 Go, 57 millions d'enregistrements.

oué c'est encore loin des 10aines de milliards...
 
Pour les systèmes noSQL ça me parait un peut complexe (étant donné le temps qu'on a pour la réalisation et le peu de documentation disponible) mais c'est super intéressant !

 
Juste pour savoir : où va tu aller chercher les millions de documents à indexer? Parce qu'à part sur le web, je doute qu'une entreprise possède autant de documents Et là, pour le coup, tu veux nous réinventer Google
 
Et pour les "plusieurs milliers de termes" par document, tu va vite te rendre compte qu'on utile finalement peu de vocabulaire quand tu enlèves les mots qui ont peu d'intérêt d'être indexés (et, ou, avec, sur, dans...). Ensuite, tu peux transformer en lemmes tes termes. Avec ça, tu va voir que finalement, tu va tourner autour de 3000-4000 termes pour toute ta base documentaire...

Il s'agit effectivement d'indexer des pages web (projet universitaire).

 
Si ce n'est qu'un projet, la question de la volumétrie est un faux problème, faut juste que tu démontres le concept par une application qui va indexer un nb de sites web limité. Google a commencé avec qq petits PC (Facebook aussi), aujourd'hui, le nb de serveurs utilisés par Google est quasi secret, leur emplacement aussi (plus ou moins).
 
Donc te prends pas la tête avec la volumétrie. Si on te pose la question, tu réponds qu'il suffira d'augmenter le nb de machines

L'idée c'est quand même de développer un outil efficace et peu coûteux en ressources...

 
Indexer le web sera forcément coûteux en ressource   Soit en stockage, soit en perfs d'exploitation (temps de réponse, tu peux compresser les données mais après, pour l'exploitation, ça prendra plus de temps)... Pourquoi crois-tu que Google a autant de serveurs dans le monde? Pour le plaisir de collectionner les machines    
 
Après, y'a peut-être à chercher du côté des GPU pour booster les perfs, mais là, faudra inventer ta propre architecture pour les données, les outils ainsi que les algos qui vont avec. Je doute que ça soit dans tes cordes (ou de celles de la plupart des gens)...

c'est pour cela qu'en général on paye très cher des BDD car l'infrastructure est évolutive jusqu'à un certain point, et l'intelligence et performances sont basées sur des choses éprouvées
 
c'est pour cela qu'une telle quantité de données, une base comme Cassandra est intéressante car la données est redondé, et l'ajout de machines augmente les capacités globales

L'indexation sera bien évidemment limité à un modif de domaines

En tout cas merci pour toutes vos réponse, la j'ai créé un petit script qui me génère un fichier sql pour tester postgres.
 
Il est en train de me créer un fichier qui contient 500mille termes, 2 millions de documents, et une moyenne de 2500 termes par document (soit 5 milliards positions).
 
Lorsque je générait le fichier je faisait une série d'INSERT INTO. Lorsque j'ai essayé d'executer le fichier dans postgres, il est tellement lent que j'ai fait un petit calcul : il m'aurait fallu 2 ans pour finir l'importation !
 
Je réessaye donc avec des INSERT multiples

C'est une infinité de fois plus rapide avec des INSERT multiples ! Même si ça mouline encore

essayes pgloader

si tu as de bon tuto je suis preneur

J'ai fais un petit essaie sur SQL Server, j'ai crée la table relations avec 1milliards d'enregistrements (j'ai pas toute la journée pour generer le reste ) et les query faites sur l'index (terme_id) sont instantanée.
 
Le tout maintenant est de savoir quel genre de query tu vas faire dessus, pcq avec autant d'enregistrement les indexes supplementaire vont avoir +- la taille de la table.
 
Si c'est pour trouver dans quel 10 premiers document un mot precis est trouvé, c'est tout facil et ca va super vite.
Si c'est pour trouver dans quel 10 premiers documents plusieurs mots precis sont trouvés ca deviens un peu plus compliqué mais ca tourne toujours vite (limité a 10 mots).
 
Pour des choses plus complexe il faudra serieusement penser a aller voir du coté nosql (cassandra & co.).
 
Pour la volumetrie que tu donnes, je doute tres serieusement que les documents aient en moyenne 2500 mots differents (je verrais plutot 300-400). C'est une difference qui reduit considerablement la taille de la table relations.

+1 je pense que notre ami ne s'y connait pas trop en traitement naturel des langues. Dans son cas, à mon avis, il n'y a aucun intérêt à indexer les "petits mots", le la les sur dans... Et je parie qu'il ne transforme pas en lemmes les termes des documents. D'où pourquoi il va se retrouver avec autant de termes indexés mais qui ne vont lui servir strictement à rien.
Je recommande donc de lire l'article sur le tf-idf, qui pourrait être utile pour accélérer la recherche et surtout la pertinence. http://fr.wikipedia.org/wiki/Tf-idf
Un mot qui apparaît souvent et dans tous les docs n'a aucun intérêt car pas pertinent pour filtrer les documents. Au contraire un, terme qui apparait souvent dans un seul doc le sera...

2500 mots c'est dans le pire des cas.
 
A mon avis ce qui prend énormément de temps dans l'insert des positions, c'est qu'il doit gérer l'unicité des couples terme, document et position, ainsi que les relations avec les tables documents et termes...
 
La même table sans relation devrait se remplir beaucoup plus vite.
 
Je teste avec la première méthode qui consistait à créer une table relation avec un champs positions de type tableau, ça a l'air d'être très rapide. Je teste maintenant et je vous tien au jus...

Bon en faite c'est quand même long.
 
Du coup pour accélerer j'ai viré les clé primaire et les clé étrangeres de la table relation et ça va plus vite (environ 3mn pour insérer 1 million de relation comportant environ chacun 20 positions --> soit 1 milliard de mot en tout). J'ajouterai les clés avec un ALTER TABLE une fois l'import terminé
 

Oui c'est normal : quand tu fais une insertion, le SGBD doit mettre à jour les indexes, ce qui ralentit l'écriture
C'est pour cela qu'il y a des méthodes et des outils pour insérer des données en masse
 
1) tu peux passer par le loader natif de ton SGBD, pour postgresql est pgloader
2) tu peux désactiver les indexes, et les recréer après insertion

Le problème c'est que lorsque j'ajoute les indexes avec alter table après l'import, un simple count (*) prend un temps fou, donc je doute de la veritable indexation des données.
 
Peut être qu'il faut executer une requête ?
 
Pour pgloader j'ai un peu compris le fonctionnement, seulement si quelq'un pouvait m'expliquer comment se connecter à postgres. J'ai un pb de connexion a la DB lorsque j'execute "pgloader -c pgloader.conf"...
 
Au début du pgloader.conf j'ai :
[pgsql]
host = localhost
port = 5432
base = pgloader
user = thibaut
pass = None
 
Je ne sais pas ce que je dois faire. L'utilisateur unix "thibaut" à accès a postgres.

(vous pensez réellement que ça ira beaucoup plus vite avec pgloader ?)

je ne connais pas suffisamment postgresql ni pgloader pour t'aider mais pour ton histoire de "select count(*)" c'est normal, c'est une requête qui parcours entirèrement la table
 
l'index sert lors d'une recherche, cela fonctionne comme pour ton encyclopédie universalis : il est préférable de parcourir l'index pour trouver tout de suite la page précise, plutôt que de parcourir les 12 tomes de ton encyclopédie à la recherche d'une information

En quoi enlever les clé primaires et étrangères avant l'import des données, et les remettre après accélère le temps d’insertion ?
 
Le temps gagné au moment de l'import n'est-il pas "perdu" lors de la remise en place des clés ?

Ben non. A chaque insert, le sgbd doit recalculer l'index. Si tu l'enlèves avant l'import et le remets après, le sgbd va calculer en 1 fois l'index. Ca va donc plus vite...

okay !

Au fait, t'as pas répondu si, pour améliorer la pertinence des réponses fournies par ton moteur de recherche, tu utilisais la lemnisation des termes et le tf-idf (ou un coefficient ayant la même fonction)?
 
Je dis ça parce que si c'est pour nous pondre un moteur qui fait que de la recherche par mots-clés, sans un minimum d'intelligence (coeff de pertinence, sémantique...), ça sert pas à grand chose Y'a déjà de tels moteurs en GPL (Lucène, par ex)...

bien évidemment le poids des mots sera défini par le tf-idf. L'indexation sera étendu aux lemmes, synonymes et idées associées.
Seule la polysémie et autres analyses sémantique ne seront pas développés
Tu t'y connais bien en moteur de recherche ? Tu pourras peut être m'être utile

 
Comme dit dans un précédent post, j'ai développé pour mon appli Astres (cf signature), une implémentation de l'algo LSA ( http://fr.wikipedia.org/wiki/Analy [...] ue_latente ) afin de calculer le taux de corrélation entre des tickets (help-desk), histoire de pousser au résolveur des tickets similaires afin de résoudre un incident plus vite, ou identifier un problème (au sens ITIL), même espacé sur plusieurs mois. Avant de choisir cet algo, j'ai lu plusieurs thèses d'universités en Angleterre et USA plus tout un tas de sites web traitant de l'ontologie, taxonomie et sémantique en général... Pour résoudre le pb de la lemnisation, j'ai utilisé la BD Lexique.org qui est vraiment bien et en GPL.