TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

How should you build a high-performance column store for the 2020s?

164 点作者 deafcalculus超过 7 年前

15 条评论

manigandham超过 7 年前
Most of these techniques are already in production:<p>Microsoft SQL Server has columnstore indexes and can even be combined with its in-memory tables. MemSQL has been doing this for years and v6 is incredibly fast, also combines in-memory row-stores. ClickHouse is very good if you don&#x27;t mind more operations work. MariaDB has the ColumnStore storage engine, Postgre has the cstore_fdw extension. Vertica, Greenplum, Druid, etc. EventQL was an interesting project but abandoned now.<p>AWS RedShift, Azure SQL Data Warehouse, Snowflake Data, Google BigQuery are the hosted options, with BQ being the most advanced with its vertical integration.<p>If you want to operationalize Apache Arrow today, Dremio is built around it and works similar to Apache Drill and Spark to run distributed queries and joins across data sources.
评论 #15675756 未加载
lima超过 7 年前
Yandex&#x27;s recently open sourced ClickHouse[1] column store does some of these.<p>It heavily relies on compression, data locality and SIMD instructions and supports external dictionaries for lookup.<p>[1]: <a href="https:&#x2F;&#x2F;clickhouse.yandex&#x2F;" rel="nofollow">https:&#x2F;&#x2F;clickhouse.yandex&#x2F;</a>
评论 #15674070 未加载
评论 #15673868 未加载
xoogler_thr超过 7 年前
This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.
评论 #15675644 未加载
评论 #15674039 未加载
评论 #15673750 未加载
elvinyung超过 7 年前
I think one interesting project in the near future could be to try and build a column-oriented storage engine that&#x27;s &quot;good enough&quot; for both OLAP and OLTP workloads.<p>The main precedent here is Spanner&#x27;s <i>Ressi</i> storage engine, which, according to the most recent paper [1], uses a PAX-like format (with blocks arranged row-oriented, but values within a block are column-oriented, so kind of like Parquet) for on-disk data, but combines it with a traditional log-structured merge tree for writes and point queries.<p>[1] <a href="https:&#x2F;&#x2F;static.googleusercontent.com&#x2F;media&#x2F;research.google.com&#x2F;en&#x2F;&#x2F;pubs&#x2F;archive&#x2F;46103.pdf" rel="nofollow">https:&#x2F;&#x2F;static.googleusercontent.com&#x2F;media&#x2F;research.google.c...</a>
评论 #15678426 未加载
bboreham超过 7 年前
I wonder if the 2020s column store would outperform kdb, which was written in the 1990s with a UI from the 1950s.
评论 #15675930 未加载
评论 #15675838 未加载
dustingetz超过 7 年前
Datastore of 2020s will be designed around an immutable log because it permits both strong consistency and horizontal scaling (like git).<p>Once you&#x27;re both distributed and consistent, the problems today&#x27;s stores are architected around, go away. Your distributed queries can index the immutable log however they like. column-oriented, row-oriented, documents, time-oriented, graphs, immutability means you can do all of it, <i>as a library in your application process</i><p><a href="http:&#x2F;&#x2F;www.datomic.com&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.datomic.com&#x2F;</a> - it&#x27;s what you get when Facebook&#x27;s graph datastore has a baby with immutability.
评论 #15673692 未加载
评论 #15675007 未加载
评论 #15675474 未加载
评论 #15674601 未加载
评论 #15676539 未加载
twotwotwo超过 7 年前
If I had to guess new capabilities chips will add in the 2020s, hardware-accelerated compression or compact encoding are near the top of the list. That could be anything from branch-free instructions to read&#x2F;write varints to fully-self-contained (un)packer(s) you just point at some data and run. I&#x27;m <i>most</i> interested in something so fast as to be worth considering to replace fast software algos or to use in places we don&#x27;t think about compressing at all now, though hardware accelerated zlib would obviously have applications too.<p>Some existing stabs in this direction include that some Samsung SoCs had a simple &quot;MComp&quot; memory compressor (<a href="https:&#x2F;&#x2F;github.com&#x2F;XileForce&#x2F;Vindicator-S6-Unified&#x2F;blob&#x2F;master&#x2F;drivers&#x2F;memory&#x2F;exynos-mcomp.h" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;XileForce&#x2F;Vindicator-S6-Unified&#x2F;blob&#x2F;mast...</a>), that the new Qualcomm Centriq chips use compression (<a href="https:&#x2F;&#x2F;3s81si1s5ygj3mzby34dq6qf-wpengine.netdna-ssl.com&#x2F;wp-content&#x2F;uploads&#x2F;2017&#x2F;08&#x2F;qualcomm-amberwing-memory-compression.jpg" rel="nofollow">https:&#x2F;&#x2F;3s81si1s5ygj3mzby34dq6qf-wpengine.netdna-ssl.com&#x2F;wp-...</a>), and that some IBM POWER CPUs have dedicated circuitry for memory compression (<a href="http:&#x2F;&#x2F;ibmsystemsmag.com&#x2F;aix&#x2F;administrator&#x2F;lpar&#x2F;ame-intro&#x2F;" rel="nofollow">http:&#x2F;&#x2F;ibmsystemsmag.com&#x2F;aix&#x2F;administrator&#x2F;lpar&#x2F;ame-intro&#x2F;</a>). There&#x27;s also hardware zlib offload, like Intel QuickAssist.<p>I&#x27;d expect more of this in the future because 1) space-is-speed is just a fundamental thing we deal with computing, 2) chips keep getting faster relative to RAM, 3) you already see lots of special-purpose instructions being added (crypto, strings, fancier vector stuff...) as it gets more expensive to improve general-purpose IPC. Maybe there&#x27;s some additional value given the arrival of 3D XPoint and (probably) other future NVRAMs--would help you fit more on them without spending more time compressing than writing--but regardless, the trends seem to point to compression assists being interesting.<p>One reason I could turn out wrong is if the general-purpose facilities we have make software the best place to write compressors anyway, i.e., fast software packers get so good it becomes difficult to justify hardware assists. General-purpose low- and medium-compression algos like LZ4 and Zstd run pretty fast already, and we have even faster memory compressors (WKdm, Density). Of course, that&#x27;s on big Intel cores; maybe special-purpose compressor hardware will continue to mostly be more interesting alongside smaller cores.
jaffee超过 7 年前
Pilosa, <a href="https:&#x2F;&#x2F;github.com&#x2F;pilosa&#x2F;pilosa" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pilosa&#x2F;pilosa</a> which is mentioned, is actually open source, and a relatively readable Go codebase if anyone is interested in what &quot;an entire data engine on top of bit-vectors&quot; looks like.
gopalv超过 7 年前
(man, I&#x27;d love to go work on this for three years, without worrying about a &quot;customer&quot; or &quot;backwards compatability&quot;)<p>&gt; That is, if you have N distinct values, you can store them using ceil(log(N)&#x2F;log(2)) bits<p>Ideally you don&#x27;t need to do ceil, if you had an low number like 5 items, then it looks like you need 3 bits to store it, but you can store it in 2.4 bits (just pack 10 values into 24 bits instead of 30).<p>Getting distinct and repeated values by tearing apart data so that you can use these algorithms is something which I could use some papers to refer to.<p>For instance, here&#x27;s[1] what we&#x27;re trying to do with Double encoding loops, but it still suffers from the problems of a car moving from 0.3 -&gt; 0.2 location.<p>[1] - <a href="http:&#x2F;&#x2F;bit.ly&#x2F;2zt70iL" rel="nofollow">http:&#x2F;&#x2F;bit.ly&#x2F;2zt70iL</a>
alberth超过 7 年前
Are column-store databases relevant on SSD&#x2F;NVME?<p>I ask because on a physical medium like hard disk, storing data on physical disk in column orientation can make a significant improvement to read operations.<p>But with SSD&#x2F;NVME, you don’t have to worry about the inherent slowness of physical platters that exist in hard disk.
评论 #15675442 未加载
评论 #15675966 未加载
评论 #15675502 未加载
rwmj超过 7 年前
Possibly naive question, but isn&#x27;t an index (in a classical relational database) the same as a column store?
评论 #15675486 未加载
评论 #15675720 未加载
argimenes超过 7 年前
Not Invented Here, huh?
misterHN超过 7 年前
put data in text files, ASCII printable characters, one data point per line<p>put data files in directory<p>name data files after columns<p>use &quot;.data&quot; filename extension for data files<p>write a tool to create index files (append &quot;.index&quot; to the name of the input text file) that map record number to byte offset in data file<p>If data files are all &lt; 4GB, use a 32 bit unsigned integer to represent the byte offset in the index file<p>Each index file is a packed array of 32 bit integers<p>Write a tool to create length files &quot;.length&quot; that count the number of entries in a data file<p>Generate .length files for all data files<p>Use mmap to access index files<p>Use C for all of the above<p>This is for variable-length data values. Not every column will have these, making the .index files redundant in this case; the .index files should not be created in this case and program logic should support both uniform value length access and nonuniform value length access. The reason to prefer two access modes is to keep data from the .index files out of the cache when it is redundant.<p>When all of this is done, the next thing to do is write a tool to test the cache characteristics on your processor by implementing sorting algorithms and testing their performance. Unless you are using a GPU (why?) all data your algorithm touches will go through every level of the cache hierarchy, forcing other data out. If possible, use a tool that reports hardware diagnostics. These tools may be provided by the processor vendor.<p>Now, there is a trend to give the programmer control over cache behavior<p><a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;9544094&#x2F;how-to-mark-some-memory-ranges-as-non-cacheable-from-c" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;9544094&#x2F;how-to-mark-some...</a><p>I don&#x27;t know if this is worth exploring or a wild goose chase. It may improve performance for some tasks, but it sounds a little strange for the programmer to tell the computer how to use the cache...shouldn&#x27;t the operating system do this?<p>Anyway, that&#x27;s a start.
评论 #15674060 未加载
dogruck超过 7 年前
Sure comes across as arrogant for Prof Abadi to remark:<p>&gt; I assume that the Arrow developers will eventually read my 2006 paper on compression in column-stores and expand their compression options to include other schemes which can be operated on directly (such as run-length-encoding and bit-vector compression).<p>In this blog post, I don’t agree with:<p>&gt; Almost every single major data-processing platform that has emerged in the last decade has been either open source.<p>That’s somewhat true by definition. OTOH, I also know most financial firms use proprietary solutions (which leverage open source components).
WilsonPhillips超过 7 年前
I think incorporating a blockchain element could prove an interesting way to implement this in practice.
评论 #15675044 未加载