Nous attirons votre attention sur une traduction de l' article de Joseph Hellerstein «Looking Back at Postgres» , publié sous la version 4.0 de l' affirmation des droits d'auteur Creative Commons (CC-BY 4.0). Les auteurs se réservent le droit de diffuser ce travail sur des sites Web personnels et d'entreprise avec un lien approprié vers la source.

Traduction réalisée par Elena Indrupskaya. J'ajouterai de moi-même qu '"un programmeur qui voulait désespérément construire un système avec plusieurs versions" semble être Vadim Mikheev, mais nous connaissons tous les "volontaires de Russie" qui ont réécrit GiST.

Annotation

Il s'agit d'un souvenir du projet Postgres, dirigé à l'Université de Californie à Berkeley et dirigé par Mike Stonebraker du milieu des années 1980 au milieu des années 1990. Comme l'un des nombreux souvenirs personnels et historiques, cet article a été demandé pour le livre [ Bro19 ] on Stonebreaker's Turing Award. Par conséquent, l'article se concentre sur le rôle principal de Stonebreaker et ses réflexions sur le design. Mais Stonebreaker n'a jamais été programmeur et n'a pas interféré avec son équipe de développement. La base de code Postgres était le travail d'une équipe d'étudiants brillants et parfois de programmeurs universitaires à temps plein qui avaient un peu plus d'expérience (et seulement un salaire légèrement plus élevé) que les étudiants. J'ai eu la chance de rejoindre cette équipe en tant qu'étudiant au cours des dernières années du projet. J'ai reçu du matériel utile pour cet article de certains des étudiants plus âgés impliqués dans le projet, mais toutes les erreurs ou omissions sont les miennes. Si vous en remarquez, contactez-moi et je vais essayer de les réparer.

1. Introduction

Postgres était le projet le plus ambitieux de Michael Stonebreaker - sa tentative sérieuse de créer un système de base de données universel. Pendant une décennie, le projet a généré plus d'articles, de doctorats, de professeurs et d'entreprises que toute autre activité Stonebreaker. Le projet couvrait également plus du domaine technique que tout autre système qu'il avait construit. Malgré le risque inhérent de cette ampleur, Postgres est également devenu l'artefact logiciel le plus réussi issu des équipes de recherche de Stonebreaker, et sa principale contribution à l'open source. Ceci est un exemple d'un «deuxième système» [ Bro75 ] qui a réussi. Au moment de la rédaction, plus de trente ans depuis le début du projet, le système open source PostgreSQL est le système de base de données open source indépendant le plus populaire au monde et le quatrième système de base de données le plus populaire. Parallèlement, les entreprises créées à partir de Postgres ont généré un total de plus de 2,6 milliards de dollars (en coût d'acquisition). À tous égards, la vision du Postgres Stonebreaker avait une énorme résonance durable.

1.1. Contexte

Stonebreaker a connu un énorme succès au début de sa carrière avec le projet de recherche Ingres Berkeley [ SHWK76 ] et la startup suivante, qu'il a fondée avec Larry Rowe et Eugene Wong: Relational Technology, Inc. (RTI).

Au fur et à mesure que RTI se développait au début des années 1980, Stonebreaker a commencé à travailler sur la prise en charge des types de données dans les SGBD qui allaient au-delà des lignes et colonnes traditionnelles du modèle relationnel Codd d'origine (Edgar Frank Codd). Un exemple motivant à l'époque était le besoin de bases de données pour prendre en charge les outils de conception assistée par ordinateur (CAO) pour l'industrie microélectronique. Dans un article de 1983 de Stonebreaker et d'étudiants, Brad Rubenstein et Antonin Guttman ont expliqué à quel point cette industrie avait besoin de prendre en charge «de nouveaux types de données tels que les polygones, les rectangles, les chaînes de texte, etc.», « recherche spatiale efficace »,« contraintes d'intégrité complexes », ainsi que« hiérarchies de conception et représentations multiples »dans les mêmes structures physiques [ SRG83 ]. Avec cette motivation, le groupe a commencé à travailler sur l'indexation (y compris l'utilisation des arbres R de Guttman pour l'indexation spatiale [ Gut84 ]) et sur l'ajout de types de données abstraits (ADT) au système de base de données relationnelle. À cette époque, les ADT étaient une nouvelle conception populaire des langages de programmation, qui a d'abord été introduite par Barbara Liskov, plus tard lauréate du prix Turing, et explorée dans la programmation d'applications de base de données par Lonely Rowe, un nouveau collaborateur de Stonebreaker. Un article dans un enregistrement SIGMOD de 1983 [ OFS83 ] Stonebreaker et les étudiants James Ong et Dennis Fogg décrivent une étude de ce concept dans l'extension Ingres appelée ADT-Ingres, qui incorpore de nombreux concepts de présentation étudiés plus profondément et avec un meilleur support du système dans Postgres.

2. Postgres: informations générales

Comme son nom l'indique, Postgres est Post-Ingres: un système conçu pour prendre ce qu'Ingres pourrait faire et aller au-delà. Une caractéristique distinctive de Postgres était l'introduction de ce qu'elle a finalement appelé les propriétés objet-relationnelles de la base de données: la prise en charge du concept de programmation orientée objet dans le modèle de données et le langage de requête déclarative du système de base de données. Mais Stonebreaker a également prévu de résoudre un certain nombre d'autres problèmes technologiques indépendants du support orienté objet dans Postgres, tels que les règles de base de données actives, les données versionnées, le stockage tertiaire et la concurrence.

Deux articles ont été écrits sur la conception Postgres: une description de la conception ancienne en 1986 SIGMOD [ SR86 ] et une description intermédiaire dans CACM 1991 [ SK91 ]. Le projet de recherche Postgres a progressivement échoué en 1992 avec la fondation d'Illustra, une startup qui a impliqué Stonebreaker, l'étudiant diplômé principal Wei Hong et plus tard devenu programmeur en chef Jeff Meredith. Dans la liste ci-dessous, les opportunités mentionnées dans l'article de 1986 sont marquées d'un astérisque * et les opportunités de l'article de 1991, qui ne figuraient pas dans l'article de 1986, sont marquées d'un poignard ^† . Les autres tâches énumérées ci-dessous ont été prises dans la documentation sur le système et la recherche, mais elles ne figurent dans aucune spécification de conception. Beaucoup de ces sujets ont été abordés chez Postgres bien avant d'être étudiés ou réinventés par d'autres. Dans de nombreux cas, Postgres était trop en avance sur son temps, et l'intérêt pour les sujets a explosé plus tard, dans une perspective moderne.

Prise en charge d'ADT dans le système de base de données
- Objets complexes (c.-à-d. Données imbriquées ou données de forme non première normale (forme non première normale - NF2)) *
- Types et fonctions de données abstraites personnalisées *
- Méthodes d'accès extensibles pour les nouveaux types de données *
- Traitement optimisé des requêtes avec des fonctionnalités coûteuses définies par l'utilisateur
Bases de données et systèmes de règles actifs (déclencheurs, avertissements) *
- Règles implémentées lors de la réécriture des demandes ^†
- Règles implémentées comme déclencheurs de niveau d'enregistrement ^†
Stockage et récupération basés sur les journaux
- Code de récupération à complexité réduite qui traite le journal comme des données *, en utilisant de la mémoire non volatile pour l'état de validation ^†
- Stockage non réécrit et requêtes temporelles ^†
Prise en charge des nouvelles technologies de stockage en profondeur, en particulier les disques optiques *
Prise en charge des multiprocesseurs et des processeurs spécialisés *
Prise en charge de divers modèles de langue
- Modifications minimales du modèle relationnel et prise en charge des requêtes déclaratives *
- Accès à la «voie rapide» à partir des API internes en contournant le langage de requête ^†
- Multilinguisme ^†

Nous discuterons brièvement de la contribution de Postgres pour chacun de ces éléments par rapport aux travaux ultérieurs dans le domaine de l'informatique.

2.1. Prise en charge d'ADT dans le système de base de données

L'objectif clair de Postgres était de prendre en charge de nouvelles propriétés relationnelles-objet: étendre la technologie de base de données pour fournir les avantages du traitement des requêtes relationnelles et de la programmation orientée objet. Au fil du temps, le concept relationnel-objet qui est apparu pour la première fois dans Postgres est devenu une fonctionnalité standard dans la plupart des systèmes de bases de données modernes.

2.1.1. Objets complexes

Très souvent, les données sont représentées comme des entités imbriquées ou des «objets». Un exemple classique est un bon de commande, qui comprend un ensemble intégré de produits, leurs quantités et leurs prix. La religion de la modélisation relationnelle a dicté que ces données doivent être restructurées et enregistrées dans un format sans imbrication, en utilisant plusieurs tables plates d'objets (commandes, produits) avec des tables plates de relations (product_in_order). Une raison typique de cet aplatissement est qu'il réduit la duplication des données (car le produit est décrit de manière redondante dans de nombreux bons de commande), ce qui évite à son tour la complexité ou les erreurs lors de la mise à jour de toutes les copies redondantes. Mais dans certains cas, vous souhaitez conserver la sous-vue, car elle est naturelle pour l'application (par exemple, le mécanisme de disposition du circuit en CAO), et les mises à jour sont rares. Ce débat sur la modélisation des données est au moins aussi ancien que le modèle relationnel.

L'approche clé de Postgres était de «s'asseoir sur deux chaises» en termes de modélisation des données: Postgres a enregistré les tables en tant que type de données «le plus externe», mais a permis aux colonnes d'avoir des types «complexes», y compris des tuples ou des tables imbriqués. L'une de ses implémentations les moins courantes, explorée pour la première fois dans le prototype ADT-Ingres, était de permettre la déclaration déclarative d'une colonne de type de table comme définition de requête: «Quel comme type de données» [ SAHR84 ] (Quel - Ingres Query Language - Approx. .) .

Le thème «post-relationnel» de la prise en charge à la fois des requêtes déclaratives et des données intégrées est réapparu au fil des ans, souvent généré par des différends sur ce qui est le mieux. À l'époque de Postgres dans les années 1980 et 1990, certains groupes impliqués dans les bases de données orientées objet ont repris cette idée et l'ont développée dans le langage OQL standard, qui a ensuite cessé d'être utilisé.

Au tournant du millénaire, les requêtes déclaratives sur les objets imbriqués sont devenues une obsession de la recherche pour le segment de la communauté des développeurs de bases de données sous forme de bases de données XML. Le langage XQuery résultant (dirigé par Don Chamberlin, le personnage de SQL) est nécessaire pour prendre en charge des objets complexes dans le langage Postgel de Postgres. XQuery est largement utilisé et largement utilisé dans l'industrie, mais n'a jamais été populaire auprès des utilisateurs. Aujourd'hui, ces concepts sont réexaminés dans des projets de langage de requête pour le modèle de données JSON, populaire dans les applications basées sur un navigateur. Comme OQL, dans les groupes qui ont initialement rejeté les requêtes déclaratives en faveur de la programmation orientée développeur (le mouvement «NoSQL»), ces langages n'apparaissent souvent comme un ajout tardif que du désir de rajouter des requêtes au système. Dans le même temps, au fur et à mesure que Postgres a grandi au fil des ans (et est passé du langage de requête Postquel à des versions SQL qui répondent à de nombreux objectifs pris en compte), il a inclus la prise en charge des données intégrées, telles que XML et JSON, dans les SGBD à usage général, sans nécessiter aucune ou refonte importante. La controverse se déroule avec plus ou moins de succès, et l'approche de Postgres pour étendre la structure relationnelle en utilisant des extensions pour les données imbriquées s'est révélée à plusieurs reprises être un état final naturel pour toutes les parties après la fin des arguments.

2.1.2. Types et fonctions de données abstraites personnalisées

En plus de suggérer des types imbriqués, Postgres a avancé l'idée d'introduire des ADT opaques et extensibles qui sont stockés dans la base de données mais non interprétés par le noyau. Fondamentalement, cela a toujours fait partie du modèle relationnel de Codd: les entiers et les chaînes étaient traditionnels, mais en fait le modèle relationnel englobe tout type de données atomiques avec des prédicats. La tâche consistait à fournir une telle flexibilité mathématique dans les logiciels. Pour utiliser des requêtes qui interprètent ces objets et les manipulent, un programmeur d'application doit être en mesure d'enregistrer des fonctions définies par l'utilisateur (UDF) pour ces types dans le système et d'appeler ces fonctions dans des requêtes. Il est également souhaitable que les fonctions d'agrégation définies par l'utilisateur (UDA) résument les collections de ces objets dans les requêtes. Le système de base de données Postgres a été innovant et prend en charge ces fonctionnalités de manière complète.

Pourquoi mettre une telle fonctionnalité dans un SGBD, plutôt que dans des applications de haut niveau? La réponse typique à cette question était un avantage significatif dans la performance du code placé sur les données par rapport à la «traction» des données vers le code. Postgres a montré que cela est tout à fait naturel dans le cadre d'un environnement relationnel: seules des modifications mineures ont été nécessaires dans le catalogue de métadonnées relationnelles et des mécanismes d'appel de code tiers ont été créés, mais la syntaxe de requête, la sémantique et l'architecture du système ont fonctionné de manière simple et élégante.

Postgres est un peu en avance sur son temps pour explorer cette fonctionnalité. En particulier, à cette époque, la communauté des chercheurs en bases de données n'était pas particulièrement inquiète des implications sécuritaires du téléchargement de code non sécurisé sur le serveur. Cela a commencé à être perçu comme un problème lorsque la technologie a été remarquée dans l'industrie. Stonebreaker a mis Postgres sur le marché dans sa startup Illustra, qu'Informix a acquise dans une large mesure pour sa capacité à prendre en charge les packages d'extension DataBlade, y compris UDF. Informix, avec sa technologie basée sur Postgres et ses solides offres de bases de données parallèles, est devenu une menace importante pour Oracle. Oracle a investi massivement dans la commercialisation négative des risques associés à la capacité d'Informix à exécuter du code C utilisateur «non sécurisé». Certains attribuent la mort d'Informix à cette campagne, bien que la fraude financière d'Informix (et les poursuites fédérales ultérieures contre son PDG d'alors) aient certainement posé des problèmes plus graves. Maintenant, des décennies plus tard, tous les principaux fournisseurs de bases de données prennent en charge des fonctions personnalisées dans une ou plusieurs langues, en utilisant de nouvelles technologies pour se protéger contre les pannes de serveur ou la corruption de données.

Pendant ce temps, les piles technologiques des mégadonnées des années 2000, y compris le phénomène MapReduce, qui a «gâté beaucoup de sang» par Stonebreaker et David DeWitt [ DS08 ], sont une réimplémentation de l'idée de Postgres - code utilisateur publié dans le cadre de la demande. Il semble que MapReduce combine en grande partie les idées de développement de logiciels Postgres avec des idées de concurrence de systèmes tels que Gamma et Teradata, avec quelques innovations mineures autour du redémarrage du processus de requête pour les charges de travail avec une évolutivité extrême. Les startups basées sur Postgres, Greenplum et Aster, vers 2007, ont montré que la parallélisation de Postgres pouvait conduire à quelque chose de beaucoup plus fonctionnel et pratique que MapReduce pour la plupart des clients, mais en 2008, le marché n'était toujours pas prêt pour cette technologie. . À l'heure actuelle, en 2018, presque chaque pile de Big Data gère essentiellement la charge de travail SQL parallèle avec UDF, ce qui est très similaire à la conception que Stonebreaker et l'équipe ont utilisée pour la première fois dans Postgres.

2.1.3. Méthodes d'accès extensibles pour les nouveaux types de données

Les bases de données relationnelles se sont développées à peu près au même moment que les arbres B au début des années 1970, et les arbres B ont contribué à donner à Codd un rêve «d'indépendance par rapport au stockage de données physiques»: l'indexation avec les arbres B fournit un niveau d'indirection qui Réorganise le stockage physique de manière adaptative sans nécessiter de modifications d'application. La principale limitation des arbres B et de leurs structures associées est qu'ils ne prennent en charge la recherche et les requêtes d'égalité que dans la plage unidimensionnelle. Mais que faire si vous avez des requêtes de plage bidimensionnelles typiques des applications de cartographie et de CAO? Ce problème était connu lors de Postgres, et l'arbre R [ Gut84 ], développé par Antonin Guttman dans le groupe Stonebreaker, était l'un des nouveaux index les plus réussis conçus pour résoudre ce problème dans la pratique. Cependant, l'invention de la structure d'index ne résout pas le problème de la prise en charge de plages multidimensionnelles dans un SGBD pour des systèmes complexes. Il y a beaucoup de questions. Pouvez-vous facilement ajouter une méthode d'accès, telle que des arborescences R, à votre SGBD? Pouvez-vous apprendre à l'optimiseur à comprendre que la méthode d'accès spécifiée sera utile pour certaines requêtes? Pouvez-vous obtenir une récupération correcte et un accès simultané? C'était un point très audacieux dans le plan d'action de Postgres: un problème d'architecture logicielle affectant la plupart du moteur de base de données, de l'optimiseur au niveau de stockage, ainsi que le système de journalisation et de récupération. Les arbres R de Postgres sont devenus une force motrice puissante et un excellent exemple de l'extensibilité élégante de la couche de méthode d'accès et de son intégration dans l'optimiseur de requêtes. Postgres a montré, à l'aide d'un ADT opaque, comment enregistrer une méthode d'accès décrite de manière abstraite (dans ce cas, un arbre R), et comment un optimiseur de requête peut reconnaître un prédicat de sélection abstrait (dans ce cas, un choix de plage) et le faire correspondre avec cette méthode d'accès décrite de manière abstraite. Une attention moindre a été accordée au contrôle d'accès simultané dans les travaux initiaux: le manque de classement unidimensionnel des clés a rendu la serrure utilisée dans les arbres B dans ce cas inapplicable.

Les caractéristiques prometteuses des méthodes d'accès extensibles de Postgres ont inspiré l'un de mes premiers projets de recherche à la fin des études supérieures: Generalized Search Trees - GiST [ HNP95 ] et le concept ultérieur de théorie de l'indexation [ HKM ⁺ 02 ]. J'ai implémenté GiST dans Postgres pendant un semestre après avoir terminé mon doctorat, ce qui a rendu l'ajout de la nouvelle logique d'indexation à Postgres encore plus facile. La thèse de Marcel Kornacker de Berkeley (Marcel Kornacker) a résolu les problèmes complexes de récupération et d'accès simultané, posés par le type d'index extensible "modèle" GiST [ KMH97 ].

Aujourd'hui, PostgreSQL combine avantageusement l'architecture logicielle originale des méthodes d'accès extensibles (il a des index B-tree, GiST, SP-GiST et Gin) avec l'extensibilité et l'accès concurrentiel intense de l'interface d'arbre de recherche généralisée (GiST). Les index GiST prennent en charge le populaire système de géo-information PostGIS basé sur PostgreSQL. Les index Gin fournissent une prise en charge de l'indexation de texte interne dans PostgreSQL.

2.1.4. Optimiseur de requête avec UDF coûteux

Dans l'optimisation de requête traditionnelle, la tâche consistait à minimiser la quantité de flux de tuple (et donc les opérations d'E / S) créées lors du traitement de la demande. Cela signifie que les instructions qui filtrent les tuples (extraction) sont bonnes au début du plan de requête, tandis que les instructions qui peuvent générer de nouveaux tuples (jointure) doivent être exécutées plus tard. Par conséquent, les optimiseurs de requêtes «poussent» les opérateurs d'extraction sous les connexions et les organisent de manière aléatoire, en se concentrant plutôt sur une optimisation intelligente des connexions et des accès au disque. Les FDU ont changé l'approche: si vous avez des FDU coûteuses dans vos exemples d'instructions, l'ordre d'exécution des FDU peut être critique pour optimiser les performances. De plus, si l'UDF dans l'opérateur de sélection prend vraiment beaucoup de temps, il est possible que la sélection soit effectuée après les connexions (c'est-à-dire que la sélection doit être «pull up» - sélection «pullup»). La prise en compte de ces facteurs a compliqué l'espace de recherche de l'optimiseur. J'ai pris ce problème comme la première tâche difficile à l'école supérieure, et il a fini par faire l'objet de mon travail de maîtrise avec Stonebreaker à Berkeley et de mon doctorat au Wisconsin sous la direction de Jeff Naughton, mais avec l'aide constante des conseils de Stonebreaker. Postgres a été le premier SGBD à stocker le coût et la sélectivité des fonctions définies par l'utilisateur dans un répertoire de base de données. Nous avons abordé le problème d'optimisation, ayant trouvé l'ordre optimal des opérations d'échantillonnage, puis l'alternance optimale des opérations d'échantillonnage le long des branches de chaque arbre de connexion considéré dans la recherche de plan. System R .

, , . , , .

PostgreSQL , . , , , , 2018 . , , , , , . , Postgres .

, , , PostgreSQL (Neil Conway), « » .

2.2.

Postgres . : , « », 1990- .

. — Datalog. « » : , , .

Datalog , - . Datalog — « » . , , .

, , , , . .

(Eric Hanson), Ingres, Postgres. (Spyros Potamianos) PRS2: Postgres Rules System 2. . — . , Ingres. « » « ». , « » « 10%». , « », . ( ), .

PRS2 , , . Postgres (, ) Postgres 3.1 1991 ( ):

 
*        :
*     .        
*  (. .        
* "" )    .   -  
*   () .        .
*   .    .     
*   .  ...
* ,  , ? ,    ,  .
*         , 
*  ...

Postgres , «» — . PostgreSQL, - .

Postgres « » IBM Starburst MCC HiPAC. SQL . . , , , , « »: , . , - , , , , . , , , , Postgres.

2.3. X

Postgres :

Postgres, - . (write-ahead log — WAL), , . , Ingres 1970- , . [ SK91 ]

, , . , IBM Tandem . : - , , , .

X Postgres . , , , — « » « » . , , — . , «» . : , . Postgres, , , , [ Sto87 ]. Postgres .

« » , , . . , , , , Postgres. Postgres . PostgreSQL .

, PostgreSQL : . , PostgreSQL , Postgres, , Postgres . , (snapshot isolation) Oracle -, .

(Mike Olson) , , B- Postgres B- Berkeley DB, Postgres. . Berkeley DB Sleepycat Corp., () PostgreSQL « ». : , (MVCC), , .

PostgreSQL . Greenplum PostgreSQL . (Matt McCline)— (Jim Gray) Tandem. .

. , NoSQL ( , WAL), (MMDB — main memory databases, ). , . , .

2.4.

Au milieu du projet Postgres, Stonebreaker s'est inscrit comme l'un des cadres pour une grande subvention numérique de science des terres appelée Project Sequoia. Une partie de la proposition de subvention portait sur le traitement de quantités sans précédent d'images numériques par satellite, nécessitant jusqu'à 100 téraoctets de mémoire, c'est-à-dire une quantité de données beaucoup plus importante qu'il ne serait sage de stocker sur des disques magnétiques à l'époque. La base de la solution proposée était d'étudier l'idée de créer un SGBD (à savoir Postgres), qui facilite l'accès au stockage «tertiaire» semi-autonome fourni par les lecteurs robotiques avec remplacement automatique du disque pour gérer les disques optiques ou les bibliothèques de bandes.

Cela a conduit à plusieurs études différentes. L'un d'eux était le système de fichiers Inversion - une tentative de fournir une abstraction du système de fichiers UNIX sur un SGBD relationnel. Dans un article de synthèse pour Sequoia, Stonebreaker l'a décrit dans son style habituel de «simple exercice» condescendant [ Sto95 ]. En fait, Mike Olson, étudiant à Stonebreaker (et fondateur de Cloudera par la suite), s'occupe de cela depuis plusieurs années, et le résultat final n'a pas été très simple [ Ols93 ] et n'a pas survécu dans la pratique.

Quelques années plus tard, Inversion Bill Gates «a combattu les mêmes moulins à vent» dans WinFS - une tentative de recréer le système de fichiers le plus utilisé au monde sur l'arrière d'une base de données relationnelle. WinFS a été livré dans les versions de développement de Windows, mais n'est jamais entré sur le marché. Gates l'a appelé plus tard sa plus grande déception chez Microsoft.

Un autre domaine de recherche principal sur ce front a été l'inclusion d'un référentiel tertiaire sur la pile de bases de données relationnelles plus typiques, qui a fait l'objet d'une thèse de doctorat de Sunita Sarawagi. Le sujet principal était de changer l'échelle dans laquelle vous envisagez de gérer l'espace (c'est-à-dire les données stockées et la hiérarchie de la mémoire) et le temps (coordonner la planification des requêtes et le cache pour minimiser les E / S indésirables). L'un des principaux problèmes de ce travail était de stocker de grands tableaux multidimensionnels dans un stockage tertiaire et de les récupérer, ce qui fait écho aux travaux dans le domaine de l'indexation multidimensionnelle. Les idées clés comprenaient la division du tableau en parties et le stockage ensemble des parties sélectionnées ensemble, ainsi que la réplication des parties afin que la partie de données puisse avoir plusieurs «voisins» physiques. Le deuxième problème est de réfléchir à la façon dont le disque devient un cache pour le stockage tertiaire. Enfin, l'optimisation et la planification des requêtes doivent tenir compte du temps de chargement long des données du stockage tertiaire et de l'importance des hits (hits) du cache disque. Cela affecte à la fois le plan choisi par l'optimiseur de requêtes et le temps nécessaire pour terminer le plan.

Les robots sur bandes et disques optiques ne sont actuellement pas largement utilisés. Mais les problèmes de stockage tertiaire sont très courants dans le cloud, qui en 2018 a une hiérarchie de stockage profonde: des SSD attachés aux services de stockage fiables de type disque (par exemple, AWS EBS), au stockage d'archives (par exemple, dans AWS S3), au stockage profond (par exemple , AWS Glacier). Aujourd'hui, ces niveaux de stockage sont encore relativement séparés, et le raisonnement sur le stockage de bout en bout englobant ces niveaux n'est pratiquement pas pris en charge par la base de données. Je ne serais pas surpris que les questions examinées à ce sujet dans Postgres soient réexaminées prochainement.

2.5. Prise en charge multiprocesseur: XPRS

Stonebreaker n'a jamais créé un grand système de base de données parallèle, mais il a dirigé de nombreuses discussions difficiles dans ce domaine. Son article «Case for Shared Nothing» [ Sto86 ] a documenté des solutions architecturales modulaires à grande échelle dans ce domaine. Il a popularisé la terminologie utilisée dans l'industrie et a intrigué le support des architectures sans ressources partagées, telles que Gamma et Teradata, qui ont été redécouvertes dans les années 2000 par la communauté du Big Data.

Ironiquement, la contribution la plus importante de Stonebreaker dans le domaine des bases de données parallèles était l'architecture de «mémoire partagée» appelée XPRS, qui signifiait «PostgreSQL étendu sur RAID et Sprite». Au début des années 1990, XPRS était la «ligue de justice» pour les systèmes Berkeley: il combine le système abrégé Postgres Stonebreaker, John Ousterhout, le système d'exploitation Sprite distribué, et l'architecture RAID Dave Patterson et Randy Katz RAID ) Comme pour de nombreux emplois inter-facultaires, la mise en œuvre du projet XPRS a en fait été déterminée par les étudiants diplômés qui y ont travaillé. Il s'est avéré que la principale contribution a été apportée par Wei Hong, qui a rédigé sa thèse de doctorat sur l'optimisation des requêtes parallèles dans XPRS. Ainsi, la principale contribution de XPRS à la littérature et à l'industrie a été d'optimiser les requêtes simultanées sans aborder de manière significative les problèmes associés à RAID ou Sprite.

De ces trois projets, Postgres et RAID ont eu un impact énorme sur l'avenir. Sprite est le meilleur souvenir de la thèse de doctorat de Mendel Rosenblum sur les systèmes de fichiers structurés (LFS), qui n'avait rien à voir avec les systèmes d'exploitation distribués. Les trois projets contenaient de nouvelles idées pour le stockage sur disque, en plus de modifier les copies individuelles en place. LFS et le gestionnaire de référentiel Postgres sont assez similaires dans leur nouveau traitement de la revue comme référentiel principal et la nécessité d'une réorganisation en arrière-plan coûteuse. Une fois, j'ai soigneusement sondé le Stonebreaker sur la rivalité entre LFS et Postgres ou les "faits frits" académiques sur leur relation, mais je n'ai jamais rien appris d'intéressant de sa part. Peut-être qu'à ce moment-là, à Berkeley, quelqu'un «remuait de l'eau».

En principe, la concurrence «explose» l'espace des plans de l'optimiseur de requêtes, multipliant les choix traditionnels effectués lors de l'optimisation des requêtes (accès aux données, algorithmes de connexion, ordre de connexion) par toutes les manières possibles de paralléliser chaque choix. L'idée principale de «l'optimiseur Wei Hong» appelé par Stonebreaker était de diviser le problème en deux: lancer l'optimiseur de requête traditionnel dans l'esprit du système R pour un nœud, puis «paralléliser» le plan résultant, planifier le degré de parallélisme et le placement de chaque opérateur en fonction de la représentation configuration des données et du système. Cette approche est heuristique, mais en elle la simultanéité augmente le coût de l'optimisation de requête traditionnelle de manière additive, plutôt que multiplicative.

Bien que l'optimiseur de Wei Hong ait été développé dans le contexte de Postgres, il est devenu l'approche standard pour de nombreux optimiseurs de requêtes simultanés dans l'industrie.

2.6. Prise en charge de divers modèles de langue

Parmi les intérêts de Stonebreaker, renouvelé à plusieurs reprises depuis l'époque d'Ingres, figurait l'interface de programmation d'application (API) du système de base de données. Dans ses conférences de la série Database Systems, il a souvent inclus le langage GEM Carlo Zaniolo comme un sujet qu'il est important de comprendre pour les partisans du système de base de données. Cet intérêt pour le langage l'a sans aucun doute amené à s'associer avec Larry Rowe dans Postgres, qui à son tour a profondément influencé la conception du modèle de données Postgres et son approche relationnelle objet. Leur travail était principalement axé sur les applications pour travailler avec un grand volume de données de la sphère commerciale, y compris le traitement des informations commerciales et les nouvelles applications telles que CAD / CAM et GIS.

L'un des problèmes qui a été imposé à Stonebreaker à l'époque était l'idée de «cacher» les frontières entre les constructions du langage de programmation et le référentiel de base de données. Divers projets de recherche et entreprises concurrentes qui recherchent des bases de données orientées objet (OODB) ont ciblé la soi-disant «perte de conformité» entre les langages de programmation orientés objet impératifs tels que Smalltalk, C ++ et Java, et les relations déclaratives modèle. L'idée d'OODB était de rendre les objets du langage de programmation, si désiré, marqués comme «permanents» et automatiquement traités par le SGBD intégré. Postgres a pris en charge le stockage d'objets imbriqués et de types de données abstraits, mais son interface, basée sur des requêtes déclaratives dans un style relationnel, a supposé un accès non naturel à la base de données pour le programmeur (cela nécessitait l'utilisation de requêtes déclaratives), qui étaient également coûteuses (nécessitant une analyse et optimisation). Pour concurrencer les fournisseurs OODB, Postgres a fourni la soi-disant interface Fast Path: essentiellement l'API C / C ++ pour le stockage de base de données interne. Cela a permis à Postgres d'avoir des performances de référence académiques OODB moyennes, mais cela n'a jamais résolu le problème de laisser les programmeurs dans différentes langues éviter le problème de la perte de conformité. Au lieu de cela, Stonebreaker a qualifié Postgres de label «objet-relationnel» et a simplement contourné l'utilisation de bases de données orientées objet en tant que marché à zéro milliard de dollars. Aujourd'hui, presque tous les systèmes de bases de données relationnelles commerciales sont des systèmes de bases de données «relationnels-objets».

Cela s'est avéré être une solution raisonnable. Aujourd'hui, aucun des produits OODB n'existe sous sa forme prévue, et l'idée d '"objets persistants" dans les langages de programmation a été largement écartée. En revanche, l'utilisation de couches de cartographie relationnelle objet (ORM) est très répandue, alimentée par des travaux antérieurs, tels que Java Hibernate et Ruby on Rails, qui permettent «d'adapter» les bases de données déclaratives à presque tous les objets impératifs de manière relativement fluide. langage de programmation orienté comme bibliothèques. Cette approche au niveau de l'application diffère des bases de données relationnelles objet OODB et Stonebreaker. En outre, des stockages de valeurs-clés légers sont également utilisés avec succès sous des formes non transactionnelles et transactionnelles. Leur découvreur était l'étudiant diplômé de Stonebreaker Margo Seltzer, qui a travaillé sur la base de données Berkeley DB dans le cadre de sa thèse de doctorat en même temps que le groupe Postgres, qui prévoyait la croissance des référentiels de valeurs-clés NoSQL distribués tels que Dynamo , MongoDB et Cassandra.

3. Impact sur les logiciels

3.1. Open source

Postgres a toujours été un projet open source avec des versions cohérentes, mais au début, il était destiné à être utilisé pour la recherche plutôt que pour la production.

Comme le projet de recherche Postgres a été interrompu, deux étudiants de Stonebreaker, Andrew Yu et Jolly Chen, ont modifié l'analyseur système pour remplacer le langage Postquel original par une variante SQL extensible. La première version de Postgres prenant en charge SQL était Postgres95, et la suivante s'appelait PostgreSQL.

Une équipe de développement open source s'est intéressée à PostgreSQL et l'a «acceptée» même si les intérêts du reste de l'équipe de Berkeley ont changé. L'équipe centrale de PostgreSQL est restée relativement stable au fil du temps et le projet open source est devenu très développé. Initialement, les efforts étaient concentrés sur la stabilité du code et des fonctionnalités visibles par l'utilisateur, mais au fil du temps, la communauté des logiciels open source a considérablement changé et amélioré le cœur du système, de l'optimiseur aux méthodes d'accès et au principal système de transaction et de stockage. Depuis le milieu des années 1990, une très petite fraction des composants internes de PostgreSQL provenait de l'équipe académique de Berkeley. Sa dernière contribution a peut-être été ma mise en œuvre de GiST dans la seconde moitié des années 1990, mais même elle a été substantiellement réécrite et approuvée par des bénévoles de la communauté open source (dans ce cas, la Russie). La partie de la communauté open source qui travaille sur PostgreSQL mérite les plus grands éloges pour son processus rationalisé, qui pendant des décennies a servi à créer un projet très efficace et à long terme.

Bien que beaucoup de choses aient changé au cours des 25 dernières années, l'architecture sous-jacente de PostgreSQL reste très similaire aux versions universitaires de Postgres au début des années 1990, et les développeurs familiarisés avec le code source actuel de PostgreSQL trouveront facile de lire le code source de Postgres 3.1 (1991). Tout, de la structure du répertoire du code source aux structures de processus et aux structures de données, reste étonnamment similaire. Le code de l'équipe Postgres à Berkeley avait une grande colonne vertébrale.

Aujourd'hui, PostgreSQL est sans aucun doute le système de gestion de base de données open source le plus performant, et il prend en charge des fonctionnalités que l'on ne trouve souvent pas dans les produits commerciaux. Il s'agit également (selon un site de notation influent) du SGBD indépendant open source le plus populaire au monde, et son influence ne cesse de croître: en 2017 et 2018, il s'agissait de la base de données ayant la popularité la plus rapide au monde [ DE19c ]. PostgreSQL est utilisé dans une grande variété d'industries et de tâches, ce qui n'est pas surprenant, étant donné sa concentration sur de nombreuses opportunités.

Selon DB-Engines, PostgreSQL est aujourd'hui la quatrième base de données la plus populaire au monde, après Oracle, MySQL et MS SQL Server, tous trois proposés par des sociétés spécifiques (MySQL a été acquis par Oracle il y a de nombreuses années) [ DE19a ]. Les règles de classement sont discutées dans la description de la méthodologie de classement DB-Engines [ DE19b ].

Heroku est le fournisseur de cloud SaaS qui fait désormais partie de Salesforce. Postgres a été introduit dans Heroku en 2010 comme base de données par défaut pour sa plate-forme. Heroku a choisi Postgres pour sa fiabilité. Avec la prise en charge de Heroku, de plus grandes plates-formes de développement d'applications telles que Ruby on Rails et Python pour Django ont commencé à recommander Postgres comme base de données par défaut.

Aujourd'hui, PostgreSQL prend en charge une infrastructure d'extension qui facilite l'ajout de fonctionnalités supplémentaires au système via des fonctions définies par l'utilisateur et les modifications associées. Il existe maintenant un écosystème d'extensions PostgreSQL, semblable au concept llustra des packages d'extension DataBlade, mais avec du code open source. Les extensions les plus intéressantes incluent, par exemple, la bibliothèque Apache MADlib pour l'apprentissage automatique dans l'interface SQL et la bibliothèque Citus pour l'exécution de requêtes parallèles.

L'une des applications open source les plus intéressantes reposant sur Postgres est le système d'information géographique PostGIS, qui utilise de nombreuses fonctionnalités Postgres qui ont inspiré Stonebreaker à l'origine pour démarrer le projet.

3.2. Mise en œuvre commerciale

PostgreSQL est depuis longtemps un point de départ attrayant pour la création de systèmes de bases de données commerciales, étant donné son utilisation sous la licence logicielle open source «tout autorisée», son code fiable, sa flexibilité et ses nombreuses fonctionnalités. En résumant les coûts d'acquisition énumérés ci-dessous, nous constatons que Postgres a reçu plus de 2,6 milliards de dollars en coûts d'acquisition.

Veuillez noter qu'il s'agit d'une mesure en dollars de transactions financières réelles et est beaucoup plus importante que les valeurs qui sont souvent utilisées en haute technologie. Les chiffres en milliards sont souvent utilisés pour décrire la valeur estimée des blocs d'actions, mais sont souvent surestimés de 10 fois ou plus par rapport à la valeur actuelle dans l'espoir de son importance future. Les dollars de transaction d'acquisition de la société mesurent sa valeur marchande réelle au moment de l'acquisition. Il est juste de dire que Postgres a créé plus de 2,6 milliards de dollars de valeur commerciale réelle.

De nombreux efforts commerciaux associés à PostgreSQL se sont concentrés sur ce qui est probablement sa principale limitation: la capacité d'évoluer vers une architecture parallèle sans partager les ressources.

La parallélisation de PostgreSQL nécessite beaucoup de travail, mais est hautement réalisable par une petite équipe expérimentée. Aujourd'hui, les branches de l'industrie open source PostgreSQL telles que Greenplum et CitusDB offrent une telle opportunité. Il est regrettable que PostgreSQL n'ait pas été correctement parallélisé en open source beaucoup plus tôt. Si PostgreSQL avait été développé dans l'open source avec le support d'une architecture sans partage de ressources au début des années 2000, il est possible que la direction du big data open source se soit développée d'une manière complètement différente et plus efficace.

Illustra était la deuxième plus grande startup de Stonebreaker, fondée en 1992 pour commercialiser Postgres, lorsque RTI a lancé Ingres sur le marché.

Illustra était en fait le troisième nom proposé pour l'entreprise. Poursuivant le thème de la peinture, étant donné le nom d'Ingres, Illustra s'appelait à l'origine Miro. En raison de problèmes de marque, le nom a été changé pour Montage, mais il a également rencontré des problèmes de marque.

L'équipe fondatrice comprenait une partie du noyau de l'équipe Postgres, y compris Wei Hong, récemment diplômé de l'école supérieure et Jeff Meredith, alors programmeur senior, ainsi que des diplômés d'Ingres Paula Hawthorn et Michael Ubell. Mike Olson, étudiant diplômé de Postgres, a rejoint l'équipe peu de temps après sa fondation et j'ai travaillé chez Illustra pour optimiser des fonctionnalités coûteuses dans le cadre de mon doctorat. Illustra : SQL92 , Postquel, Postgres DataBlade — . Illustra Informix 1997 400 . . [ Mon96 ], DataBlade Informix Informix Universal Server.
Netezza , 1999 , PostgreSQL FPGA. Netezza , 2007 . IBM 1,7 . . [ IBM10 ].
Greenplum PostgreSQL . 2003 , Greenplum PostgreSQL, API PostgreSQL, API . , Greenplum PostgreSQL , , Orca. Greenplum EMC 2010 300 . . [ Mal10 ], 2012 EMC Greenplum Pivotal. 2015 Pivotal Greenplum Orca . Greenplum Postgres API MADlib SQL [ HRS+12 ]. MADlib Apache. , Greenplum, Apache HAWQ, Pivotal, « » Greenplum (. . PostgreSQL) , Hadoop.
EnterpriseDB 2004 , PostgreSQL , . EnterpriseDB Advanced Server Oracle, Oracle.
Aster Data 2005 , . PostgreSQL. Aster , SQL MapReduce. Aster Data Teradata 2011 263 . . [ Sho11 ]. Teradata Aster , - Aster Teradata.
ParAccel 2006 , PostgreSQL . ParAccel Postgres . 2011 Amazon ParAccel, 2012 AWS Redshift — ParAccel. 2013 ParAccel Actian ( Ingres) , , Actian. AWS Redshift Amazon — Amazon, , , Teradata Oracle Exadata. Postgres .
CitusDB (CitusDB — ; Citus Data. — . .) 2010 , PostgreSQL . PostgreSQL, 2016 CitusDB API PostgreSQL PostgreSQL. 2016 CitusDB .

4.

Postgres, .

, , , Postgres « » (Second System Effect) (Fred Brooks) [ Bro75 ]. , , - . Postgres , , , . , , . — Postgres , . : , . , « » . , , . «-» , «-» .

, , « », , . ( 2001 (). — . .) 2000- « ». , Postgres. , , .

(Ralph Waldo Emerson), « — ».

, « » ( ), , , , , . , . , , - . , . , .

, Postgres, — , . « » PostgreSQL, , . , :

, , , 1995 . Postgres, , . , , , . [ Sto14 ]

, , , , « » . « ». , , , , Postgres. - , : « - ». ( ), .

5.

Postgres , , (Craig Kerstiens) PostgreSQL.

Littérature

[Bro75] Frederick P Brooks. The mythical man-month, 1975.
[Bro19] Michael L. Brodie, editor. Making Databases Work. Morgan & Claypool, 2019.
[DE19a] DB-Engines. DB-Engines ranking, 2019. db-engines.com/en/ranking . (Last accessed January 4, 2019).
[DE19b] DB-Engines. Method of calculating the scores of the DB-Engines ranking, 2019. db-engines.com/en/ranking_definition (Last accessed January 4, 2019).
[DE19c] DB-Engines. PostgreSQL is the DBMS of the year 2018, January 2019. db-engines.com/en/blog_post/79 (Last accessed January 4, 2019).
[DS08] David DeWitt and Michael Stonebraker. Mapreduce: A major step backwards. The Database Column, 1:23, 2008.
[Gut84] Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, SIGMOD '84, pages 47–57, New York, NY, USA, 1984. ACM.
[HKM ⁺ 02] Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, and Vasilis Samoladas. On a model of indexability and its bounds for range queries. J. ACM, 49(1):35–55, January 2002.
[HNP95] Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. Generalized search trees for database systems. In Proceedings of the 21th International Conference on Very Large Data Bases, VLDB '95, pages 562–573, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
[HRS ⁺ 12] Joseph M Hellerstein, Christoper Re, Florian Schoppmann, Daisy Zhe Wang, Eugene Fratkin, Aleksander Gorajek, Kee Siong Ng, Caleb Welton, Xixuan Feng, Kun Li, et al. The MADlib analytics library: or MAD skills, the SQL. Proceedings of the VLDB Endowment, 5(12):1700–1711, 2012.
[IBM10] IBM to acquire Netezza, September 2010. www-03.ibm.com/press/us/en/pressrelease/32514.wss#release (Last accessed January 22, 2018).
[KMH97] Marcel Kornacker, C. Mohan, and Joseph M. Hellerstein. Concurrency and recovery in generalized search trees. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, SIGMOD '97, pages 62–72, New York, NY, USA, 1997. ACM.
[Mal10] Om Malik. Big Data = Big Money: EMC Buys Greenplum. In GigaOm, July 2010. gigaom.com/2010/07/06/emc-buys-greenplum .
[Mon96] John Monroe. Informix acquires illustra for complex data management. In Federal Computer Week, January 1996.
[OFS83] James Ong, Dennis Fogg, and Michael Stonebraker. Implementation of data abstraction in the relational database system ingres. ACM Sigmod Record, 14(1):1–14, 1983.
[Ols93] Michael A. Olson. The design and implementation of the inversion file system. 1993.
[SAHR84] Michael Stonebraker, Erika Anderson, Eric Hanson, and Brad Rubenstein. Quel as a data type. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, SIGMOD '84, pages 208–214, New York, NY, USA, 1984. ACM.
[Sho11] Erick Shonfeld. Big pay day for big data. teradata buys aster data for $263 million. In TechCrunch, May 2011. techcrunch.com/2011/03/03/teradata-buys-aster-data-263-million (Last accessed January 22, 2018).
[SHWK76] Michael Stonebraker, Gerald Held, Eugene Wong, and Peter Kreps. The design and implementation of ingres. ACM Transactions on Database Systems (TODS), 1(3):189–222, 1976.
[SK91] Michael Stonebraker and Greg Kemnitz. The postgres next generation database management system. Commun. ACM, 34(10):78–92, October 1991.
[SR86] Michael Stonebraker and Lawrence A. Rowe. The design of postgres. In Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, SIGMOD '86, pages 340–355, New York, NY, USA, 1986. ACM.
[SRG83] M Stonebraker, B Rubenstein, and A Guttman. Application of abstract data types and abstract indices to cad bases. IEEE Trans, on Software Engineering, 1983.
[Sto86] Michael Stonebraker. The case for shared nothing. IEEE Database Eng. Bull., 9(1):4–9, 1986.
[Sto87] Michael Stonebraker. The design of the postgres storage system. In Proceedings of the 13th International Conference on Very Large Data Bases, VLDB '87, pages 289–300, San Francisco, CA, USA, 1987. Morgan Kaufmann Publishers Inc.
[Sto95] Michael Stonebraker. An overview of the sequoia 2000 project. Digital Technical Journal, 7(3):39–49, 1995.
[Sto14] Michael Stonebraker. The land sharks are on the squawk box, 2014. www.acm.org/turing-lecture-stonebraker (Last accessed January 4, 2019).

Postgres rétrospectivement