包含标签 论文 的文章

SQL Server Column Store Indexes

2023年5月24日
| 数据库
SQL Server 11代 Denali，在行存系统上增加了列存和索引结构，这些改动并不是重新来一套，而是基于现有技术的改进，如对行做了分片segment，每个 row segment 再根据 column 进一步细分为 column segment；column segment本身是现有的 blob存储，同时还利用了压缩技术，基于 column segment 又开发出了 segment directory，这个 directory包含了一些元信息如行数量、size、多少数据被编码了、min和max等，这些改动之后，还可以跟现有的lock、log、recovery、patition、mirror、replication完全兼容整合；之后查询引擎部分也会做一些改动来兼容行、列数据，这里使用了多核、bitmap filter、算子间的内存共享、SIMD等进一步优化，根据代价模型评估，选择合适的索引，测试TPC-DS时，前面大部分数据都是批的方式处理的，而且做了并行化，只有最后的聚合、重分区是用 行模式处理的，最后效率大幅度提升

阅读全文

Advanced Database Systems: History of Databases

2023年5月21日
| 读书笔记
数据库的发展历史，从复杂模型：网络模型、层次模型，再到简单的关系模型最后胜出，关系模型不止是简单，而且提出了物理、逻辑解耦、高层级别API；所以从1970年代开始，数据库的基本模型，发展方向是定了；后面出现了各种对关系模型的补充，但是大多数只是重复发明，除了code in database，schema last是比较新颖的发明；在这几十年内，商业数据库一直是主导，IBM、Oracle、微软一直是领导者；直到2000年互联网的出现打破了这个局面，数据库面临大量的访问，需要购买大量商业数据库成本太贵，此时开源产品就是更好的选择；同时也出现了各种对关系模型，他们的扩展性、性能都非常好，但他们不支持SQL、不支持事务，十年之后再看这些数据库多多少少都有一些局限性，于是分布式的NewSQL出现，加上云厂商的对象存储，云上数据库也成为主流；现在数据库有很多细分市场，每个主题内都有好几个玩家，这些数据库在巩固自己领地的同时，又在不断扩展自己的能力；他们开始支持SQL，增加事务，从历史角度看，声明式语言、解耦、简单模型一直是有生命力的

阅读全文

Column-Stores vs. Row-Stores: How Different Are They Really?

2023年5月7日
| 数据库
论文中通过行存系统来模拟列存，并将几个可能提升的关键点：延迟物化、块迭代、压缩、invisible-join，挨个拆分，并分析每种可能提升的原因和提升比例‘在行存的系统中使用垂直分区依然达不到列存性能，因为垂直分区后需要冗余存储主键，重建这些tuple 需要hash-join，数量大内存CPU开销也大；全索引如果返回的数据多hash-join压力大可能会更慢，反之可能更快；物化视图最好只需要读取部分数据，bitmap选择率高时效率会变差。对于列存：块迭代可以提升5% - 50%性能(取决于压缩)、invisible-join可以提升50% - 70%、压缩为2倍，如果数据有序可以量级提升、延迟物化提升3倍，如果将这些全部去掉，列存跟行存就差不多了；在列存中使用反规范化大宽表效果不好，增加维度表列冗余数据变多、只有大宽表的维度属性是排序高度压缩的才有效

阅读全文

Lakehouse A New Generation of Open Platforms that Unify Data Warehousing and Advanced Analytics

2023年5月6日
| 数据库
第一代的数仓有很好的数据治理，缺点是计算存储耦合，且无法存储半结构数据；第二代的数据湖将计算存储分离，且能存储各种格式，云厂商推出的对象存储本质是差不多，不过扩展和可靠性更高更便宜，但二代需要两套系统，数据要在数仓和对象存储之间做ETL，有很多问题；而LakeHouse则试图解决这些问题，通过在对象存储之上增加元数据管理，实现事务功能，数据质量、ACID都实现了，因为是基于开放的格式，不会锁定厂商，也能支持各种场景。因为开放的格式和对象存储的延迟问题，性能和每秒事务不会很好，通过缓存系统、辅助数据结构、数据布局优化来优化性能，另外DataFream 支持SQL和 API，可以延迟处理这样可以进一步优化。目前的限制：S3的延迟、单表事务、servless；通过TPC-DS对比其他云厂商的数仓，性能和价格都很不错，还能支持传统场景，机器学习、科学分析等各种复杂场景。

阅读全文

Building An Elastic Query Engine on Disaggregated Storage

2023年5月4日
| 数据库
SnowFlake的一篇论文，目前的架构包含四层：中心化的服务处理端到端的查询、计算层、临时存储层、对象存储层，并讨论了设计临时存储这一层的原因，通过访问数据指标能发现，临时存储的需求变化很大，跟计算层，远端持久存储层都不同。为更好的提高利用率需要计算层跟 临时存储层解耦。调度方面包括：工作窃取、延迟的一致性hash。由于云厂商的计费方式支持到秒级别，原先的预热VM 方式不好使了需要采用共享资源的方式来支持多租户，带来的挑战是，重新设计临时存储层(这层缓存了持久数据和中间数据，扩容会影响其他租户)，需要提供私有地址。三个开放问题：临时存和计算层解耦、内存-SSD-远端存储三层机制的有效管理、亚秒计费策略的共享资源架构挑战

阅读全文

What Goes Around Comes Around

2023年5月3日
| 数据库
Stonebraker的论文，介绍了 9个不同时代的数据模型；层次数据库IMS，以及网络数据库CODASYL，这两者都是逻辑数据、物理数据耦合，之后出现了关系模型，有了数据独立；再往后就是各种对关系模型的补充，如实体-关系模型、关系模型++、语义数据模型、OO模型、对象关系模型、半结构模型等；从中我们可以总结到：查询优化器很有用、技术的争论通常由市场和其他因素决定，简单模型比复制模型更容易实现数据独立、KISS 保持简单是很重要的、除非用户使用中出现很大问题否则他们不会买单、没有编程语言社区的支持想在语言上做改进突破很难、新技术的推广，需要标准化，或者大力度的推广、schema-last 可能只合适小部分场景

阅读全文

Efficiently Compiling Efficient Query Plans for Modern Hardware

2023年2月5日
| 数据库
这是HyPer的一篇论文(HyPer是由德国莫尼黑大学主导的OLAP、OLTP混合型主内存数据库)，介绍了code-gen的具体实现，最初HyPer的code-gen是生成了C++代码，然后使用gcc编译；但编译时间很长，再加上优化时间就更长了，甚至比查询执行时间还长；于是HyPer做了优化，改用LLVM，将code-gen的核心代码转为了LLVM的IR，这个IR是调用LLVM的API生成的，不是手写的所以相对容易一些，对于一些简单的操作是生成了LLVM，于是复杂的操作，如scan、join、sort需要将LLVM和C++混合执行，LLVM可以直接调用C++，所以不存在性能损失；通过最后执行来看，LLVM的code-gen从编译、优化时间，SQL执行时间，都比其他系统有很大提升

阅读全文

Generating code for holistic query evaluation

2023年2月4日
| 数据库
英国爱丁堡大学的一篇论文，从传统系统到现代系统的变化一个重要点是：内存增大很多，以前的I/O瓶颈对于现在来说不那么重要了，反而是CPU和内存瓶颈；而之前的火山模型对于CPU利用率来说很不好，大量的虚函数调用，多层级的函数调用增加了cache miss，也会产生更多的指令，不利于并行化和cache局部性；这篇论文提出了一个代码模板，通过识别不同的查询计划算子，来对应的生成不同的代码(对应一个大函数)，不同函数之间通过物化来连接，之后通过编译器GCC来编译这段C代码，还可以对代码最O2级别优化(但会增加运行期执行时间)来达到更好的效果，论文对比了join、sort、聚合，虽然使用的是NSM存储模型，但是执行效果来看跟MonetDB的DSM差不多了；代码生成的缺点是对于小查询会有额外的开销(编译、优化、link时间)

阅读全文

Implementing Database Operations Using SIMD Instructions

2023年2月1日
| 数据库
介绍了SIMD指令一些基本概念，并行流水线，以及分支预测失败带来的影响；论文中提到了使用SIMD指令的方式，以及不同平台产生的差异；之后用伪代码的方式描述几个数据库常用操作；scan操作详细对比了标量版和SIMD版的区别，以及如何消除分支的方式，还有返回选中的一个元素、多个元素的标量、SIMD方式；聚合的实现方式SIMD有提供相关的操作 SIMD_min、SIMD_max即可，对于索引部分主要是介绍树结构索引，详细讨论了中间节点、叶子节点的实现方式；在有序元素上使用二分效率是非常高的，但也会有分支预测失败问题，论文中给出了混合二分+顺序扫描方式；最后是join处理方式，这里只列出了nested-loop join的SIMD实现，Duplicate-outer、Duplicate-inner、Rotate-inner

阅读全文

SIMD-Scan: Ultra Fast in-Memory Table Scan using onChip Vector Processing Units

2023年1月19日
| 数据库
现代数据库由I/O瓶颈转向了CPU瓶颈，利用多核能力加速全表扫描，但是向量化的能力没能充分发挥。使用向量化包括：内嵌汇编、硬件厂商提供的跨平台库函数、编译器指示符、编译器自动优化，每种都是可用性和可控性之间的权衡。论文中引入了两项优化：使用SIMD方式在寄存器中解压 轻量压缩数据(使用concatenate、shift、shuffle、mark等指令完成)；使用SIMD完成等值和范围查找(使用掩码指令，将4个元素加载到寄存器中，再通过min、max比较范围，最后生成索引数组向量位)，通过测试结果都有大幅度提升，并且优化实现可以适用各种数据库

阅读全文

  1. 1
  2. 2
  3. 3
  4. 4