时间：2022-11-06 10:30:01 | 来源：信息时代
时间：2022-11-06 10:30:01 来源：信息时代
嵌入式数据库查询 : 采用自适应的查询处理技术对内存数据的查询处理。传统的查询处理技术充分地利用大量的主存来存储一些临时数据结构(如哈希表)和中间结果。当主存不能满足数据存储需求时,可采用一些复杂的算法利用磁盘上的空间来避免内存溢出。在嵌入式数据库环境中,内存非常有限,向稳定内存写操作很慢,而临时的实体化也不允许。通常也很难提前估计出内存需求,选择小了将导致内存溢出,选择大了又会减少有限的内存空间; 其次,一些复杂的算法违背了代码精简和压缩的原则,对于嵌入式数据库不再适用。
考虑到以上原因,嵌入式数据库系统通常采用自适应的查询处理技术。整个数据都存储在内存中,查询处理优化的主要目的是减少从内存中读数据的次数。
一个基本的查询执行通常分为两个步骤: 查询优化器首先产生可选的查询执行计划(QEP),然后查询引擎通过一种执行模型,利用关系操作符库来执行QEP。对于不同的查询执行计划有不同的查询树形式。在左深树(left-deep trees)中,操作符顺序执行,每个中间结果都要进行实体化。而右深树(right-deep trees)是在流水线中执行操作符,避免了实体化中间结果,但仍需要在内存中实体化所有的左关系。Bushy树可以减少处理中间结果大小和内存消耗。
查询处理需要一个最优的查询执行计划,为了减少实体化操作,左深树和Bushy树被排除,而选择右深树和极右深树来表示查询,具体采用哪个依赖于存储中间结果而能使用的内存。查询优化器通常是内存标识的。
由于不能保证每个操作符都能得到整个内存,内存必须在全部操作符之间选择分配。Arvind等人提出一种基于代价函数来给操作符分配内存的方法。
对于没有索引的连接操作,可以使用三种连接方法:
(1)嵌套循环连接:当内存较少时,这是一个理想的选择,它的优点是不需要额外的数据结构。
(2)排序合并连接:排序操作需要占用一定的内存空间。这种方法在最坏的情况下执行得较好。
(3)哈希连接:需要在主存中创建哈希表,在内存不限制的情况下,哈希连接的速度是最快的,但选择一个好的哈希函数是关键。
对于有索引的连接操作,可是采用以下连接操作:
(1)索引嵌套循环连接:带索引的那个关系作为循环连接的内关系。
(2)排序合并连接:如果索引在连接属性上,那么不需要进行排序操作。
对于连接索引,遍历索引和相关的指针将产生用于连接的候选元组。
选择、投影和排序可以直接进行,而去重、聚集、集合取合、取差操作能够通过在关系上进行排序和构建哈希索引来计算得到。聚集、排序和去重操作一般是在物化结果的基础上执行,然而可以通过在查询计划树的叶结点上指定元组到达顺序,来对这些聚集操作使用流水线操作。
在线咨询
