袁锋[1]2004年在《数据流系统中查询处理机制的研究与实现》文中指出近年来,数据库的理论与应用得到了极大的发展,在传统的数据库理论基础之上发展出了很多分支,数据流即是其中新发展起来的一个重要的研究方向。作为一种新兴的应用形式,数据流具有非常广阔的应用空间,从而也得到了人们越来越多的关注。 在数掘流中数据是以一种动态的流动的形式存在,而不是像传统关系数据库那样保存在磁盘中的静态数据,它的提出主要源于传感器网络和网络点击流等应用形式,这些特殊的数据形式是以处理静态数据为主的传统数据库难于处理的。数据流模型的主要特点是无界性、随机性和不可预知性,而数据流的应用也往往要求具有一定的实时性。 在这样的背景下,在传统数据库技术的基础之上,我们开始对数据流进行比较深入和细致的研究。我们根据数据流的特点提出了一种数据流查询处理的实现方法,这种方法主要基于我们所提出的分级窗口策略,在这种策略之上,我们设计并实现了数据流原型系统RealStream。RealStream的主要功能是在多流多查询环境下基本查询的处理,同时支持查询的优化与多种窗口结构,并在分级窗口的基础之上实现了数据共享。 本文首先介绍了当前数据流理论和数据流系统的研究概况,然后说明了数据流上查询处理功能模块在实时数据流系统中的位置及其作用;在分析了数据流上窗口操作实现过程中可能出现的各种问题之后,我们针对这些问题提出了一种分级窗口的维护策略,并进一步介绍了分级窗口的特点、适用范围和维护方式,在原型系统RealStream中也实现了这种策略;然后对数据流上常见的几种窗口结构进行了分析,并给出了各种类型窗口的具体实现方法;最后在以分级窗口为底层架构的基础之上,对整个查询处理中的各个功能模块进行理论分析与具体实现的介绍。
王力[2]2007年在《基于基因算法的大型关系数据库查询优化技术研究》文中认为随着数据库技术的迅速发展和信息系统的广泛应用,企业管理效率提高的同时也促成了海量数据的积累,一些大规模的系统,如证券、银行和人口统计等系统的数据量甚至超过了TB级。从大多数系统的应用实例来看,查询操作在各种数据库操作中所占比重最大,但在进行访问查询时,会遇到系统响应时间过长,占用系统资源过多等问题,查询速度已成为影响系统性能的重要瓶颈。常规算法在处理查询优化问题时都有着自身无法克服的局限性。例如:穷尽搜索算法所优化的关系数目不能太多,否则效率会急剧下降;启发式算法不一定得到最优解;局部随机搜索算法容易陷入局部最优化的陷阱中;一般的全局搜索算法又太过于依赖“代价函数分布曲面”。因此,本文在大型关系数据库查询优化中引入基因算法,来更好的解决大型数据库的查询优化问题。论文所做的工作如下:①分析了目前国内外针对关系数据库查询优化的研究成果,并对查询优化必要性进行了论证。②重点研究了查询优化器的结构、模块功能和工作原理;重点分析了查询重写和计划优化阶段的作用。③研究了多连接查询优化的原理和执行引擎的相关理论,分析了常见的搜索算法,并对它们的特点进行了总结。④研究了基因算法理论及其关键技术,并对变异算子进行改进,提出使用两种变异算子,克服了在树型编码中交叉算子生成新个体能力不足的问题,最后把基因算法和其它搜索算法进行比较。⑤根据基因算法的特点,设计出一个基于基因算法的多连接查询优化模型,并对该模型进行分析测试。结果证明使用基因算法的查询效率比使用其它普通算法的查询效率有明显的提高。
韩梅[3]2004年在《数据库管理系统查询优化技术研究》文中提出当今的信息技术时代，数据库已经成为管理信息和挖掘信息的巨大潜能的基本和必需的工具。随着时间的推移，数据库中的数据量日益增加，因而数据库的最重要特征之一在于把其性能维持在可接受的水平上，实现这一目的的主要机制就是数据库查询优化器。 如果没有设计良好的查询优化器，即使是小型的数据库也会表现出非常明显的性能低下。目前的众多的商用数据库都不同程度的实现了查询优化功能。由于实际优化器的内部结构所涉及的功能和过程异常复杂，通常的商业数据库的查询优化器估计至少需要50人年的开发量。本文主要研究了关系数据库中的查询优化技术，对比了现有的各种技术的优劣，提出了基于统计的、适应于SECBase数据库的查询优化器模型，并且针对其中的多连接查询的效率问题，建立了多连接查询优化的算法模型，引入了组合优化问题的遗传算法。此外，还对实现查询优化的一些关键问题进行了具体的讨论。通过实验证明，提出的优化器模型是可行的，其中采用的遗传算法对处理多连接查询有着显着的优越性。
兰超[4]2016年在《面向图数据的Top-k检索算法研究》文中进行了进一步梳理近年来随着社交网络、知识图谱等应用的飞速发展,图数据大量出现在学术界和工业界,如何有效管理图数据并从中挖掘有价值的信息已经成为当前数据管理领域的研究热点。其中面向图数据的Top-k检索问题广泛存在于在各类应用中,旨在从图中找出与查询最相关的k个匹配结果,是图数据管理的一个重要研究问题。针对当前图数据的数据规模大、节点和边的种类多、内容动态变化等特点,本研究重点关注面向图数据的Top-k检索中叁个关键问题:分布式环境的Top-k子图检索、多数据源的Top-k子图检索和动态数据的持续相关Top-k检索,归纳总结已有工作的优点和不足,提出相应改进算法。本研究的创新点主要有:·提出基于星形查询拆分的分布式Top-k子图检索算法。算法基于星形子图拆分策略,包含对原始查询进行子查询拆分、检索子查询匹配结果、合并子查询匹配结果叁个主要步骤。本研究基于算法停止条件的相关特点对算法子查询执行和合并子查询匹配结果过程进行了叁方面的优化,进一步降低了算法的跨节点数据传输开销。实验结果表明:算法具有很好的可扩展性,优化后算法执行时间比已有方法平均低30%-40%。·提出面向多数据源Top-k子图检索的排序连接算法。算法包含构造来自不同数据源的匹配结果列表、连接结果列表并计算所得完整结果的分数和判断算法停止条件是否满足叁个主要步骤。针对已有方法计算尚未访问结果得分上界松弛的问题,本研究提出优化的匹配结果列表排序函数和基于最小下降分数的结果列表读取策略,并从理论上证明了排序函数最优参数配置应该满足的条件,以及优化读取策略产生的结果访问顺序最优。实验结果表明:本研究提出的排序连接算法比已有工作开销低50%到70%。·提出基于动态区间窗口划分的持续相关Top-k检索算法。算法基于从时间维度对问题空间进行单位时间区间划分的思想,在每个区间执行Top-k检索,再归并计算持续相关Top-k结果。针对单位区间划分可扩展性差的问题,本研究进一步提出基于动态区间窗口划分的算法,检索过程中动态维护时间窗口,避免不必要区间划分,减少了子问题的数量,同时合并不同区间重复的计算子过程,提升了算法的空间和时间效率。实验结果表明:基于动态区间窗口划分算法在消耗更少内存的情况下,执行时间比已有方法低50%以上。
王雷[5]2017年在《面向分布式数据库的连接查询优化》文中研究指明互联网环境下,随着数据规模的不断增大,查询请求的高并发,使得数据库系统的存储与计算的横向扩展能力显得非常重要。基于分布式存储的数据库,以其良好的可扩展性受到了工业界与学术界的广泛关注,本文在分布式存储架构下对连接查询进行研究,总结影响连接查询效率的叁大因素:数据的本地提取、数据的网络传输以及连接算法的执行效率。针对这叁个因素,在分布式存储架构的基础上,提出了分布式数据库连接查询优化框架,有效地降低了查询响应时间,提升了用户体验。本文工作的主要贡献如下:1.提出了一个有效的分布式数据库连接查询优化框架。在分布式存储的系统架构下,针对影响连接查询效率的主要因素,提出了分布式数据库连接查询优化框架,从并行度、连接算子以及半连接操作叁方面对连接查询进行优化,并在开源分布式数据库OceanBase上实现了连接查询优化的框架。2.在开源分布式数据库OceanBase上,设计并实现了并行的嵌套循环连接、哈希连接以及半连接操作。一方面对数据进行并行的请求与处理,加快数据的本地提取,使用半连接操作有效地减少了数据的网络传输;另一方面使连接算子能够充分利用系统的计算资源,采用并行计算技术快速响应连接操作,显着地提高了连接效率。3.通过大量实验,验证了分布式连接查询优化框架的可行性与效率。利用开源数据库性能评测工具Sysbench,开展了充足的实验,实验结果表明:本文提出的连接查询优化框架能有效的降低响应时间,提升查询效率。本文提出的分布式连接查询优化框架在分布式数据库OceanBase上的测试结果表明:从并行度、连接算子以及半连接操作叁方面出发对连接查询进行优化,可以有效地减少连接查询的响应时间,并且提升连接查询效率。同时,本文提出的分布式连接查询优化框架对其他基于分布式存储的数据库有一定的借鉴意义,也为将来的连接查询优化工作提供了参考。
顾荣[6]2016年在《大数据处理技术与系统研究》文中研究指明随着计算机和信息技术的迅猛发展和普及应用,行业数据爆炸性增长,全球已经进入了“大数据”时代。大数据已引起全球业界、学术界和各国政府的高度关注。大数据已经渗透到各行各业,巨大的数据资源已成为国家和企业的战略资源。大数据给全球带来了重大的发展机遇与挑战。一方面,大规模数据资源蕴涵着巨大的商业价值和社会价值,有效地管理和利用这些数据、挖掘数据的深度价值,对国家治理、社会管理、企业决策和个人生活将带来巨大的影响。另一方面,大数据带来新的发展机遇的同时,也带来很多技术挑战。格式多样、形态复杂、规模庞大的行业大数据给传统的计算技术带来了巨大挑战,传统的信息处理与计算技术已难以有效地应对大数据的处理。因此,需要从计算技术的多个层面出发,采用新的技术方法,才能提供有效的大数据处理技术手段和方法。大规模数据的有效处理面临数据的存储、计算和分析等几个层面上的主要技术困难。首先,动辄达到数百TB级甚至PB级规模的行业大数据,远远超出了传统数据库系统的处理能力。因此,需要研究提供有效的分布式大数据存储管理技术方法与系统。同时,大规模数据处理是一个非常耗时的计算过程,使得传统的单机系统远远无法满足大数据对计算性能的要求。因此,需要研究提供高效的并行化大数据计算技术方法与系统。进一步,大数据的有效分析利用通常涉及到对大规模数据的分析挖掘,而巨大的数据量使得传统的单机机器学习和数据挖掘算法都难以在可接受时间内完成计算,导致算法失效。因此,需要研究提供有效的并行化大数据机器学习与分析挖掘算法和大数据机器学习系统。大数据处理不同于传统的计算与信息处理技术的另一个重要特点是,它是一项涉及计算与信息处理技术众多方面的综合性技术,具有显着的技术综合性和交叉性特征,以任何一个单一和隔离的技术层面和技术方法,都难以有效完成大数据的处理。因此,大数据的有效处理需要将存储、计算与分析层面的技术紧密结合、交叉综合,以形成一种完整的大数据处理技术栈,构成一体化的大数据处理系统平台。基于以上问题背景,本文对大数据处理的多个技术层面进行了深入研究,在分布式存储技术与系统、并行化计算技术与系统、以及大数据并行化机器学习与数据分析算法与系统方面,进行了一系列的研究。具体而言,本文工作包括以下主要技术内容和贡献：(1)大数据分布式存储管理技术与系统研究。主要开展了叁方面的研究工作。1)为了提升大数据分布式存储系统的性能,研究实现了分层式大数据存储系统缓存调度策略与性能优化方法,可显着提高分布式存储系统数据访问的性能；2)研究实现了一种通用的分布式文件系统性能测试方法与系统工具,可以用于各种分布式文件系统的性能评估和研究优化,或者用于大数据应用系统设计时选择合适的存储系统和参数优化配置；3)研究设计了分布式层次化大规模RDF语义数据存储技术与管理系统,可有效地存储管理大规模RDF语义数据。(2)主流大数据并行计算系统性能优化研究。主要研究了两方面的工作。1)Hadoop MapReduce作业执行调度优化技术,研究实现了优化的MapReduce作业与任务调度处理方法以及高效的任务执行状态通信方法,实现了一个与标准Hadoop完全兼容的优化版本Hadoop; 2) Spark RDD数据堆外(Off Heap)内存存储机制,针对Spark在处理大规模数据性能受到JVM垃圾回收严重影响的问题,研究实现了一种基于分布式堆外内存存储的Spark RDD数据存储机制。(3)大数据并行化机器学习与数据分析方法与算法研究。主要研究实现了多个应用领域的复杂大数据机器学习与数据分析并行化算法,包括：1)针对数据挖掘领域中大规模神经网络训练性能低下的问题,研究实现了一个定制式大规模神经网络训练并行化算法与计算平台cNeural;2)针对在搜索引擎和信息检索领域重要的排序学习(Learning To Rank)算法GBRT (Gradient Boosting Regression Tree)训练耗时较长的问题,研究提出了基于K-Means直方图近似算法优化的加速方法及其并行化算法；3)针对语义网推理领域中RDFS和OWL推理规则集在大规模语义数据上推理耗时过长的问题,研究实现了基于Spark并行计算平台的高效并行化推理方法与系统。(4)统一大数据机器学习与数据分析编程模型与系统平台研究。针对大数据分析处理时面临的系统平台可编程性和易用性问题、以及大数据分析处理时的计算性能问题,研究提出了一种基于矩阵模型的统一大数据机器学习与数据分析编程模型与框架,并进一步设计实现了一个跨平台统一大数据机器学习与数据分析系统平台Octopus(大章鱼),该系统底层可与Hadoop、Spark、MPI、Flink等主流大数据平台集成,实现底层平台对上层数据分析程序员的透明性,而上层可使用R/Python编程语言与编程开发环境,基于矩阵模型,方便高效地完成大数据分析算法和应用的编程和计算。通过对上述大数据分布式存储、并行化计算、以及大数据分析层面关键技术方法与系统的研究,本文取得了一系列研究工作成果,这些成果可作为重要支撑技术与系统,有效运用于构建一体化的大数据处理系统平台。本文部分成果已经被成功运用于工业界的开源或者商业化大数据处理系统或应用产品中。
陈一栋[7]2008年在《分布式数据库查询优化算法研究与实现》文中指出分布式数据库系统是计算机网络与数据库系统的有机结合。由于涉及大量数据在网络上的传输,因此查询处理和优化就成为分布式数据库提高查询性能的关键因素。查询处理和优化就是通过合理的算法尽量减少通信的信息量,从而提高查询的响应时间性能以及减少系统开销。本文所做的主要工作如下:(1)详细分析了分布式查询优化的基本技术、分布式查询的分类和层次结构以及分布式查询优化的各种策略和算法。(2)通过对普通的半连接查询优化算法的研究,针对普通半连接顺序执行半连接的不足,提出了一种改进的半连接查询优化算法。该算法由建立半连接图和获得半连接执行策略两个步骤实现。实验证明,该查询优化算法明显地减少了中间结果数据量,有效地降低了网络通信总代价,提高了优化效益。(3)针对分布式数据库复杂的多连接查询问题,本文在研究了粒子群优化算法的基础上,提出了一种多连接粒子群优化算法MJPSO(Multi-Join Particle Swarm Optimization),并给出了该算法的实现。实验证明,该算法适合应用于复杂的多连接查询优化问题,能够更快速地从关系语法树中搜索和选择优化方案。
郭丽英[8]2008年在《数据库中查询重写及基于遗传算法的多连接查询优化研究》文中研究表明查询优化是数据库管理系统设计和实现所采用的一项重要技术,也是影响数据库系统性能的一个重要因素,当前所有商用数据库都成功采用了这项技术。关系数据库系统和非过程化的SQL语言能够取得巨大成功,主要得益于查询优化技术的发展。对于-个复杂的查询,寻找一个优化的执行策略是数据库系统开发成功的关键所在,此项研究目前在数据库领域仍然属于NP问题。在查询执行的过程中,低效的SQL查询语句、概貌信息的匮乏、连接顺序的错误选择都是直接导致查询效率低下的原因。数据库的查询优化是在数据字典的基础上,提取有益的概貌信息、建立数据库概貌模型、对低效的查询语句进行查询重写、为多表连接查询选择最优的连接操作顺序等。本文针对用户对查询效率要求较高的特点,对实现查询优化的一些关键问题做了具体讨论。其中包括数据库概貌模型的建立与管理；SQL查询语句的重写等。本文针对查询优化中的多连接查询的效率问题,建立了多连接查询优化的算法模型,引入了组合优化问题的遗传算法。此外,还对实现查询优化的一些关键问题进行了具体的讨论。通过实验证明,提出的优化器模型是可行的,其中采用的遗传算法对处理多连接查询有着显着的优越性。
玄萍[9]2004年在《并行数据库查询优化的遗传算法》文中进行了进一步梳理查询优化是并行数据库系统的核心技术。目前，查询优化的研究主要围绕着具有多个连接操作的复杂关系数据库查询的优化问题进行。近十几年来，人们对于并行数据库中的多连接查询优化问题，已经进行了广泛的研究。然而，目前在基于机群并行计算环境的多连接查询的优化算法的研究工作还很少。本文重点研究了基于机群并行数据库中关系的存储分布、多连接查询优化和查询处理等关键技术。 机群并行计算机系统是并行处理技术的一个重要分支，是进行高性能计算的一个有效途径，必将主宰并行计算技术的发展。本文在借鉴了机群并行数据库系统特点的基础上，提出了关系分布算法、多连接查询优化算法和查询处理方法。 机群系统中，网络通信的带宽一直是系统的瓶颈，处理机间的数据交换会大大的增加连接操作执行的时间开销。本文提出的关系分布算法，在选择关系的分布属性、分布方式和处理机集合时，充分考虑了机群系统中引起数据重分布的因素，减少了额外的通信开销；同时兼顾了并行系统中的算子内并行、算子间并行和流水线并行等多种并行，便于开发机群系统的并行性。 多连接查询的优化问题是并行查询优化的关键问题之一。本文算法针对机群并行数据库系统的特点，研究了资源分配在查询执行代价估算中的作用和方法，提高了查询计划代价计算的精度，保证了优化结果的质量。与此同时，为了节省网络通信的开销，算法的代价模型计算将网络的通信代价考虑在内，充分利用了查询中各关系的物理存储信息，减小了不必要的通信开销。 中文摘要百亩亩亩..亩困.口百.百亩口口 在并行查询处理方面，本文基于分布式组件对象模型，实现了并行数据库查询处理的数据重分布算法、连接算法和流水线执行算法等查询处理算法以及并行查询计划的调度执行算法，开发了并行数据库的叁种并行，提高了多连接查询的执行效率。 在实验部分，通过对荃于最小中间结果的贪心算法、基于右深树的启发式算法和本文提出的算法的模拟实验，对比了叁种算法的性能。实验结果表明，算法较大的提高了机群系统中多连接查询优化的效率，是解决多连接查询优化的有效途径，对提高并行数据库的性能起到重要作用。
曾祥楷[10]2016年在《基于内存的分布式列式数据库查询优化》文中提出随着人们对数据查询、分析的要求越来越高,传统的基于磁盘的关系型数据库已不能完全满足要求,而内存因为其远高于磁盘的访问速度,能极大降低数据的存取延迟而越来越多的被作为数据库的存储介质。而基于列优先的存储方式因为有更高的压缩率和在数据查询任务中更小的中间数据而被广泛应用在内存数据库中。本文针对内存存储与磁盘存储的不同,以及列优先存储和行优先存储的不同,设计了一套基于内存的分布式环境下的列式数据库上的查询优化方法,其中包括:1、将传统关系型数据库中的基于规则的查询优化与列式存储模式相结合,采用选择下推、条件化简等一系列操作对逻辑查询树进行有针对性的变形,使之具有更少的算子,并且在分布式环境下具有更小的数据传输量。2、对涉及到多表join的查询,结合实际应用环境,采用非随机的分层动态规划算法计算最优的连接顺序,并在实现中提供良好的选择策略实现接口,使之在不同的应用环境下可以使用不同的算法提供更适合的join路径选择方案。3、在查询中结合数据片的存储位置、网络开销、节点负载等信息,综合计算预估多种查询方案的代价,分别采用贪心算法和遗传算法两种算法优化执行计划在分布式集群上的执行策略,提高查询的实时响应能力。通过在已有的内存数据库系统GoldFish上实现该查询优化模块,并对比spark-sql等已有开源分布式数据库系统,我们发现带有查询优化模块的GoldFish系统在内存使用率,查询延迟等性能指标上均有很好的表现。
参考文献：
[1]. 数据流系统中查询处理机制的研究与实现[D]. 袁锋. 东北大学. 2004
[2]. 基于基因算法的大型关系数据库查询优化技术研究[D]. 王力. 重庆大学. 2007
[3]. 数据库管理系统查询优化技术研究[D]. 韩梅. 解放军信息工程大学. 2004
[4]. 面向图数据的Top-k检索算法研究[D]. 兰超. 清华大学. 2016
[5]. 面向分布式数据库的连接查询优化[D]. 王雷. 华东师范大学. 2017
[6]. 大数据处理技术与系统研究[D]. 顾荣. 南京大学. 2016
[7]. 分布式数据库查询优化算法研究与实现[D]. 陈一栋. 长沙理工大学. 2008
[8]. 数据库中查询重写及基于遗传算法的多连接查询优化研究[D]. 郭丽英. 东北大学. 2008
[9]. 并行数据库查询优化的遗传算法[D]. 玄萍. 黑龙江大学. 2004
[10]. 基于内存的分布式列式数据库查询优化[D]. 曾祥楷. 电子科技大学. 2016
标签：计算机软件及计算机应用论文; 数据库系统的特点论文; 大数据论文; 分布式存储论文; 分布式数据库系统论文; 分布式算法论文; 分布式架构论文; 并行处理论文; 分布式技术论文; 数据库性能论文; 优化策略论文; 数据检索论文; 算法论文; 数据库论文;