Hatena::�֥���(Diary)

ablog ���Υڡ����򥢥��ƥʤ��ɲ� RSS�ե����� Twitter

2017-04-20

���ظ��ǡ����١����Υڡ����Υǡ�����¤

�Իظ��ǡ����١����Ϲ�ñ�̤ǥڡ���(Oracle Database �Ǥ����ǡ����֥��å�)�˥ǡ�������Ǽ���Ƥ����Τ��Ф��ơ����ظ��ǡ����١������󤴤Ȥ˥ڡ����˳�Ǽ���Ƥ��롣�������¹Ի��˷��̥��åȤ��֤��ݤ����̤��Х��Х��Υڡ����˳�Ǽ�����Ƥ����ǡ������ɤ����äƥ��ץ�(�쥳����)���������Ƥ���*1�Τ��Ȼפä������Ϥ���ID�Τ褦�ʤ��Τ����äƤ����褦����

��ID �� C-Store �Ǥ� pid��MonetDB �Ǥ� BAT(Binary Association Tables) �� oid �ȸƤФ��Ƥ��롣

The Design and Implementation of Modern Column-Oriented Database Systems

f:id:yohei-a:20170420230742p:image:w640

  • NSM(N-ary Storage Model): �������ǥ֥��å��ʥڡ����ˤ˥ǡ�������Ǽ��������
  • DSM(Decomposition Storage Model): �������ǥ֥��å��ʥڡ����ˤ˥ǡ�������Ǽ��������

f:id:yohei-a:20170420233150p:image:w360

C-Store �� pid �� MonetDB �� oid �Τ褦�� ID �ʳ��� Join Index �Ȥ�����ˡ�⤢�롣

����Ū�ʼ����� C-Store �Υ�������������Ĵ�٤뤳�Ȥ��Ǥ��롣


�����˾ܤ����Ͻ��������ΰʲ��Υ����ȥ��ǾҲ𤵤��Ƥ���

VLDB 2009 Tutorial on Column-Stores *1 ��ɽ�����줿�Ȥ����ФäƤ��ޤ����錄���ζ��ʽ��Ǥ������ʽ��פȸ��äƤ��ޤä� appengine ja night #21 *2��

Google BigQuery�ʤɤλ��Ȥߤ��Τꤿ���Ȥ������ظ��ǡ����١����������� - wmo6hash::blog

��������饤�ɻ��ȡ�


https://www.cs.duke.edu/courses/fall01/cps216/lectures/10-physical.pdf���⥷���ץ����ɤ�������

NSM = N-ary Storage Model

DSM = Decomposition Storage Model


��­

C-Store �Ϥ��Υޥ����롦���ȡ����֥졼�������������������ظ��ǡ����١����ǡ�����Ū�ˤ��������Ƥ��� Vertica(HP��) �Υ롼�ĤǤ���

���ȡ����֥졼���������Ȱ����ˤ�����ʸ���񤤤Ƥ��� Daniel Abadi �����Ͼ��� VLDB 2009 Tutorial on Column-Stores ���񤤤Ƥ��뤦���ΰ��ͤǤ⤢�ꡢʬ�����䤹���������񤫤��Ƥ����Τ��ץ����å��Ǥ���


MonetDB �ˤĤ��Ƥϰʲ�����


���ȡ����Х����������ǥå���(�����ǥå��������꡼��������)�Ȱ㤦�Τϰʲ��������Ȼפ��ޤ���


f:id:yohei-a:20170508155026p:image:w640f:id:yohei-a:20170508155025p:image:w160

We argue that the poor performance of

MySQL and the commercial RDBMS

��X�� is related to the Volcano iterator pipelining model [6]. While the Volcano approach is elegant and efficient for I/O bound queries, in computation-intensive tasks, its tuple-at-a-time execution makes runtime interpretation overhead dominate execution. That is, the time spent by the RDBMS on actual computations is dwarfed by the time spent interpreting

the expressions in a query tree, and looking up the needed attribute values in pages storing tuples in the N-ary storage model (NSM). As a result, quite a high number of CPU instructions are needed for each simple computational operation occurring in a query. Additionally, the instructions per cycle (IPC) efficiency achieved tends to be low, because the tuple-at-a-time model hides from the CPU most parallel execution opportunities, namely those provided by performing computations for different tuples in an overlapping fashion.

MonetDB [2], developed at CWI 1, is an alternative approach to building a query execution system. Its MIL algebra [3] minimizes the interpretation overhead by providing execution primitives that process data in a column-at-a-time fashion. Since MonetDB uses vertically decomposed storage model (DSM) [5], where columns are simple arrays, and each primitive performs only one fixed operation on the input data, the primitive implementation boils down to a sequential loop over aligned input arrays. Modern compilers can apply loop pipelining to such code, allowing MIL primitives to achieve high IPC on super-scalar CPUs. However, the column-at-a-time execution model introduces the extra cost of intermediate result materialization, which is only sustainable inside main memory, thus limiting the scalability of the system.

Figure 1 presents the architecture of X100, a new execution engine for MonetDB that combines the benefits of low-overhead column-wise query execution with the absence of intermediate result materialization in the Volcano iterator model. One of its distinguishing features is vectorized execution: instead of single tuples, entire vectors of values are passed through the pipeline. Another is in-cache processing: all the execution is happening within the CPU cache, using main memory only as a buffer for I/O and large intermediate data structures. These techniques make X100 execute efficiently on modern CPUs and allow it to achieve raw performance comparable to C code.


�ӥå��ǡ���ʬ�Ϥ��ǡ����١��� Netezza �� Matrix �Ϸ���� �����ơ�Amazon Redshift�⡩����

Matrix�٤ȡ�Netezza�٤γ�ȯ�Ԥ������ꥫ�ͤ�Barry Zane (�Х꡼��������) �ᡣ�����ꥫ�ȥåץ��饹�������ͥ���������������´�ȸ塢Prime Computer�Ҥ�������1983ǯ��Applix�Ҥ˰ܤꡢCTO�˽�Ǥ��13ǯ�ֺ��Ҥ��ޤ�����(Applix�Ҥ�2007ǯ��Cognos�Ҥˤ���������)

���θ塢2000ǯ��Netezza�Ҥ�Ω���夲��PostgeSQL���١����˳�ȯ�����ǡ����١������ץ饤���������ʤǤ�����Netezza�٤���ȯ���ޤ�������Netezza�٤ϡ������󥿡��ץ饤������DWH���ץ饤�������Ȥϡפ��ƹͤ��Ƴ�ȯ���졢�׿�Ū���������ƥ������������С����ǡ����١��������ȥ졼�����ҤȤĤΥޥ��������礹�뤳�Ȥǡ����̥ǡ�����ʬ�Ϥ���ǽ�ˤ��ޤ�����

Barry Zane��: Netezza������, ParAccel MPP (Matrix)������, ���ϥ�����ʬ�ϥ��󥸥����꤬���� �ӥå��ǡ���ʬ�ϸ����ǡ����١����Υ����ѡ��������ƥ��� | Insight Technology, Inc.

  • Amazon Redshift and the Case for Simpler Data Warehouses

6. Related Work

While Amazon Redshift, when launched, was the first widely available data warehouse-as-a-service, its core database technology (parser, optimizer, engine, storage organization, MPP architecture) was derived from technology licensed from ParAccel. ParAccel belongs to a group of column-oriented DBMS products that appeared from the middle through the end of the 2000s: Vertica, Ingres VectorWise, Infobright, Kickfire, and many others [1]. These systems had several similarities in their design philosophy and list of features, with many of them influenced by two pioneering modern column-store systems: CStore [8] and MonetDB/X100 [3].

Redshift��s compression techniques are similar to those used by Vertica, and their performance tradeoffs are well understood [2]. Redshift foregoes traditional indexes (or projections in CStore/Vertica) and instead focuses on sequential scan speed through compiled code execution and column-block skipping based on value-ranges stored in memory. Infobright��s Knowledge Grid and Netezza��s Zone Maps also rely on block skipping which as a technique was first discussed in [5]. Code compilation techniques in query execution have received renewed attention in academia [6][9] and are also used in other systems such as Microsoft��s Hekaton [4].

http://dl.acm.org/ft_gateway.cfm?ftid=1586891&id=2742795

����

*1���̡��Υڡ����˳�Ǽ�����Ƥ��륫�����Υǡ��������礷���쥳�����ʥ��ץ��ˤ˲��򥭡������������Τ���

���ѥ��к��Τ����Υ��ߡ��Ǥ����⤷�����Ƥⲿ�����Ϥ��ʤ��Ǥ�������
������


����ǧ��

�ȥ��å��Хå� - http://d.hatena.ne.jp/yohei-a/20170420/1492685305