Partage

Bon challenge : recherche dans une liste d'entiers

Sujet résolu

Anonyme

29 août 2011 à 17:22:42

Bonjour à tous,

J'ai presque terminé la conception de ma table nommée page mais quelque chose ne va pas.

Voici les deux champs intéressants :

id : INT(10) entier non signé codé sur 4 octets
items (id des objects présents dans la page) : VARBINARY(200) chaîne d'octets de taille variable (max 200)

Ces deux champs sont indexés pour accélérer la recherche car je veux pouvoir rechercher une page d'après l'identifiant d'un objet qu'elle contient.

L'idée est de stocker une liste d'INT(10) dans le champs items.

J'ai codé une fonction ruby qui transforme un INT(10) en 4 caractères
Je peux donc en mettre 50 dans mon champs items (car 50*4=200)

Maintenant le soucis est comment rechercher par une requête SQL une chaîne de 4 octets dans une chaîne de maximum 200 octets ? La fonction LIKE de mysql permet de faire ça mais je ne veux pas qu'elle me trouve 4 octets qui appartiennent à 2 nombres différents... Vous me suivez ?

Si c'est impossible je serais obligé de stocker les nombres sous cette forme :
"0052CFA1;000005;FFFF56;..."

Un petit indice m'aiderait surement à trouver, merci d'avance!

Seba991

29 août 2011 à 18:02:07

en utilisant la fonction substring entre 1 et 4, entre 5 et 8, entre 9 et 12 ... entre n et n+3 ?

Je sais qu'elle fonctionne sur des varchar... j'ai jamais bossé avec des VARBINARY... mais ca doit être à peu près pareil non ?

( tu boucles sur n tant que ton substring ne te renvoie pas une chaine nulle ou un caractère de fin de chaine... je ne sais pas comment fonctionne les VARBINARY)

Fayden

29 août 2011 à 19:39:47

Oui mais non, on ne conçoit pas une table comme ça. Tu fais une ligne par item, et tu ajoutes une colonne pour indiquer à quelle ligne de quelle table (FOREIGN KEY) cet item appartient.

Anonyme

29 août 2011 à 21:31:13

@Fayden c'est plus compliqué que ça, chaque page contient entre 0 et 50 objets et chaque objet est représenté dans la table objet.
@Seba991 c'est exactement ce que je voulais faire, mais je savais pas qu'on pouvait faire des boucles dans une requête. Merci en tout cas. Mon champs item ressemble plutôt à ça maintenant :

SXXXXXXXX;SXXXXXXXX;... (50 max) où S est un caractère représentant le statut de l'objet dans la page (visible? invisible? etc.) et X est un chiffre entre 0 et F.
Ainsi :
LIKE %00000001;% me trouve les pages contenant l'objet 1
LIKE %V________;% me trouve les pages contenant un objet visible (V)
LIKE %V000000FF;% me trouve les pages contenant l'objet 256 et où cet objet est visible

Seba991

29 août 2011 à 21:37:40

Citation : Arsenic33

@Fayden c'est plus compliqué que ça, chaque page contient entre 0 et 50 objets et chaque objet est représenté dans la table objet.
@Seba991 c'est exactement ce que je voulais faire, mais je savais pas qu'on pouvait faire des boucles dans une requête. Merci en tout cas. Mon champs item ressemble plutôt à ça maintenant :

SXXXXXXXX;SXXXXXXXX;... (50 max) où S est un caractère représentant le statut de l'objet dans la page (visible? invisible? etc.) et X est un chiffre entre 0 et F.
Ainsi :
LIKE %00000001;% me trouve les pages contenant l'objet 1
LIKE %V________;% me trouve les pages contenant un objet visible (V)
LIKE %V000000FF;% me trouve les pages contenant l'objet 256 et où cet objet est visible

Je suis ravi d'avoir pu t'aider...

Il n'empêche, je suis totalement d'accord avec Arsenic33, la conception de ton modèle de données n'est pas bonne... Tu devrais suivre sa suggestion

tu fais une table "page" contenant un identifiant de page [ ton int(10) si j'ai bien suivi ]
tu fais une table "objet" contenant un champ "statut" char(01) et un champ identifiant objet (codé en hexadécimal si ca te chante... Mais ca serait vachement plus pratique de garder ton int(10) et de ne pas se servir de ta fonction Ruby ;-) )...
tu fais une table "liaison page_objet" contenant l'identifiant de ta page et les identifiants de chacun des objets présents sur ta page
(un record par objet présent sur une page)

ensuite, pour savoir quelles pages contiennent l'objet
dont l'id est LIKE %00000001%

ta requête sera :

SELECT Pag.int 
FROM   ma_base_de_donnee.ma_table_page Pag
INNER JOIN ma_base_de_donnee.ma_table_liaison Lia ON Lia.identifiant_page = Pag.identifiant
INNER JOIN ma_base_de_donnee.ma_table_objet Obj ON Obj.identifiant = Lia.identifiant_objet
WHERE Obj.identifiant_objet LIKE %00000001%

Bien à toi,

Seba991

Fayden

29 août 2011 à 21:54:55

Citation : Arsenic33

@Fayden c'est plus compliqué que ça, chaque page contient entre 0 et 50 objets et chaque objet est représenté dans la table objet.

Exactement. Donc, tu dois faire une table pour associer tes pages à tes objets.

Lord Casque Noir

30 août 2011 à 9:39:22

> dont l'id est LIKE %00000001%

disons plutôt "dont l'id est 1" non ?

sinon, les listes dans des colonnes, t'as 2 options :

1- tu le fais pas (donc t'utilises une table de lien comme d'habitude)
2- tu utilises une vraie base de données (ex: postgresql) et tu as déjà une table de lien comme d'habitude, mais tu as une bonne raison de dénormaliser (genre tu veux accélérer les recherches croisées) et tu mets donc une colonne INTEGER[] qui contient la liste d'ids (mise à jour par un trigger sur la table de lien), un index gist dessus, et les recherches du type "colonne_ids contient {1,2,3}" sont hyper rapides.

sous mysql tu peux émuler le 2 en utilisant une colonne TEXT avec tes ids dedans, et en mettant un index FULLTEXT dessus... mais ça t'oblige à utiliser myisam, donc c'est sale.

Anonyme

31 août 2011 à 15:54:31

Merci à tous pour vos réponses toutes utiles

Je n'oublierais pas vos conseils pour plus tard; je compte en apprendre plus sur les systèmes de BDD...

Pour info, voilà le bilan qui est toujours ma version de la table. Je sais que c'est pas forcément ce qui tournera le plus vite mais je reverrais ça quand j'aurais appris à me servir des fonctions de liaison et éventuellement de PostgreSQL.

Je précise qu'un objet peut être présent dans plusieurs pages sous différents status, d'où le stockage du statut dans le champs items.

Exemple de page stockée dans la table :

INT(10) id = 7 (entre 1 et plus de 2^32)
INT(10) owner = 4
VARCHAR(90) readers = "*" (max 10 id)
VARCHAR(90) editors = "00000004;0000000C;" (max 10 id)
VARCHAR(500) items = "V0000009B;H0000009C;V0000009D;" (max 50 pairs status+id)

Forme de l'objet après chargement :

<Page:
 @id = 7,
 @owner = 4,
 @readers = :everybody,
 @editors = [4, 12],
 @items = {
  <Item: @id = 155, ...> => :visible,
  <Image: @id = 156, ...> => :hidden,
  <Link: @id = 157, ...> => :visible
 }
>

Partie chargement/sauvegarde dans la classe Page

class Page
 attr_reader :id
 attr_accessor :owner, :readers, :editors, :items
 
 Status = {
  'H' => :hidden,
  'V' => :visible,
  :hidden => 'H',
  :visible => 'V'
 }
 
 def initialize id, owner, readers, editors, items
  @id = id.to_i
  @owner = owner.to_i
  @readers = readers == '*' ? :everybody : readers.split(';').map! &:hex
  @editors = editors == '*' ? :everybody : editors.split(';').map! &:hex
  @items = {}; items.split(';').each{|s| @items[Item.select s[1..-1].hex] = Status[s[0]]}
 end
 
 def update
  mysql_query "UPDATE page SET \
owner=#{@owner}, \
readers=#{@readers.map{|r| r.to_s 16}.join ';'}, \
editors=#{@editors.map{|e| e.to_s 16}.join ';'}, \
items=#{@items.collect{|id, status| Status[status] << id.to_s(16)}.join ';'} \
WHERE id=#{@id}"
 end
end

class << Page
 def select by = 'id', limit = 0..10, *arg
  by.is_a? Integer and return load(nil, nil, by)[0]
  ok = case by
  when 'id'
   "id=#{arg[0]}"
  when 'owner'
   "owner=#{arg[0]}"
  when 'readers', 'editors', 'items' # Status[nil].to_s == ''
   "#{by} LIKE '%#{Status[arg[1]]}#{arg[0].to_s(16).rjust 8, '0'};%'"
  when 'item_status'
   "items LIKE '%#{arg[0]}________;%'"
  else return nil end
  pages = []
  res = mysql_query "SELECT * FROM page WHERE #{ok} LIMIT #{limit.min},#{limit.max}"
  res.each_row{|row| pages << Page.new(*row) }
  res.free
  pages.any? and pages
 end
end

Lord Casque Noir

31 août 2011 à 22:04:59

pourquoi tu ne le fais pas correctement avec une table de lien ?
là, c'est moche, lent, pas indexable, tout pour plaire !

Seba991

31 août 2011 à 22:15:09

Je suis d'accord avec le Lord...

Si tu ne suis pas nos conseils, ca ne sert à rien de venir en demander...

Anonyme

4 septembre 2011 à 3:05:59

@Lord Casque Noir C'est indexé. Les index sur des VARCHAR(20) sont très courants pour les pseudonymes. Dans ce cas il s'agit d'un VARCHAR(500) qui évite de passer par 50 liens à la place. Je vais tester ma version demain avec 1 millions de pages contenant entre 0 et 50 item. Je testerais ensuite la même chose avec une table de liaison, qui contiendra donc bien plus qu'un million d'entrées. Si je peux utiliser votre solution sans augmenter le nombre de requêtes ou leur durée d'exécution, pour la récupération comme pour la mise à jour et l'insertion, alors j'avouerais que ma version est "moche". Dans le cas contraire, elle serait plutôt astucieuse.

@Seba991 Le fait de ne pas suivre un conseil n'implique pas qu'il est inutile et encore moins que ça ne servait à rien de venir en demander. Rien ne m'empêche de changer la gestion des données dans une version supérieure de mon site. C'est pas la première fois que j'utiliserais la fonction 'rechercher dans les fichiers' de notepad++.

J'avoue que ça c'est moche :
VARCHAR(90) editors = "00000004;0000000C;" (max 10 id)
Mais ça ?
VARCHAR(91) editors = ";4;C;" (toujours 10 max pour éviter les problèmes)
C'est déjà plus courant, les fonctions explore/implode de PHP sont là pour ça.
On peut imaginer utiliser LIKE '%;nombre;%' pour les recherches.
Peut-être que je surestime cette fonction, on le saura bientôt...

Fayden

4 septembre 2011 à 3:11:18

Je trouve un peu irritant que tu viennes demander de l'aide ici mais rejettes toutes les réponses qui te sont apportées. Pourquoi poster ta question dans ce cas ?

Anonyme

4 septembre 2011 à 14:44:14

Ma question de base était "Maintenant le soucis est comment rechercher par une requête SQL une chaîne de 4 octets dans une chaîne de maximum 200 octets ? La fonction LIKE de mysql permet de faire ça mais je ne veux pas qu'elle me trouve 4 octets qui appartiennent à 2 nombres différents... Vous me suivez ?"

Vos réponses ont dépassé ma question (merci encore) mais ne m'en veut pas si je n'applique vos conseils à la minute.

Résultats du test pour 10 000 pages contenant un nombre aléatoire d'objets (entre 0 et 50)

Version actuelle de mon site :
5min pour insérer les 10 000 pages
SELECT id FROM page WHERE items LIKE '%03559509;%'
=> 12ms

Version avec une table de liens :
3h pour insérer les 10 000 pages plus 360 000 liens
SELECT p.id FROM page p JOIN page_item pi ON p.id=pi.page_id WHERE pi.item_id=365055
=> 42ms

Il y a un index de type INDEX sur pi.page_id et pi.item_id, et un index de type PRIMARY sur p.id et pi.id

Donc d'accord avec une table de liens c'est plus propre et plus pratique, mais ça à un prix.
Je vais donc explorer la piste de Lord avec postgresql car un INTEGER[] sera toujours mieux qu'un VARCHAR(500). Je vais probablement garder la table de liens aussi car même si ça complique la gestion des insertions et des suppressions, elle pourrait s'avérer utile pour des recherches différentes...

Lord Casque Noir

4 septembre 2011 à 22:12:24

Citation : Arsenic33

@Lord Casque Noir C'est indexé.

Pour info, un index de type btree est utilisable uniquement pour des recherches de type égalité (x=a) ou intervalle (x>=a, x<=a, a<=x<=b, etc). La recherche (x LIKE 'truc%') est une recherche d'intervalle ('truc' <= x < 'trud'). Sinon, ce type d'index peut être parcouru pour examiner toutes les valeurs si c'est trop fatigant d'aller les chercher dans la table, mais ce c'est plus vraiment utilisé comme un index.

Un index de type btree n'optimise bien évidemment pas (x LIKE '%truc%') car il n'y a pas de préfixe (ça commence par un %) donc la recherche n'est pas un intervalle. Donc tout le contenu de la table est examiné.

Le seul type d'index que je connaisse qui marche avec ça est le trigram dans postgresql (mais c'est hors sujet).

> 5min pour insérer les 10 000 pages

C'est 4m59s de trop

> 3h pour insérer les 10 000 pages plus 360 000 liens

C'est 2h59m58s de trop

> SELECT p.id FROM page p JOIN page_item pi ON p.id=pi.page_id WHERE pi.item_id=365055
> => 42ms

Un timing potable (avec un index utilisable) ne dépasserait pas 0.1 ms...

> On peut imaginer utiliser LIKE '%;nombre;%' pour les recherches.

oui

> Peut-être que je surestime cette fonction, on le saura bientôt...

oui

> Je vais probablement garder la table de liens aussi car même si ça complique la gestion des insertions et des suppressions

En fait la table de lien simplifie tout puisqu'elle respecte les usages du SQL et est donc extrêmemnt simple à utiliser. Tu veux ajouter un lien, tu fais un INSERT, tu veux supprimer un lien, tu fais un DELETE, etc. Avec cette daube à base de LIEK c'est totalement ingérable, puisque la BDD ne peut pas interpréter le contenu de la colonne. QUand à l'intégrité référentielle, pouyaya, on est plus à ça près !

Tu mets la charrue avant les boeufs quand même. Une table de lien, ça fonctionne très bien (et c'est beaucoup plus performant que cette daube à base de LIKE), sauf dans un seul cas : quand tu as deux gros ensembles avec une petite intersection et que tu veux l'intersection. Ça arrive pour les gestions de tags, les moteurs de recherche, et les sites de rencontre par exemple. Les moteurs fulltext (et le intarray de postgres, le star join de oracle) sont faits pour gérer ce genre de cas...

Anonyme

5 septembre 2011 à 17:24:06

OK, OK je te fais confiance! Faut croire que j'aime apprendre de mes erreurs

Les temps que j'ai eu sont longs en effet. J'utilisais Windows 7, et MySQL n'est pas configuré pour utiliser beaucoup de RAM. La compatibilité Windows/Ubuntu de mon site devient très contraignante en terme d'organisation, de propreté, et limite énormément les options! J'ai qu'une envie c'est de tout refaire pour Ubuntu seulement :-/ J'ai demandé à faire réinstaller mon serveur privé sous Ubuntu et je vais installer ma base de données proprement puis tester les temps sur cette machine, qui j'espère seront bien meilleurs.

J'ai le dual boot, mais tout serait quand même plus simple si Ubuntu gérait Starcraft II et Modern Warfare 2

Peut-être qu'un linux virtuel ferait l'affaire, à voir...

Lord Casque Noir

5 septembre 2011 à 21:02:16

si mysql utilise plus de ram, ça ne changera pas grand chose à ce genre de requête puisque toute la table doit être examinée...

Anonyme

6 septembre 2011 à 17:25:07

SELECT p.id FROM page p JOIN page_item pi ON p.id=pi.page_id WHERE pi.item_id=365055

Sur mon PC:
=> 450ms => 0.2ms la deuxième fois
Je change l'id en 365054 :
=> 450ms => 0.2ms la deuxième fois
Je remet l'id d'avant :
=> 0.2ms
Je met l'id d'un objet qui n'existe pas :
=> 600ms => 0.2ms la deuxième fois

La même chose se passe sur mon serveur privé sous Ubuntu avec des temps de 450ms puis 0.1ms.

Ma base complète ne pèse fait que 25Mo (5 pour l'index de la table de liens) donc elle tiendrait largement sur la RAM d'un serveur dédié à la base. Je pense que c'est bien une question de RAM, car les temps que j'obtient après la mise en cache automatique semblent être ceux auxquels tu pensais.

Bref, test terminé! Je peux maintenant vider ma base et penser à lui affecter plus de ressources matérielles quand ce sera nécessaire...

Lord Casque Noir

7 septembre 2011 à 10:24:27

attention mysql a un cache de requêtes, utilise :

SELECT SQL_NO_CACHE p.id FROM page p JOIN page_item pi ON p.id=pi.page_id WHERE pi.item_id=365055

sinon les timings sont invalides.

il doit manquer un index sur tes tables, page_item doit avoir (page_id,item_id) (qui est la clé primaire) et (item_id,page_id) pour les recherches...

Anonyme

7 septembre 2011 à 16:22:37

Là tu m'enlèves une aiguille du pied! Tout est sensé maintenant. J'ai faisais un index (champs1, c2, ..) au lieu de un pour chaque : (c1), (c2), ... et maintenant que je comprends, ça change clairement tout
J'ai 1 PRIMARY et 1 UNIQ comme tu m'a indiqué et j'obtiens entre 0.3 et 1.1ms ce qui me convient largement.

SELECT SQL_NO_CACHE * FROM page p INNER JOIN page_item pi ON (pi.page_id, pi.item_id) = (p.id, 365055)
SELECT SQL_NO_CACHE * FROM page p INNER JOIN page_item pi ON pi.page_id = p.id AND pi.item_id = 365055
SELECT SQL_NO_CACHE * FROM page p INNER JOIN page_item pi ON pi.page_id = p.id WHERE pi.item_id = 365055

C'est peut-être une fausse impression mais la dernière m'a l'air un poil plus rapide.
En tout cas, merci pour tout et si tu veux un conseil en Ruby, ai confiance en moi je suis loin d'être le même en Ruby qu'en SQL

Seba991

8 septembre 2011 à 20:53:50

Encore un utilisateur convaincu

(même si ça n'a pas été facile ^^)