精华内容
下载资源
问答
  • 那些必读的数据库领域论文

    千次阅读 2019-12-18 21:06:30
    点击蓝色“有关SQL”关注我哟加个“星标”,天天与6000人一起快乐成长文 | 刘江总编地址 |点击原文链接可得推荐理由:这两天在尝试搜集所有数据库包括非关系型数据库和分...

    点击蓝色“有关SQL”关注我哟

    加个“星标”,天天与6000人一起快乐成长

    文      | 刘江总编

    地址   | 点击原文链接可得

    推荐理由:这两天在尝试搜集所有数据库包括非关系型数据库和分布式数据库的论文,以及一些经典的 Blog,教材还有优秀书籍。这是CSDN刘江总编的一篇整理,推荐给数据库爱好者。等论文搜集好了,会在公众号分享,大家回复1024,便可拿到。

    正文

    之前林仕鼎曾整理过系统架构领域的学习资料,这几天Spark核心团队成员辛湜(Reynold Xin)公开了他整理的一份数据库学习资料列表,Hacker News上引起了不少讨论。其中的评述文字也很有价值,简要编译如下。大家对这个列表如有补充,请评论。

    基础与算法

    • The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb (1997): 此文与十年前的原始论文解释了一个量化公式,用来计算数据页是否应该缓存在内存中。能读到Jim Gray处理一系列相关问题(比如数据页应该多大)的方法,幸何如之。

    • Paxos Made Simple (2001): Paxos构成了许多分布式系统的基础。想法很简单,但理解起来却出名的难(可能是因为原始论文的写法太……)。

    • AlphaSort: A Cache-Sensitive Parallel External Sort (1995): 缓存友好的排序。

    • Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (2014): 实际使用中各种排序算法及其利弊很好的综述。

    关系数据库

    • Anatomy of a Database System (200x): Joe Hellerstein(伯克利教授,数据库专家)对关系数据库很棒的综述,涉及到各个组件。

    • A Relational Model of Data for Large Shared Data Banks (1970): Codd对数据独立性的探讨。尽管最近NoSQL兴起,但我相信这篇论文的一些思想在大规模并行数据系统中越来越重要了。

    • ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging (1992): 第一个实际可用的算法,支持在故障时并发事务执行而又不丢失数据。此文既有底层细节,又有高层算法的解释,因此很难读。可能还不如先去读一本数据库教材。

    • Efficient Locking for Concurrent Operations on B-Trees (1981)和The R*-tree: An Efficient and Robust Access Method for Points and Rectangles (1990): B-Tree是各类数据库的核心数据结构,在随机查找时读放大因子很低。R-tree是B-Tree的扩展,支持多维数据(如地理数据)的查找。

    • Improved Query Performance with Variant Indexes (1997): 分析型数据库和OLTP数据库需要不同的利弊权衡方式。这反映在索引数据结构的选择上。此文讨论了许多更适合分析型数据库的索引数据结构。

    • On Optimistic Methods for Concurrency Control (1981): 支持并发有悲观和乐观两种方式。此文解释了乐观并发控制。……

    • Access Path Selection in a Relational Database Management System (1979): 查询优化的基础。此文解释了传统的成本模型方法,以及选择最佳计划的一个动态规划方法。……

    • Eddies: Continuously Adaptive Query Processing (2000): 此文模仿流体力学提出了一系列动态优化查询执行的技术。虽然Eddies还没有商业系统的实际应用,但很启发思路,重要性也在与日俱增。……

    经典的系统设计

    • A History and Evaluation of System R (1981): IBM的System R和Berkeley的Ingres两个系统都证明了关系数据库是可行的。值得注意的是,30年来关系数据库的内部并没有什么太大变化。

    • The Google File System (2003) 和 Bigtable: A Distributed Storage System for Structured Data (2006): Google数据基础设施的两大核心组件。……虽然可能已经被Google更新的技术取代,但其中的思想将历久弥新。

    • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (2001) 和 Dynamo: Amazon’s Highly Available Key-value Store (2007): Chord诞生于分布式散列表还是学术研究热点的时代。它只做一件事儿,却做到了极致:如何在完全分布式的环境(P2P)中使用一致性散列查找键的位置。Dynamo论文则解释了如何使用Chord构建分布式K-V存储。请注意Dynamo与Chord有一些设计决策上的变化,比如指取表(finger table)是O(N)的而不是O(logN)的,因为Dynamo为Amazon内部使用,对数据中心的节点有更大控制权,而Chord针对的是广域网中的P2P节点。

    列式数据库

    列式存储和面向列的查询引擎对于分析型负荷即OLAP至关重要,已有15年历史(最早的MonetDB论文发表于1999年),到现在几乎所有商业数据仓库都有列式引擎了。

    • C-Store: A Column-oriented DBMS (2005) 和 The Vertica Analytic Database: C-Store 7 Years Later (2012): C-Store是新英格兰地区多所大学(指MIT、布朗、马萨诸塞州大等)的专家们很有影响的学术研究。Vertica是其商业化版本。

    • Column-Stores vs. Row-Stores: How Different Are They Really? (2012): 讨论列式存储和查询引擎的重要性。

    • Dremel: Interactive Analysis of Web-Scale Datasets (2010): Google令人惊叹的论文。……将列式存储应用于复杂的嵌套数据结构。论文对嵌套数据结构的支持谈得很多,对查询执行的细节涉及较少。有好几个开源项目声称自己在构建Dremel的开源版。但Dremel系统通过大规模并行和列式存储实现低延迟,因此在Google之外这种模型未必有用,因为很少有公司能搞得起几千个节点来做即时查询。

    数据并行计算

    • MapReduce: Simplified Data Processing on Large Clusters (2004): MapReduce既是一种编程模型(借鉴自函数式编程中的古老概念),也是Google用于分布式数据密集计算的系统。这个编程模型如此简单而又功能强大,能够满足广泛的编程需求。系统加上模型,是容错而且可扩展的。说现在有一半学术界的人在研究的问题都受到MapReduce的极大影响,应该并不为过。

    • Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (2012): 伯克利Spark集群技术项目背后的学术论文。Spark公开了RDD这种分布式内存抽象,是跨一个集群内存分布的不可变记录集合。RDD可以转换为使用MapReduce式的计算。RDD抽象对有强时间局部性的负荷(比如查询处理和迭代机器学习)效率可以提高几个数量级。Spark是一个很好的例子,说明了将MapReduce编程模型与执行引擎分离的重要性。

    • Shark: SQL and Rich Analytics at Scale (2013): 描述了Shark系统,构建在Spark上的SQL引擎。这篇论文更重要的是讨论了为什么之前的SQL on Hadoop/MapReduce查询引擎都这么慢。

    • Spanner (2012): Spanner是“可扩展、多版本、全球分布和同步复制的数据库”。其中关键是TrueTime API,那个在多个节点之间无需通信而为事件定序。有人猜测TrueTime API与向量钟类似,但每个节点必须存储较少数据。不幸的是,虽然Google说要发表关于TrueTime的论文,但现在还没看到。

    • Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks (2007): Dryad是微软开发的编程模型,支持大规模数据流编程。“MapReduce与Dryad的差异在于,Dryad应用可以指定任意的通信DAG,而不是非要用map/distribute/sort/reduce操作序列。”

    趋势(云计算,仓库规模计算和新硬件)

    • A View of Cloud Computing (2010): 关于云计算的权威论文。从技术角度讨论了云计算(主要指资源的弹性而不是面向消费者的“云”)的经济意义和阻碍因素。这些阻碍因素将影响云中系统的设计决策。

    • The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines: Google的Luiz André Barroso和Urs Hölzle解释了仓库规模技术中数据中心软硬件的基础知识。还有配套的视频(注:HighScalability有相应文章)讨论了在大规模并行系统中减少长尾延迟(long-tail latency)的重要性。其他的关键思想还包括资源的解聚(disaggregation)。GFS/HDFS这样的技术已经用高速网络带宽解聚了硬盘,但是DRAM还没有看到这种趋势,因为那需要低延迟联网。

    • CAP Twelve Years Later: How the "Rules" Have Changed (2012): Eric Brewer提出的CAP定理指出,任何联网的共享数据系统都只能在一致性、可用性和分区容忍性三个属性中保证其中两个。许多NoSQL存储都用此为自己牺牲一致性的设计决策来辩解。此文是Eric Brewer回顾文章,解释了“‘三中取二’的表述是错误的,过度简化了各个属性之间的矛盾关系。”

    杂项

    • Reflections on Trusting Trust (1984): 1984年Ken Thompson的图灵奖演讲,描述了黑盒后门问题,指出了信任不是绝对的。

    扩展阅读

    许多学校都有针对研究生的数据库阅读列表

    • Berkeley: http://www.eecs.berkeley.edu/GradAffairs/CS/Prelims/db.html

    • Brown: http://www.cs.brown.edu/courses/cs227/papers.html

    • Stanford: http://infolab.stanford.edu/db_pages/infoqual.html

    • Wisconsin: http://www.cs.wisc.edu/sites/default/files/db.reading.pdf

    • Joseph Hellerstein的Berkeley数据库研究生课程阅读列表,比本列表更全面

                                       

                                      

               

    往期精彩:

    本号精华合集(二)

    零基础 SQL 数据库小白,从入门到精通的学习路线与书单

                   

    展开全文
  • 带读 IBM 关系型数据库经典论文

    千次阅读 2019-05-16 07:55:37
    而成本评估,就是考验对计算机内部结构的理解,随机读,顺序读,磁盘转速,字段密度(也就是统计信息)。     COST = PAGE IO + W*(RSI CALLS)     是多么经典的成本计算公式! 当然现在慢慢演化...

    壹  扪心自问

     

     

     一条 SQL 可能在很多人看来是 select , 那是业务;部分人看来,却是一棵棵树,语法树,那是 DBA;少部分人会分析磁盘开销,笛卡尔统计值,时空复杂度,那是内核设计。

     

    扪心自问,你是属于哪一种?

     

     

    贰  关系引擎

     

     

    | 来源:Access Path Selection...( P.Griffiths Selinger )

    | 翻译:Lenis

     

     

    从 1979 年开始,关系数据库引擎的本质结构一直都没有太多变化,所以优化的步骤看上去也就是那么几条军规。 比如从解析出发,经历成本评估,选择最优化,执行。

     

    关于优化,我们能做的也就是从成本评估这里找到突破口。

     

    而成本评估,就是考验对计算机内部结构的理解,随机读,顺序读,磁盘转速,字段密度(也就是统计信息)。 

     

     COST = PAGE IO + W*(RSI CALLS) 

     

     是多么经典的成本计算公式! 当然现在慢慢演化了,更具体的要参考《数据库索引优化与设计》,一本讲评估的好书(我会在星球持续写写这本书的精华部分,也是带读)。Fenng 翻译的《成本优化器》对于研究 Oracle 也是极好的参考手册。碰到执行计划异常,首先考虑是否 statistics(统计信息:包括密度,记录数等)及时更新。在 statistics 及时更新的情况下,通常由于 parameter sniff 需要指定 recompile hint 去改变执行计划。

     

     

    叁  执行计划误区

     

    在分析执行计划优劣的时候,往往大家都会有个误区:执行计划一定是选择最优的那个。 

     

     其实真不是。 

     

    当查询设计到仅仅一张表的时候,评估成本可以很简单。遍历所有可能的执行计划,在其中找到一个最低成本的计划执行便可。 

     

    我们的查询(通常情况下)会超过 2 张表,甚至是 5-6 个表,往往这类查询在 OLAP 系统中经常出现。此时的执行计划组合可能有很多种。遍历这些可能的执行计划,就会耗去很多时间。如果要找到最优的计划,说不定找到这个计划的时间,都比执行该计划要花更多时间。 

     

    所以,查询最优执行计划的时间也是要考虑在优化器的算法中。在尽可能短的时间里,找到还算不错的执行计划便可。而不是每次都把所有可能的执行计划都去评估一下成本,再选择最优的那个。

     

     

    肆  查询路径

     

     

    这篇论文最有意思的地方在于,他讲述的 access path 极为有用。 

     

    access path 的选择大方向有两种,一是全扫描,二是走索引。都知道走索引快,但也不绝对,查询引擎如何影响 access path 的选择,是所有优化中必须要考虑的问题。

     

    本质上,研究 access path 就是在研究每条路径的时间复杂度。因为被 statistics(统计信息)掩盖的笛卡尔积,可能得不到及时更新而产生错误的 access path 导致查询变慢。 

     

     假设: 表 sales 中有 200 万条数据,而 product 字段的 Phone 值比列占到总记录的 80%。那么下列查询是否有必要建立索引呢?

     

    SELECT product,COUNT(ID) AS OrderCnt  FROM sales  GROUP BY product 

     

    如果是这样呢:

     

    SELECT product,SUM(Amount) AS Amt  FROM sales  WHERE product ='Phone' 

     

     

    后一个影响 access plan 的就属 order 了。

     

    order 分为 两种:有序和无序 。

     

    有序的 order 是我们查询时指定的。比如 group by , order by. 我们需要结果按照一定的顺序排列,就使用 order by 指定。这种 Order 我们称其为 interesting order. 

     

    假设,sales 表有这么个查询: 

     

    SELECT product, sales_date FROM sales  WHERE product='Phone' ORDER BY sales_date ASC 

     

    如果有两个索引,分别是: (product), (product,sales_date) 大家猜猜优化器会选择哪个索引? 当我们的查询是无序的时候,两个索引都可以走,但要求排序时,对索引的要求就高了。

     

    access plan 比较复杂的一类莫过于 Join. 

     

     Join 总体上分 3 大类: Nested Loop (嵌套式循环) Merge Join (合并式) Hash Join (哈希式)  

     

    为了保持和业界术语一致,我们(包括任何正规教材)采用的是英文来解释每种概念。有时候用中文,在沟通交流时,会比较费解。  

     

    在 Join 的概念中,搞清楚 Outer Table(Build Table) 和 Inner (Prorbe) Table 非常重要。直接决定表访问的物理路径。

     

    Join(Nested Loops Join) 的实现基本流程: 

     

    1. 从 Outer Table 读取第一条满足条件的记录;

    2. 依据 Join 条件,从 Inner Table 中读取满足条件的记录;

    3. 从 Outer Table 读取第二条满足条件的记录;

    4. 依据 Join 条件,从 Inner Table 中读取满足条件的记录;

    5. 从 Outer Table 依次读取下一条满足条件的记录,重复 2 - 4 的过程,直到所有 Outer Table 中所有满足条件的记录都遍历完毕。查询结束!

       

    决定哪张表作为 Outer Table ,哪张表作为 Inner Table 可以很大程度上改变查询的性能。 假如大表作为 Outer Table, 小表作为 Inner Table, 虽然遍历大表的时间会长,但小表的访问时间会少,带给小表的影响就小;反之,大表作为 Inner Table 就会给查询和更新带来冲突,影响并发。 我们要做的事情,就是将两个表尽可能用最少数据量做 Join.

     

     

     

    伍  殊途同归

     

     

    简单过了下这篇来自 IBM 的经典论文,虽然文章小,但信息量极大。达到可以用下面的脑图来扩展:

     

     

     

     

    在阅读 MSDN 的 SQL Server 文档时,我尝试对一些基础知识点做汇总,整理成这份脑图后,发现与这篇论文所涉及的内容竟然 90% 的相似。目前为止我已经写了有 7-8 万字,藏在我们的星球。有兴趣的朋友,可以一睹为快。当然还剩下左半边部分内容未完成,接下来的 1 - 2 个月预计能完工。

     

    底下这一篇其实就是一篇样例文:

     

    【万字详解】SQL 优化引擎内幕

     

    当然这是干货,特别的干,酒水请自备!

     

     

    想要这篇 IBM 经典论文的,可以后台回复【论文】,本论文原作者开源

     

     

     

     

    猜你喜欢:

     

    回忆当年阿里的一道 SQL 面试题,亿级表合并

    本号精华合集

    关于作者

     

     

     

     

     

     

    展开全文
  • 数据库设计查询执行论文,对理解查询非常有好处
  • 第二章对数据库的设计和SQL语言的使用进行了系统分析,为深入理解数据库应用打下了基础。 第三章学习了具体的开发工具Delphi 6.0,对其数据库组琒QL语言在Delphi中的应用等数据库编程关键技术进行了系统的介绍。 ...
  • 必读的数据库领域论文

    千次阅读 2014-09-02 09:32:26
    Xin)公开了他整理的一份数据库学习资料列表,Hacker News上引起了不少讨论。其中的评述文字也很有价值,简要编译如下。大家对这个列表如有补充,请评论。 基础与算法 The Five-Minute Rule Ten Years ...

    之前林仕鼎曾整理过系统架构领域的学习资料,这几天Spark核心团队成员辛湜(Reynold Xin)公开了他整理的一份数据库学习资料列表,Hacker News上引起了不少讨论。其中的评述文字也很有价值,简要编译如下。大家对这个列表如有补充,请评论。

    基础与算法

    关系数据库

    经典的系统设计

    列式数据库

    列式存储和面向列的查询引擎对于分析型负荷即OLAP至关重要,已有15年历史(最早的MonetDB论文发表于1999年),到现在几乎所有商业数据仓库都有列式引擎了。

    数据并行计算

    • MapReduce: Simplified Data Processing on Large Clusters (2004): MapReduce既是一种编程模型(借鉴自函数式编程中的古老概念),也是Google用于分布式数据密集计算的系统。这个编程模型如此简单而又功能强大,能够满足广泛的编程需求。系统加上模型,是容错而且可扩展的。说现在有一半学术界的人在研究的问题都受到MapReduce的极大影响,应该并不为过。

    • Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (2012): 伯克利Spark集群技术项目背后的学术论文。Spark公开了RDD这种分布式内存抽象,是跨一个集群内存分布的不可变记录集合。RDD可以转换为使用MapReduce式的计算。RDD抽象对有强时间局部性的负荷(比如查询处理和迭代机器学习)效率可以提高几个数量级。Spark是一个很好的例子,说明了将MapReduce编程模型与执行引擎分离的重要性。

    • Shark: SQL and Rich Analytics at Scale (2013): 描述了Shark系统,构建在Spark上的SQL引擎。这篇论文更重要的是讨论了为什么之前的SQL on Hadoop/MapReduce查询引擎都这么慢。

    • Spanner (2012): Spanner是“可扩展、多版本、全球分布和同步复制的数据库”。其中关键是TrueTime API,那个在多个节点之间无需通信而为事件定序。有人猜测TrueTime API与向量钟类似,但每个节点必须存储较少数据。不幸的是,虽然Google说要发表关于TrueTime的论文,但现在还没看到。

    • Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks (2007): Dryad是微软开发的编程模型,支持大规模数据流编程。“MapReduce与Dryad的差异在于,Dryad应用可以指定任意的通信DAG,而不是非要用map/distribute/sort/reduce操作序列。”

    趋势(云计算,仓库规模计算和新硬件)

    • A View of Cloud Computing (2010): 关于云计算的权威论文。从技术角度讨论了云计算(主要指资源的弹性而不是面向消费者的“云”)的经济意义和阻碍因素。这些阻碍因素将影响云中系统的设计决策。

    • The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines: Google的Luiz André Barroso和Urs Hölzle解释了仓库规模技术中数据中心软硬件的基础知识。还有配套的视频(注:HighScalability有相应文章)讨论了在大规模并行系统中减少长尾延迟(long-tail latency)的重要性。其他的关键思想还包括资源的解聚(disaggregation)。GFS/HDFS这样的技术已经用高速网络带宽解聚了硬盘,但是DRAM还没有看到这种趋势,因为那需要低延迟联网。

    • CAP Twelve Years Later: How the "Rules" Have Changed (2012): Eric Brewer提出的CAP定理指出,任何联网的共享数据系统都只能在一致性、可用性和分区容忍性三个属性中保证其中两个。许多NoSQL存储都用此为自己牺牲一致性的设计决策来辩解。此文是Eric Brewer回顾文章,解释了“‘三中取二’的表述是错误的,过度简化了各个属性之间的矛盾关系。”

    杂项

    扩展阅读

    许多学校都有针对研究生的数据库阅读列表

    • Brown: http://www.cs.brown.edu/courses/cs227/papers.html
    • CMU: http://www.cs.cmu.edu/~pavlo/courses/fall2013/reading-list.html
    展开全文
  • 数据库的一些论文的个人整理

    千次阅读 2016-07-12 21:55:13
    数据库架构相关 Architecture of a Database System.... 图灵奖获得者Michael Stonebraker的论文之一,具体介绍了数据库的架构以及相关理论和主流数据库的具体做法。 启发:  对于已经阅读过基础的数据库教材的

    数据库架构相关

    Architecture of a Database System. Joseph M. Hellerstein, Michael Stonebraker and James Hamilton

        图灵奖获得者Michael Stonebraker的论文之一,具体介绍了数据库的架构以及相关理论和主流数据库的具体做法。

    启发:

        对于已经阅读过基础的数据库教材的人来说,这篇论文很适合继续深入学习和理解数据库的各个架构的。论文主要介绍了数据处理模型,并行架构,存储模块设计,事务模型实现,查询和优化器的架构,以及这些架构的共享模块。论文不但包括了书本上的基本的理论,还有一些开源和商用数据库的具体实践,这些对于理解数据库的内核都是大有裨益。另外论文对于每个内容都有大量的引用资料供有兴趣的人继续深入研究。
    不足:
        虽然论文本身属于介绍方向,没有太多专业的名词和实现的深入讨论,但由于涉及范围很多,因此篇幅较长(对于论文的长度来说)。


    Readings in Database Systems Fifth Edition (2015).  Peter Bailis, Joseph M. Hellerstein, and Michael Stonebraker

        非常有名的红宝书,也是出自Michael Stonebraker之手。本书主要集中讨论了目前DBMS的一些主流的发展方向和趋势。
    启发:
        与上面的Architecture of a Database System相比,本书主要集中于介绍DBMS发展方向和趋势,包括了当前非常流行的大数据,NoSQL,数据分析等。同时也会由作者对于该技术的一些主观评价和建议,对于想了解当前发展趋势很有指导作用。同时,论文在不同话题都有一些典型的论文推荐,可供有兴趣者深入研究。
    不足:
        某些地方作者的评价可能会较为主观,但也算是一种参考吧。某些内容由于篇幅关系,只是蜻蜓点水,对于非从业人员来说可能较难理解。

    日志恢复

    ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. C. MOHAN, DON HADERLE, BRUCE LINDSAY, HAMID PIRAHESH, PETER SCHWARZ

        相当经典的日志恢复算法,很多数据库实现的恢复算法都有ARIES的影子。
    启发:
        ARIES的实现相对简单而且高效,支持事务部分回滚,行锁,fuzzy checkpoint。ARIES对于数据页的所有更新都会记录更新日志(undo/redo log),并且利用LSN把数据页和更新日志关联起来,通过正确链接同一事务的所有更新日志,对于嵌套回滚等情况也能正确处理。另外,ARIES不强制checkpoint的时候刷新所有脏页到硬盘等其它特性,总之ARIES整个算法非常灵活,具体实践时可以根据需要进行简单修改定制。
    不足:
        ARIES算法整个部分不算复杂,但论文花费了大量篇幅去介绍和对比之前存在的各种恢复算法,这样可能使第一次阅读的人比较难掌握ARIES的精髓,因此建议先着重理解ARIES算法的整体部分,然后再着眼于其它内容。

    缓存替换算法

    The LRU-K Page Replacement Algorithm for Database Disk Buffering. E. J. O’Neil, P. E. O’Neil, and G. Weikum

    2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. T. Johnson and D. Shasha
    LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance. Song Jiang and Xiaodong Zhang
    ARC: A SELF-TUNING, LOW OVERHEAD REPLACEMENT CACHE. Nimrod Megiddo, Dharmendra S. Modha

        4篇论文分别对应4种不同的缓存替换算法,不单对于数据库的缓存,在其它需要应用缓存的情况(如文件系统的cache)下都有着重要的指导作用。
    启发:
        LRU-K,2Q,LIRS三种算法都基于倒数第二次的访问时间,以此推断块的访问频率,从而替换出访问频率低的块。ARC是采用自适应算法去根据不同的workload调整cache,对比之前三种需要配置参数才能发挥最佳性能的算法,ARC不需要配置参数也能发挥出最佳的性能。另外这4种算法都是scan-resistant,也就是可以避免扫描污染cache。
    不足:
        前三种模型都需要经过实际测试配置最佳参数,ARC模型过于理想化,没有讨论诸如内存被固定不能刷新的时候如何处理,因此应用需要根据实际情况进行调整。

    数据存储相关

    The Log-Structured Merge-Tree (LSM-Tree). Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil

    LSM树是disk-based的数据结构,对于Insert能够提供比B树更低IO开销。顺带一提,HBase的底层数据结构就是基于LSM树。
    启发:
        在刷新数据页时,会导致大量的随机IO,这些随机IO主要开销在于硬盘机械臂转动(也就是寻址)。利用内存构建B树作为写缓存,加上利用延迟和批量索引的修改进行merge sort,再刷新到硬盘上,能大大减少IO写入硬盘寻址带来的开销。
    不足:
        对于查找来说,在某些情况下会造成效率下降,因此LSM树只对于写入大大超过查找的情况才更加有效。
        由于需要利用内存建立B树进行插入缓存,因此一般需要较大的内存开销。
        对于目前流行市面的SSD不一定有较大的性能提升。
        论文对于LSM树的开销建立了相关的数据模型,并且进行了较为详细的理论证明,比较难看懂。


    The Design and Implementation of a Log-Structured File System. Mendel Rosenblum, John K. Ousterhout

    Log-Structed是一种把随机IO转换为顺序IO的存储管理方法。
    启发:
        论文提出了Log-structed的存储管理方法,该方法把所有的修改作为log,然后首先保存到内存中,接着批量顺序写到硬盘上,这样乱序IO转变顺序IO输,节省硬盘寻址时间,提高了硬盘传输利用率。同时为了更好管理硬盘上的大空间块,把多个log划分为一个segment,并且利用基于开销(cost-based)的清理策略对大空间块进行压缩和回收。论文在此理论上实现了Sprite LFS的文件系统,并且传输利用率高达70%超越了Unix的5-10%。
        对于数据库来说,可以参考log-structed方法,把原来刷新B树的数据页的随机写转变为顺序写。
    不足:
        论文主要是针对文件系统的实现,要求对于所有的修改都要转为log输出到硬盘上,因此可能会增加输出的字节数。同样,对于SSD来说,性能提升可能不会有显著的变化。


    C-Store: A Column-oriented DBMS. Mike Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, Stan Zdonik

    论文主要介绍Column-store,也就是列式存储的实现细节。同样也是Mike Stonebraker的论文。虽然论文只是实现了少部分特性,但不可否认的是里面的观点都很有新颖的见解,可以有很多启发。
    启发:
        论文以一个实现了Column store的存储引擎,C-Store,作为范例,介绍了Column store的一些实现细节。C-Store主要是针对数据仓库类型的查询(在大量的数据执行聚集的即席查询)以及OLTP类型的事务进行特殊的列式存储,从而达到了高效率的读和写。另外论文也提到了C-Store用于分布式时如何达到K-sfaety的高可用性以及避免两阶段提交(2PC)的事务特性。
        具体特性包括利用经过优化写入性能的Writeable Store(hot data放内存)和优化读性能的Read-optimized Store两个存储模块;根据查询去冗余存储表的不同列的不同顺序的数据作为投影,从而使查询可以使用最佳投影;使用多种编码方式压缩列数据;面向列存储的查询优化器和执行器;通过存储重叠列作为投影,提供了分布式高可用性;snapshot isolation可以避免2PC和查询时的锁。
    不足:
        论文提出的观点虽然新颖,但实现难度较大,在做性能对比的C-Store也只是进行了读性能对比,Writeable Store则甚至还没能达到测试要求,并且也只能运行在单机上。很多特性是否和论文提到那样有效还有待深入验证和讨论。

        除此之外,读优化需要按照查询的类型进行人工选择列来合成投影,也就是需要人工介入优化。

    并发控制

    Efficient Locking for Concurrent Operations on B-Trees. PHILIP L. LEHMAN,S. BING YAO

    介绍了一种并发操作B树的算法。
    启发:
        利用了B+树的变种Blink树,实现了B树的简便高效的查找和插入的并发操作。
        Blink树, 是在B+树的每个结点添加一个link指针指向右边兄弟。对于插入,利用Blink树的link指针,在任何时刻(包括split)每个进程(线程)最多获取三个结点的锁。对于查找,则不需要获取任何结点的锁。
        由于限制每个进程(线程)获取的锁,因此会大大提高了并发度。
    不足:
        对于删除,论文中并没有提供高效的并发操作。
        具体做法是,不删除非叶子结点的key,只删除叶子结点的数据,并且不会执行合并操作。这是考虑到现实应用中删除属于比较少见的操作。对于删除过多数据,导致叶子结点的使用率相当低的时候,可以采用锁住整棵树,然后执行整理操作。


    展开全文
  • Hbase数据库简单理解

    2016-03-21 21:29:36
    HBase是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的Google论文"Bigtable:一个结构化数据的分布式存储系统"。就像Bigtable利用了Google文件系统(File System)所提供的分布式数据存储一样,...
  • 一套完整的VC 课程设计:药品信息管理系统 数据库 论文,利用MFC框架编写一个简单的WinForm数据库系统。通过本设计可以加深理解使用面向对象程序设计思想开发一个系统的方法,提高分析问题、解决问题和实际动手的...
  • 谷歌AVA数据库的1705.08421论文

    千次阅读 2017-10-30 11:24:38
    目的是理解AVA数据库的做成过程。翻译了谷歌AVA数据库的1705.08421论文。 翻译初版,部分还需要斟酌,之后在改善。 内容参见如下。 概要 本论文提出了一个视频数据集,(时空局部化)原子视觉动作(Atomic ...
  • 数据库语义缓存能够让数据库理解”查询语义,可以为数据库的动态调节提供信息。而查询缓存是语义缓存的一种,在 SQL解析与查询执行之间,通过研究查询缓存的自主管理来提高数据库的查询性能。首先介绍了数据库常用...
  • 正如一阶逻辑已被证明是表达和理解关系数据库模型的基础语义的有用形式主义一样,内涵逻辑也被表示为一种类似的形式主义,用于表达和理解历史数据库中涉及的时间语义。关系模型,扩展到包括历史关系,是根据逻辑IL...
  • 工程师通常将NoSQL数据库理解为“不仅是SQL数据库”,还是“没有SQL”,它是最广泛使用的关系数据库的替代方案。 就像给定的名称一样,它是SQL的替代品,其使用方式是将SQL共存。 关系数据库管理系统(RDBMS)是...
  • 数据库开题报告

    2013-03-26 11:50:11
    关于数据库的开题报告 方便大家对于有关数据库论文的一些理解
  • 论文阅读——数据库相关

    千次阅读 2012-05-14 20:55:45
    举个例子可以帮助理解: 我这有一台超大功率的面粉加工机,前者相当于 把所有农户袋装的麦子收集起来用卡车一次送往加工厂 后者相当于农户排好队用同样的卡车一人一人的往加工厂送麦子 麦子加工5分钟完成,但是每个...
  • 关于数据库的练习题,关系代数

    千次阅读 2020-06-30 01:49:17
    基本操作理解 数据库作业二 图书馆管理系统中有4个关系模式: 学生(学号,姓名) 书架(书架编号,书架名,位置) 书籍(书籍编号,书名,书架号,ISBN,版本号) 借阅(学号,书籍编号,借阅时间,还书时间) 对...
  • 关于数据库系统的学习

    千次阅读 2009-03-20 22:56:00
    数据库系统,从本科就在学习,到了硕士阶段又学了一次,可是自己也不敢说真的理解清楚数据库系统。为了参加数据库的开发比 赛,又重新拿起那本经典的教材《 Database System Concepts 》反复研究,逐步体会到了...
  • 使用XML实现动物疾病关系数据库的语义映射,周全,关金金,关系数据库是现今农业信息存储的主要形式;随着web技术的发展,信息检索越来越复杂,关系数据库需要更好被Web理解,更多需要语义上
  • 关系数据库并非旨在理解语言的细微差别,因此必须提出为什么我们必须处理细微差别的问题。 本文正在寻找一种将自然语言查询转换为能够用于搜索关系数据库的结构化查询语言(SQL)的替代解决方案。 该过程使用自然...
  • 该内容为fisherface的matlab代码,绝对可以运行,实验的数据库为ORL人脸数据库,并且在代码中很多中文注释,便于理解,为了大家方便,在压缩包中还放了fisherface的原始原始论文和PCA算法的原始论文。希望这些资料对...
  • PingCAP 团队的论文《TiDB: A Raft-based HTAP Database》入选 VLDB 2020,这是对 TiDB 数据库阶段性成果的肯定,非常为国内数据库技术的快速发展而感到高兴。由于关于 TiDB 数据库在高可用、水平扩展和 ACID 事务的...
  • 部门管理: 美术馆管理: 用户信息管理: 美术馆预约管理: 预约审批管理: 论文: 好了、就介绍到这了、适合学生和毕设参考使用、有需要的同学可以Q我要代码(WX:andywebjava)、作者不易、不开源哈 望理解哈哈哈...
  • 一课程设计目的二系统设计数据库逻辑结构设计系统功能模块图课程设计总结...理解和掌握数据库设计和开发的思路和方法并更好的理解和消化课本所学的知识为今后的实际应用打下良好的基础系统设计数据库逻辑结构设计系统...
  • 数据库管理系统已被广泛用于存储和检索数据。 但是,由于自然语言查询接口到关系数据库的分析引起了研究界的极大兴趣,因此数据库通常很难访问数据,因为它们的接口在与用户的协作中很严格。 这可以称为结构化免费...
  • JSP SH论文答辩管理系统是一套完善的web设计系统,对理解JSP java编程开发语言有帮助,(SH框架)系统具有完整的源代码和数据库,系统主要采用B/S模式开发。 二、功能介绍 (1)权限管理:对权限信息进行添加、删除、...
  • 图像理解与机器视觉论文.pdf
  • 关于图形数据库的见解 最近在网上阅读了相关图形数据库的知识,深有体会,此外本人想把所理解的知识分享给大家,有错误点请指出,共同进步。 图形数据库(Gragh database):起源于欧拉的七桥问题,基于图论所设计...
  • 基于Jsp的图书馆管理系统软件设计源码+数据库+sql+毕业论文文档资料: 16+MySQL booksManager data 基于Jsp图书馆管理系统毕业论文.doc 安装包 毕业设计(论文)开题报告.doc 毕业设计(论文)指导记录表.doc 毕业...
  • 视频理解论文杂读

    千次阅读 2018-05-06 16:11:47
    这篇论文个人很难理解作者对于图1的解释,但是如果按照non-local 或者compact non-local去理解,就会比较通顺。 按照non-local的思路,作者的计算顺序是(C1*THW)*(THW*C2) * (C2*THW)。当我们把后面的先乘,那么...
  • 尽管关系模型在数据操作和完整性支持... 该方法完全在关系模型中阐明,缺乏可靠的理论基础-这种缺乏被认为吸引了从业者-在过去的五年中,已在一些中小型应用程序中对其进行了测试,事实证明该方法是有用且可理解的。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,033
精华内容 18,813
关键字:

关于数据库的理解的论文