[go: up one dir, main page]

CN116034349A - 列式分析存储格式的半结构化数据的概率文本索引 - Google Patents

列式分析存储格式的半结构化数据的概率文本索引 Download PDF

Info

Publication number
CN116034349A
CN116034349A CN202180050173.2A CN202180050173A CN116034349A CN 116034349 A CN116034349 A CN 116034349A CN 202180050173 A CN202180050173 A CN 202180050173A CN 116034349 A CN116034349 A CN 116034349A
Authority
CN
China
Prior art keywords
text
bitmap
columns
computer
file
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202180050173.2A
Other languages
English (en)
Inventor
温鉴
H·阿哈麦迪
S·金图卡尔
N·阿格尔沃
宛立建
S·哈里哈拉苏布拉曼尼安
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Oracle International Corp
Original Assignee
Oracle International Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Oracle International Corp filed Critical Oracle International Corp
Publication of CN116034349A publication Critical patent/CN116034349A/zh
Pending legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V30/00—Character recognition; Recognising digital ink; Document-oriented image-based pattern recognition
    • G06V30/40—Document-oriented image-based pattern recognition
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/80—Information retrieval; Database structures therefor; File system structures therefor of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML
    • G06F16/81—Indexing, e.g. XML tags; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/13—File access structures, e.g. distributed indices
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2237—Vectors, bitmaps or matrices
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/22—Matching criteria, e.g. proximity measures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/62—Protecting access to data via a platform, e.g. using keys or access control rules
    • G06F21/6218—Protecting access to data via a platform, e.g. using keys or access control rules to a system of files or objects, e.g. local or distributed file system or database
    • G06F21/6245—Protecting personal data, e.g. for financial or medical purposes
    • G06F21/6254—Protecting personal data, e.g. for financial or medical purposes by anonymising data, e.g. decorrelating personal data from the owner's identification
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F40/00—Handling natural language data
    • G06F40/20—Natural language analysis
    • G06F40/279—Recognition of textual entities
    • G06F40/289—Phrasal analysis, e.g. finite state techniques or chunking
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V30/00—Character recognition; Recognising digital ink; Document-oriented image-based pattern recognition
    • G06V30/40—Document-oriented image-based pattern recognition
    • G06V30/43—Editing text-bitmaps, e.g. alignment, spacing; Semantic analysis of bitmaps of text without OCR

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • General Health & Medical Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Software Systems (AREA)
  • Bioethics (AREA)
  • Computer Security & Cryptography (AREA)
  • Audiology, Speech & Language Pathology (AREA)
  • Computational Linguistics (AREA)
  • Computer Hardware Design (AREA)
  • Medical Informatics (AREA)
  • Multimedia (AREA)
  • Evolutionary Computation (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本文是一种概率加索引技术，用于使用列式输入/输出(I/O)避免来搜索诸如Parquet之类的列式存储格式中的半结构化文本文档，并且需要最小的存储开销。在实施例中，计算机将列与半结构化文档中出现的文本串相关联。检测文本串中出现的文本词。分别为每个文本词生成多个位图中包含用于每一列的相应位的位图。基于位图中的至少一个位图，访问列中的一些列或半结构化文档中的一些半结构化文档。

Description

列式分析存储格式的半结构化数据的概率文本索引
相关申请的交叉引用
Hamed Ahmadi等人于2020年3月10日提交的标题为“PERSONAL INFORMATIONINDEXING FOR COLUMNAR DATA STORAGE FORMAT”的相关美国专利申请16/814,855整体并入本文。以下非专利文献(NPL)通过引用整体并入本文：
·Julien Le Dem的“DREMEL MADE SIMPLE WITHPARQUET”，2013年9月11日发布，网址：
https://blog.twitter.com/engineering/en_us/a/2013/dremel-made-simple-with-parquet.html
·于2017年10月16日发布的“APACHE PARQUET”，网址：
https://github.com/apache/parquet-format/blob/f1de77d31936f4d50f1286676a0034b6339918ee/README.md
技术领域
本发明涉及对半结构化文本文档的集合的查询加速。本文介绍了基于位图关键字索引和列式持久化的全文搜索技术。
背景技术
半结构化内容广泛用于持久化信息，因为它在形式“结构化”内容和自然“非结构化”内容之间提供了最优折衷。半结构化数据通常具有更好的可读性并且容易被人类消耗。由于促进编码、标记化(tokenize)、解析和/或某种语义分析的定义明确的结构特性，半结构化数据也可以通过编程方式进行处理。例如，由于诸如超文本标记语言(HTML)、JavaScript对象表示法(JSON)或可扩展标记语言(XML)之类的正式标准指定的定义明确的格式，典型的网页内容一般是半结构化的、人类可读的且容易由脚本语言处理的。
因为半结构化数据是人类可读的，所以用自然的自由格式文本搜索来搜索结构化和非结构化字段非常普遍。这种搜索的重要特征是指定的文本可以出现在半结构化文本的任何部分中。
在一些领域高效地进行上述搜索是重要的。例如，在欧盟(EU)的《通用数据保护条例》(General Data Protection Regulation，GDPR)中，“被遗忘权”要求找到与指定的个人文本串相关的所有记录并按需删除。这项工作必须在短时间窗口内完成。因此，有必要使用工具来辅助搜索过程以高效地执行这个过程，尤其是当涉及数亿个可用半结构化文档中的未知部分时。
在应用层面，支持半结构化文本搜索通常涉及倒排索引的构造。这在诸如Lucene等之类的搜索应用中是常见的。倒排索引可以使搜索加速为与文档大小的对数成正比，这通常是几个数量级。但是，这样的文本索引几乎和数据本身一样大。这阻止了将倒排索引包括在内容文件本身中，因为它会使文件的存储占用空间加倍。因此，通常替代地将索引单独保存在归档存储装置或其它更便宜的大容量持久存储装置中。
附图说明
在图中：
图1是描绘示例计算机的框图，它加速在数据存储库(诸如半结构化文档的数据库)中搜索文本词；
图2是描绘示例过程的流程图，该过程加速在数据存储库(诸如半结构化文档的数据库)中搜索文本词；
图3是描绘基于Parquet文件的水平和垂直可扩展性的示例加速过程的流程图；
图4是描绘JavaScript对象表示法(JSON)字段到Parquet列的示例映射的框图；
图5是描绘示例性摄取和索引形成可以如何进行的流程图；
图6是图示可以在其上实现本发明的实施例的计算机系统的框图；
图7是图示可以用于控制计算系统的操作的基本软件系统的框图。
具体实施方式
在下面的描述中，出于解释的目的，阐述了许多具体细节以便提供对本发明的透彻理解。但是，将明显的是，可以在没有这些具体细节的情况下实践本发明。在其它情况下，以框图形式示出了众所周知的结构和设备，以避免不必要地使本发明模糊。
总体概述
本文是一种概率索引技术，用于使用列式I/O避免搜索诸如Parquet之类的列式存储格式的半结构化文本，并且需要最小的索引存储开销。当半结构化内容被解析为单独的数据列时，可以通过数据库模式或其它描述性元数据来维护结构信息，因此所得到的列式数据差不多等同于原始输入数据。对原始半结构化文本的文本搜索可以映射到对所摄取的列式数据的查询。只要将查询应用于包含结构化数据的少数列，这种方法就可以高效地工作，但是当必须对整个半结构化内容进行搜索时，这种方法就会变得效率低下。
一个技术问题是文本搜索查询预期感兴趣的数据可能在原始半结构化文本的许多字段中的任何一个中，因此查询执行不应当只查看个别字段。对关键字的所有字段的搜索将与全表扫描一样昂贵，这通常效率低下并且不推荐使用。
本文的技术通过在原始半结构化数据上创建索引并将索引嵌入到Parquet列式文件格式中来解决这个技术问题。本文的方法将概率文本搜索索引与Parquet列式格式相结合，并通过使用索引过滤Parquet列和行-组来实现I/O避免。索引包括每个可搜索词的位图。每个位图指示哪一列包含相应的词。
在实施例中，计算机将列与半结构化文档中出现的文本串相关联。检测文本串中出现的文本词。分别为每个文本词生成多个位图中包含用于每个列的相应位的位图。基于位图中的至少一个位图，访问列中的一些列或半结构化文档中的一些半结构化文档。
1.0示例计算机
图1是描绘实施例中的示例计算机100的框图。计算机100使在诸如半结构化文档的数据库之类的数据存储库中搜索文本词加速。
计算机100可以是一个或多个计算机，诸如：诸如刀片之类的机架式服务器、个人计算机、大型机、虚拟计算机或其它计算设备。当计算机100具有多个计算机时，这些计算机通过通信网络互连。在计算机100的易失性或非易失性存储装置或远程存储装置中，计算机100可以访问许多半结构化文本文档，诸如可以驻留在(一个或多个)文件或诸如数据库之类的大容量数据存储库中的文档131-132。
在这个示例中，文档131包含JavaScript对象表示法(JSON)。文档132包含可扩展标记语言(XML)。在任何情况下，文档131-132都是半结构化的，因为它们的内容可以是以下内容的混合：a)经解析的文本，诸如文档131-132中未加引号的标点符号或文档132中元素和属性的可扩展标记语言(XML)名称，以及b)自由格式文本，诸如：文档131-132中引用的文本，以及文档132中的自由格式文本(诸如“Notes about route.”)。在实施例中，半结构化文档可以是二进制对象，诸如包含二进制数据和文本串的混合的文件或二进制大对象(BLOB)。
文档131-132内文本串的划分取决于实施例。例如，JSON和XML具有基于空格和标点符号的上下文出现的相应形式语法。计算机100可以使用JSON或XML解析器从文档中识别和/或提取上下文文本串。解析器实施例包括流式标记化器，诸如用于XML的简单API(应用程序接口)(SAX)，以及解析树生成器，诸如用于文档对象模型(DOM)。
虽然一些文本在文档131-132中示为被引号括住，但引号不包括在文本串的值中。在文档131中，文本串被引号括住。在文档132中，文本串可能或可能没有被引号括住。例如，计算机100可以在文档132中单独访问的四个单独的文本串是：“Car-Plan”、“mode”、“notby bike”和“Notes about route.”。虽然文档131-132示出了几乎完全相同的内容和结构，但附加文档可以具有相同或不同的内容和/或结构。
全文搜索需要在可用文档的一些或全部文档中的文本串的一些或全部文本串中搜索子串。虽然计算机100可以单独访问文档中的文本串，但一些技术依靠对整个文档131-132进行线性扫描来搜索子串。即使文档中的文本串被冗余地存储在数据库中并被加索引，数据库索引也是不合适的，因为它只跟踪整个文本串。如果文本串被分隔到不同的数据库列(诸如A-C)中，那么数据库索引就更不适合了，因为只有一列被数据库索引加索引。Hadoop数据仓库框架缺少数据库索引。虽然倒排索引可以处置部分文本串，但倒排索引的大小通常几乎与被索引的列一样大，这可能不适合数据仓库的规模。
在实施例中，计算机100持久化(persist)包括文本串的值的列A-C。列是值的一维向量，其可以具有相似的含义和/或相同的数据类型。例如，B列中存储的每个值可以限于指示旅程的目的地地点的文本串，诸如文档131-132中所示的“car garage”。
取决于场景或实施例，一些存储的文本串可以具有明显任意的值。在任何情况下，A-C列中的至少一些至少包含一些自然语言值。自然语言包含可以出现在A-C列中的可识别词，诸如“car”、“road”和“bike”，如原始索引110中所示。
文档131-132可以是分层的，其中半结构化内容嵌套在半结构化内容中，如图所示。在实施例中，哪一列存储文本串取决于该文本串出现在文档中的层次结构中的什么位置，包括哪个嵌套级别。在相关非专利文献(NPL)“DREMEL MADE SIMPLE WITH PARQUET”中介绍了将分层半结构化内容中的字段映射到相同或不同关系表的列。
计算机100可以得出原始索引110的A-C列中出现的一些或所有不同词的清单。取决于实施例，计算机100可以通过以下方式得出词清单：a)从A-C列中提取词，或b)在将数据从外部源摄取到A-C列期间(诸如在诸如从文档131-132提取、转换和加载(ETL)期间)观察词。例如，如本文稍后所讨论的，诸如131-132之类的半结构化文档或名称-值对的特性文件可以由计算机100解析成文本串，然后将文本串持久化到原始索引110的A-C列中。这种文本串可以包含：a)单个词，诸如特性或属性的名称或值，b)多个词，诸如术语、短语、句子或段落，或c)明显任意或损坏的文本，诸如电话号码、首字母缩略词或通用资源定位符(URL)。
标记化可以诸如根据内部分隔符(诸如空格和/或标点符号)将多词文本串(诸如“Notes about route.”)分解成单独的词。例如，列A可以包含值，诸如所示出的“road-for-car”，从中可以检测到三个单独的词“road”、“for”和“car”。对于计算机100的词清单中的每个词，可以生成诸如C-E之类的位图作为索引，其指示哪些列A-C包含那个词。如图所示，分别为“car”和“road”生成位图C-D。
位图D对于包含文本串的每一列A-C分别包含位0-2。例如，如图所示，位图D的位0表示“是”以指示“road”出现在列A中。
同样，位图D的位1表示“否”以指示“road”未出现在列B中。同样，位图C的位1表示“是”以指示“car”出现在列B中。因此，位图C-E可以用作索引来检测哪些列包括包含哪些词的文本串。在各种实施例中，位图对于大小写敏感或不敏感，使得‘car’、‘Car’
和‘CAR’是相同或不同的词。
列A-C可以包含数百万个值，这些值共同包含数千个不同的词。因此，即使仅生成数千个位图，它们的生成也可能需要标记化数百万个文本串。当文本串长时，标记化工作会增加。例如，SQL VARCHAR2值可以包含数万个字符。在实施例中，可以诸如每晚(诸如当非弹性计算机集群不太忙时或当使用弹性公共云不太昂贵时)调度标记化和/或位图C-E的生成。
虽然适用于位图生成，但当稍后诸如利用交互式自组织查询或在线事务处理(OLTP)使用位图C-E时，这种离线批量处理可能不适合。本文稍后呈现的是通过使用位图C-E来避免输入/输出(I/O)访问列A-C来加速查询执行的方法。例如，位图E指示“bike”未出现在列A-C中。因此，在A-C列中搜索“bike”可以检测到“bike”的缺失，而无需实际访问文档131-132或列A-C。
在实施例中，列A-C可以以列式文件格式(诸如Apache Parquet)被持久化，诸如相关非专利文献(NPL)“APACHE PARQUET”中所呈现的。Parquet文件是自描述的，使得每个文件都包含解析该文件所需的元数据。在实施例中，位图C-E存储在每个Parquet文件的元数据中，该文件包含任何列A-C的部分或全部。
如相关NPL“APACHE PARQUET”中所解释的，Parquet文件是Hadoop文件系统(HDFS)文件，其可以被水平分区，诸如用于：a)分布式存储，诸如为了水平缩放，和/或b)随机访问，诸如当按值范围分区时。例如，如果按月对记录进行分区，那么2020年1月的记录将在隔离的文件中直接可用，该文件可以被独立访问，而无需访问诸如用于其它月份的其它数据文件。例如，列A-B可以一起在同一个Parquet文件中被持久化，并且列C可以在其自己的Parquet文件中被持久化。因此，每个月可以有两个文件。在实施例中，基于哪些列驻留在哪些Parquet文件中，位图C-E被分解成更小的位图。例如，当列A-B一起在同一个Parquet文件中被持久化时，在那个Parquet文件中被持久化的位图可以仅包含用于相应列A-B的位0-1。而仅持久化列C的另一个Parquet文件可以包含仅包含用于列C的位2的位图。
文档131-132可以分层嵌套许多子结构，并且不同的文档可以嵌套不同的子结构。可以存在可能的数百个不同的可嵌套子结构，每个子结构都具有映射到不同的相应列(诸如A-C)的几十个或数百个可能的字段。因此，可以有数百或数千列，因此在水平分区之前可以有数百或数千个Parquet文件，而在分区之后可以有数万个Parquet文件。如上面所解释的，计算机100的词清单中的每个词可以具有其自己的位图，并且可以有数千个词和数千个位图，其中的每个位图都可以在数千个Parquet分区文件中的每一个的元数据中被复制。因此，位图持久化本身就可能使可用存储负担过重。
该技术问题在本文通过针对不同的相应词将原始索引110中的位图组合以生成具有更少位图的缩减的索引120来解决。因此，虽然原始索引110可能具有太多位图而无法切实复制到每个Parquet分区文件中，但缩减的索引120具有足够少的位图以易于复制到每个Parquet分区文件中。缩减的索引120如下生成。
原始索引110的位图被成对比较以检测哪些位图相似。例如，可以比较位图C-E的所有可能配对。两个位图是否相似取决于实施例的相似性准则和/或阈值。在实施例中，如果两个位图对于相同的位0-2具有相同的值，那么它们是相似的。
原始索引110中相似的位图被组合成缩减的索引120中相同量的位的单个位图。缩减的索引120中的所有位图都具有不同的值，因为原始索引110中对于所有位共享相同值的任何位图被组合成一个位图。例如，普遍存在的词出现在所有列A-C中。在原始索引110中，每个这样普遍存在的词都具有相应的位图，其中所有位都设置为“是”，但在缩减的索引120中，所有这些普遍存在的词只共享单个位图。
在中间表中所示的实施例中，如果两个词的位图值相差最多一个位，那么这两个词是相似的。例如，如图所示，位图D-E是相似的，因为它们的所有位1-2在两个位图中都具有相同的值。只有位0在位图D-E中具有不同的值，因此位图D-E仅相差一位，这指示位图D-E的相似性。因此，位图D-E被组合成缩减的索引120中的位图F。因此，缩减的索引120包含比原始索引110更少的位图。
将用于“road”的位图D和用于“bike”的位图E进行组合意味着位图F用于“road”和“bike”两者。在实施例中，位图D-E通过使用按位或的按位析取来组合。在那种情况下，如果一个位在位图D或者E中被设置为“是”，那么位图F中的该位被设置为“是”，如本文稍后所讨论的。
2.0示例词加索引过程
图2是描绘计算机100可以执行以加速在诸如半结构化文档的数据库之类的数据存储库中搜索文本词的示例词加索引过程的流程图。参考图1讨论图2。
图2的过程分两个阶段进行。第一阶段可以是所谓的离线的，诸如每小时或每晚调度。第一阶段需要步骤201-203，这些步骤生成原始索引110，并且在一些实施例中生成缩减的索引120。
步骤201将数据列A-C与出现在半结构化文档131-132中的文本串相关联。例如，可以从文档中的一个文档中提取每个文本串，然后将其存储到列中的一个列中。使用哪个列取决于：a)(诸如在文档模式中声明的)文档字段到列的映射，以及b)从哪个字段中提取了文本串。图4中示出了步骤201的示例结果，该步骤需要将文档分解成文本串，然后将这些字符串存储到列中。
各种实施例可以如下增强步骤201。文本串分界和/或提取可以由标记化器或解析器执行，该标记化器或解析器：a)指示文档内文本串的地址或偏移量，和/或b)将分隔符串(诸如空格和/或标点符号)视为与文本串相同。例如，“field:'value'”可以产生四个文本串“field”、“:'”、“value”和“'”。
持久化分隔符串可以促进从存储在列中的文本串重构文档。一旦文本串在列中被持久化，就可以删除原始文档131-132。如果以后需要整个文档131，那么它可以从列中的文本串自动重新生成。元数据可以诸如在附加列中被持久化，诸如：a)特定文本串所来自的文档的标识符，和/或b)特定文本串所来自的文档中的位置。这种元数据可以促进：a)已删除的文档的重构，和/或b)在文本串处或附近检查文档。
紧接在提取之后和列式存储之前，步骤201可以将文本串转换成仅大写或小写，然后将转换后的串而不是原始串存储到列中，以促进以后不区分大小写的搜索。
步骤202检测出现在文本串中的文本词。标记化器可以通过识别空格和/或标点符号来标记和/或提取文本串中的词。
分别针对每个文本词，步骤203生成相应的位图，诸如C-D，其包含用于每个列A-C的相应位。每个位都被设置为布尔值，其可以被称为真(true)、假(false)、是(yes)、否(no)、已设置(set)、已清零(clear)、打开(on)、关闭(off)、一(one)或零(zero)。只有与包含该词的列对应的位才被设置为“是”。
索引110或120，包括索引的位图，可以在与由索引加索引的列相同的文件中被持久化。如果列的两个子集存储在单独的垂直分区文件中，那么每个垂直分区文件存储仅对列的相应子集加索引的单独索引。因为不同的索引需要不相交的列子集，所以不同索引的位图中的相同位位置与不同的列对应。例如，如图所示，位位置0-2与索引110和120中的列A-C对应，但在用于列X-Z(未示出)的索引中，相同的位位置0-2替代地与列X-Z对应。
当索引110或120被持久化时，离线阶段结束。最终在线阶段发生，其根据实施例或场景需要步骤204和/或205。在线阶段可以参与各种场景，诸如交互式自组织查询或在线分析处理(OLAP)。在实施例中，所有被持久化的数据和元数据都仅在在线阶段被读取。例如，步骤204-205适于搜索只读的归档存储层。
基于索引110或120的至少一个位图，步骤204访问至少一列。例如，查询可以问布尔问题，诸如是否存在包含“bike”的文档。即使原始索引110在生成缩减的索引120之后被丢弃，检查位图F也将不会提供假阴性。即，如果位图F的位0-2全部为“否”，那么存在性查询将在不访问列或文档的情况下回答为“否”。
但是，如图所示，位图F的位0是“是”，这是模糊的，可能是也可能不是假阳性。在那种情况下，步骤204线性扫描列A以寻找包含“bike”作为子串的文本串。如图所示，没有文档包含“bike”，列A的扫描证实了这一点，并且：a)虽然位图F的位0提供了假阳性，b)但是对查询的答案是“否”。列B-C不需要加载、访问和/或扫描，因为位图F的位1-2为“否”。
如果查询代替地要求包含“car”和“road”两者的所有文档的标识符，那么步骤204更复杂，因为：a)需要多个位图C和F，以及b)列中的文本串值应当关联回包含文本串的文档。在实施例中：a)列A-C被存储在同一个列文件中，并且b)文档131-132具有单独的列式文件，这些文件包含单独的索引，这些单独的索引包含单独的位图。在那种情况下，在一列中找到词需要：a)检查每个文件中的位图，以及b)不在文件中扫描该列、在一个或两个文件中扫描该列。扫描在哪个(哪些)文件中找到该词指示哪个(哪些)文档包含该词。
在实施例中，文档131-132共享相同的列式文件。诸如在文件中的元数据可以针对每一列或列的子集指示与每个文档对应的列内的值偏移量或地址的范围。例如，偏移量元数据可以指示列A的前五个文本串来自文档131，列A的后两个文本串来自文档132。因此，如果在扫描期间在列A的第三个文本串中检测到词，那么该词出现在文档131中。
此类偏移量元数据可以被用于某种程度的随机访问，诸如寻找。例如，如果列A中的前一百个文本串来自文档131中的数组字段，并且列A中的第二个一百个文本串来自文档132中的同一字段，那么询问数组字段是否包含文档132中的词的查询可以在扫描列A时跳过前一百个文本串，并在扫描第二个一百个文本串之后(诸如当列A包含来自数千个文档的数百万个文本串时)停止。
同样，如果要求包含存储在列A中的数组字段中的词的所有文档的标识符的查询可以通过以下方式加速：a)在列A中的第十个文本串中找到词以确认文档131包含该字段中的词，并且b)然后通过寻找第二个一百个文本串的开头来跳过九十个文本串以扫描文档132的列A的部分。
类似的元数据可以指示列中的文本串来自哪个字段，诸如当多个字段存储在同一列中时。在一些情况下，步骤204足以回答查询，并且步骤205不发生。如果查询请求检索整个文档或跨越多个字段和/或列的文档部分，那么步骤205如下发生。
基于在步骤204中被访问的至少一列，在步骤205中访问至少一个文档。例如，可用的列式文件可以包括包含来自易腐货物的采购订单文档的文本串的第一文件、用于干货订单的第二文件，以及用于非货物(诸如提供的服务)的订单的第三文件。为客户生成月度账单可能需要：a)向客户指派数字标识符，b)在采购订单文档的字段中记录客户编号，c)在步骤203中，为三个列式文件中的每一个生成指示哪些列包含该客户的编号的单独位图，d)在步骤204中，使用三个位图来检测哪些列式文件包含针对那个客户的订单数据，以及e)同样在步骤204中扫描三个文件中的一些文件的一些列以检测哪些文档包含客户编号。在检测到哪些采购订单文档针对那个客户之后，在步骤205中，基于访问那些采购订单文档的内容和/或三个文件的一些列的内容，为该客户生成月度账单。
3.0示例可扩展处理
图3是描绘基于Parquet文件的水平和垂直可扩展性的示例加速过程的流程图。参考图1讨论图3。
图3的过程分两个阶段进行。第一阶段是准备阶段并且可能有点离线发生，诸如如本文早先所讨论的那样每晚调度。第一阶段从半结构化文档生成Parquet分区文件，诸如相关NPL“DREMEL MADE SIMPLE WITH PARQUET”中所述。
如前面所解释的，当不同的列在单独的文件中被持久化时，发生垂直分区。垂直分区的优点是针对关键字的查询执行可以通过仅访问包括包含该关键字的列的那些列式文件来限制输入/输出(I/O)。例如，如图1中所示，“road”出现在列A中，但未出现在列B-C中。因此，根据位图D，搜索“road”只需要访问包含用于列A的数据的Parquet文件。
当用于不同文档集的数据存储在单独的Parquet文件中时，水平分区发生。例如，文档131-132可以在不同的日期创建。如果Parquet文件按天水平分区，那么来自文档131-132的内容将在单独的相应Parquet分区中被持久化。
步骤302A-E演示了轮换控制台日志的场景，该日志被周期性地截断并用控制台输出的行重新填充，诸如该控制台输出来自包括内联的JSON文档的标准输出(stdout)，如下所示。例如，服务器程序可以将stdout重定向到控制台日志，该日志在每晚午夜被截断为空。因此，跨越数月或数年的文本行的无限长的流与单个日志文件相关联。在另一个示例中，只有连续的文本行的流，但没有文件。
控制台日志中的每一行文本都可以包含冗长的诊断文章，诸如“July 15:Wrote26bytes to～/dump.bin”，其可以被解析以提取名称值对，诸如date＝July 15，length＝26以及文件＝'～/dump.bin'。文本的一些行可以包含内联的JSON文档，诸如{date:”July15”,length:26,file:”～/dump.bin”}。在任何情况下，文本的每一行都可以作为单独的文档被摄取，无论是JSON还是特性的集合。
每天都可以生成新的Parquet水平分区。例如，步骤302A基于内容日志中用于7月15日的文本行的内容来填充列A-C中的每一列的7月15日分区。步骤302B为每个7月15日分区文件生成针对诸如“car”之类的词的位图的7月15日实例。
在午夜，步骤302C截断控制台日志文件并开始用7月16日的文本行重新填充日志文件。步骤302D根据内容日志中7月16日的文本行的内容来填充列A-C中每一列的7月16日分区。步骤302E为每个7月16日分区文件生成针对词“car”的位图的7月16日实例。
步骤304A-B演示了缩减的索引120的生成。步骤304A测量不同文本词的位图之间的相似性。在实施例中，Jaccard距离被用于测量两个位图之间的相似性。当比较两个位图时，比较每个位图中同一位置的位，诸如位图D中的位0与位图E中的位0。在所有位位置上，对匹配和不匹配的位的数量计数。例如，位图D-E有两个匹配的位1-2和一个不匹配的位0。Jaccard距离可以被计算为匹配除以不匹配，对于位图D-E为2/1＝二。对于位图C和E，Jaccard距离为0/3＝零。
基于测得的相似性，步骤304B用具有相同位数的单个位图来替换两个文本词的位图。例如，位图D-E的比较可以满足至少为二的示例阈值Jaccard距离。在缩减的索引120中，位图D-E被组合并用位图F替换，如本文前面所解释的。
步骤306A-C演示了缩减的索引120的统计性质，当在列中搜索诸如“bike”之类的词时，该统计性质可能造成假阳性。基于位图F的位0被设置为“是”，步骤306A检测到列A包含“road”和/或“bike”，这是模糊的。步骤306B检测到列A包含“road”但不包含“bike”。例如，对列A的分区中的所有值进行线性扫描可以检测到列A的分区包含“road”但不包含“bike”。
列A可以在另一个Parquet文件中有另一个分区，该文件包含位图的对于位0可以具有不同的值(诸如“否”)的另一个实例。因为本文的位图不造成假阴性，所以计算机100可以检查位图以明确地检测到列的分区中不存在词。基于对于其它分区的位0为“否”，步骤306C在列A的所有分区中搜索bike时不访问列A的其它分区的Parquet文件。
步骤308演示了对值的编辑或对包含该值的文件的删除，根据不同国家的各种在线隐私法，可能需要这两者中的任一个。例如，在一些场景中，法律可以禁止公布家庭住址。自动生成和发布人的传记网页的网站可能需要编辑网页上所有出现的人的家乡街道名称，如果网页是由几十个半结构化文档生成的，这可能是困难的。
步骤308生成经编辑的网页，其中使用本文的位图来检测哪些文档的哪些字段包含该人的街道名称。例如，计算机100的查询引擎可以根据需要返回编辑的值以供应当永远无法访问未编辑值的网页生成器使用。在另一个示例中，法律要求在个人要求时删除组织拥有的关于该人的所有在线数据。
本文的位图可以被用于快速检测哪些文档的哪些字段可能包含此人全名的词，而那些匹配的文档可能需要进一步检查和/或删除。无论是删除文档还是编辑值，搜索关键字都不需要线性搜索所有可用文档的内容。代替地，本文的位图可以指示大多数文档和/或列不包含关键字，并且可以避免访问那些许多不匹配的文档和/或列。
4.0示例JSON到列映射
图4是描绘实施例中JSON字段到Parquet列的示例映射的框图。图4的左侧是示例JSON文档中的示例嵌套层次结构。图4的右侧是包含来自JSON文档的文本串的示例Parquet文件。
JSON文档有五个顶级字段，它们被映射到Parquet文件中五个名称相似的列。在这个示例中，Parquet文件缺少用于嵌套在JSON文档中的子结构字段的列。例如，JSON文档中的“email”字段在Parquet文件中没有它们自己的列。代替地，整个“comments”JSON子结构作为文本串值存储在Parquet文件的comments列中。包含与评论列对应的被设置为“否”的位的词“blog”的位图可以确认没有评论提及“blog”。
在这个示例中，所示的标签是特定于应用的概念。在另一个示例中，XML元素名称(诸如<name></name>，也称为标签)的出现被识别为可以具有本文呈现的位图的词。例如，另一个Parquet文件可以具有标签列，其值是(一个或多个)XML文档中出现的所有元素名称。
5.0具有索引形成的示例性摄取
以下示例性实施例具有附加特征。这些附加特征包括语言学，诸如词干提取、停用词和词频-逆文档频率(tf-idf)。附加特征还包括用于Parquet的细节，诸如行组标识符。在Parquet中，行组是水平分区。
词频(tf)是词在文档(诸如半结构化文档)中出现的计数。逆文档频率(idf)是包含该词的文档的分数的对数倒数，诸如：
Figure BDA0004077616120000151
其中N是加索引的文档的计数，并且n是包含该词的那些文档的计数。Tf-idf＝tf×idf。例如，在每个文档中出现的词(诸如“the”)其idf为零并且tf-idf为零，这是idf和tf-idf的最小值。tf-idf低于阈值的词可以被视为停用词，其不应当被加索引并且不应当具有诸如本文所呈现的位图。在实施例中，附加的停用词由诸如“the”之类的常用词的黑名单提供。
图5是描绘示例性摄取和索引形成可以如何根据以以下次序发生的以下步骤501-509进行的流程图：
501.识别原始半结构化输入文件中的所有词。取决于应用要求，系统可以识别：a)实际数据词(诸如JSON文档中“title”字段中的词)，和b)结构词(诸如JSON中的键)，或省略该结构词。
502.在步骤1中识别出的词当中，系统应用词干提取和停用词作为可选步骤，以从索引中修剪那些词，因为预计很少(如果有的话)搜索停用词。这些非常常见的词通常不会被搜索，因为它们的区分价值非常低。词干提取需要基于其语言学上的词干而不是整个词来索引词。例如，“ran”和“running”可以被加索引为同一个词干词“run”。例如，run的位图可以模糊匹配“run”、“ran”和“running”。适应模糊在本文前面讨论过。
503.系统开始对输入文件进行Parquet摄取。在摄取期间，系统还维护到目前为止摄取的输入文本的进度。当到达行-组边界时，系统得到词列表，其中每个词都具有指示该词是否出现在每一列中的位图。系统还向当前行-组指派至少部分数字的逻辑标识符。这个逻辑标识符是那个行-组的通用唯一标识符(UUID)。用于指派这个UUID的确切算法可以因实施例而异，只要在半结构化文档的整个集合中不存在或几乎不存在与这个UUID的冲突即可。用于行-组的UUID的一个示例可以是Parquet文件名和偏移量。另一个示例可以是整个文件的消息摘要(MD5)散列，作为文件名的替代。这在文件的唯一文件名不可用的情况下是有用的-例如，当日志文件被就地覆写时，或者在摄取流时可能发生，其中流的每个水平分区得到其自己的UUID，即使流名称本身没有改变。此外，每个行-组可以以完全独立的方式通过MD5散列处理成行-组UUID。唯一的要求是这些散列之间发生冲突的概率在整个数据湖中微乎其微。
504.在摄取结束时，系统具有用于所有摄取的行-组的词的列表。这是主词列表。
505.给定主词列表，系统列出所有行-组中的所有词，这些词已被选择超过停用词准则。这些词中的每一个都被赋予任意但唯一的序号。
506.系统从词列表中为每个行-组中出现的每个词准备位图。这些位图构成文件的一阶索引。
507.系统使用tf-idf优化索引，使得频繁出现的词可以从索引创建过程中被丢弃。如果词出现在大多数列和行-组中，那么访问它们将花费与全表扫描相同的时间，因此为该词创建索引并不是那么有益。
508.一旦索引大小已减小，系统就将应用Jaccard距离对其条目进行聚类。在Jaccard距离的某个阈值内的所有词被聚类在一起。这是在给定假阳性率的情况下导致索引大小显著减小的步骤。例如，半结构化文件被摄取到五列的Parquet文件中。创建了两个行-组。词T1和T2出现在它们的一些列中。如果Jaccard距离(又名阈值)>0.7，那么它们将被聚类在一起并具有单个索引。一般而言，Jaccard相似性的阈值越高意味着每个集群中要聚类的词的百分比越低。这是因为越高的相似性阈值允许具有越高相似性的词被聚类。此外，阈值的值与索引的大小直接成正比，因为越高的阈值导致越少的聚类和越大的索引大小。步骤8中描述的聚类步骤是耗时的。对词进行聚类的时间几乎与要加索引的词数成线性关系。因此，这应当在有大量CPU和存储器可用于保存工作集的云计算环境中完成。例如，这个步骤可以在云利用率较低的时段完成，因为迫切需要完成这个步骤。通过将这个工作负载的优先级降低到较低水平，可以最小化云操作的额外负担。
509.当完成摄取过程时，这些聚类的索引与所得到的Parquet文件一起存储。通过用额外的索引信息丰富元数据，索引可以或者存储为Parquet文件的一部分，或者存储为单独的文件。标题为“PERSONAL INFORMATION INDEXING FOR COLUMNAR DATA STORAGEFORMAT”的相关的美国专利申请16/814,855中呈现了在Parquet文件中定制元数据的技术。
5.1示例性查询操作
在查询执行期间，系统检查关键字的(一个或多个)位图以获取可能包含搜索关键字的所有parquet行-组(即，至少有一列对于搜索关键字具有TRUE位的任何行-组)。由于加索引算法存在假阳性，因此它可能识别出该词有可能出现的行-组。一般而言，加索引期间越高的阈值导致越低的假阳性率，但代价是索引大小越大。
在系统获得候选行-组之后，系统使用列位来决定系统需要访问和/或加载哪一列。对于要求为每个行-组加载相同列集的标准Parquet读取器，系统应当将按位或应用于所有行-组的位图以获取列列表，即，如果任何行-组具有为TRUE的对应列位，那么将加载列。
因为从盘读取的I/O块的数量已被修剪，所以I/O大大减少。因为盘I/O比CPU每千字节处理速度至少慢1000倍，所以这显著减少了用于自由文本搜索的查询时间。使用本文的位图在查询时间上有显著改进(若干个数量级)。
一旦识别出候选列和行-组，系统元数据中的行-组UUID就将被查询以识别行-组，并且列被用于识别投影列。这个信息作为结果返回给用户并且查询完成。用户可以选择按原样对这个结果进行操作，诸如通过标准Parquet读取那些列和行-组中的数据。
6.0数据库概述
本发明的实施例在数据库管理系统(DBMS)的上下文中使用。因此，提供了示例DBMS的描述。
一般而言，诸如数据库服务器之类的服务器是集成的软件组件和诸如存储器、节点以及节点上用于执行集成的软件组件的进程之类的计算资源的分配的组合，其中软件和计算资源的组合专用于代表服务器的客户端提供特定类型的功能。数据库服务器控制并促进对特定数据库的访问，处理客户端访问数据库的请求。
用户通过向数据库服务器提交使数据库服务器对存储在数据库中的数据执行操作的命令来与DBMS的数据库服务器进行交互。用户可以是在与数据库服务器交互的客户端计算机上运行的一个或多个应用。多个用户在本文中也可以被统称为用户。
数据库包括数据和数据库字典，其存储在诸如硬盘集之类的持久性存储器机构上。数据库由其自己的分开数据库字典定义。数据库字典包括定义数据库中包含的数据库对象的元数据。实际上，数据库字典定义了数据库的大部分。数据库对象包括表、表列和表空间。表空间是用于存储各种类型的数据库对象(诸如表)的数据的一个或多个文件的集合。如果将用于数据库对象的数据存储在表空间中，那么数据库字典将数据库对象映射到保存用于数据库对象的数据的一个或多个表空间。
DBMS参考数据库字典来确定如何执行提交给DBMS的数据库命令。数据库命令可以访问由字典定义的数据库对象。
数据库命令可以是数据库语句的形式。为了使数据库服务器处理数据库语句，数据库语句必须符合数据库服务器支持的数据库语言。许多数据库服务器支持的数据库语言的一个非限制性示例是SQL，包括由诸如Oracle之类的数据库服务器支持的SQL专有形式(诸如Oracle Database 11g)。将SQL数据定义语言(“DDL”)指令发布到数据库服务器以创建或配置数据库对象，诸如表、视图或复杂类型。数据操纵语言(“DML”)指令被发布给DBMS，以管理存储在数据库结构内的数据。例如，SELECT、INSERT、UPDATE和DELETE是一些SQL实现中常见的DML指令示例。SQL/XML是在对象-关系数据库中操纵XML数据时使用的SQL的常见扩展。
多节点数据库管理系统由互连的节点组成，这些节点共享对同一数据库的访问。通常，节点经由网络互连，并在不同程度上共享对共享存储装置的访问，诸如具有对一组盘驱动器和存储在其上的数据块的共享访问。多节点数据库系统中的节点可以是经由网络互连的一组计算机(诸如工作站、个人计算机)的形式。可替代地，节点可以是网格的节点，该网格由与机架上的其它服务器刀片互连的服务器刀片形式的节点组成。
多节点数据库系统中的每个节点都托管数据库服务器。服务器(诸如数据库服务器)是集成软件组件和计算资源(诸如存储器、节点以及节点上的用于在处理器上执行集成软件组件的进程)的分配的组合，软件和计算资源的组合专用于代表一个或多个客户端执行特定功能。
可以分配来自多节点数据库系统中多个节点的资源，以运行特定的数据库服务器的软件。软件和节点中的资源的分配的每种组合都是在本文中被称为“服务器实例”或“实例”的服务器。数据库服务器可以包括多个数据库实例，其中一些或全部在单独的计算机(包括单独的服务器刀片)上运行。
6.1查询处理
查询是表达式、命令或命令集，其在被执行时，使服务器对数据集执行一个或多个操作。查询可以指定要从中确定(一个或多个)结果集的(一个或多个)源数据对象，诸如(一个或多个)表、(一个或多个)列、(一个或多个)视图或(一个或多个)快照。例如，(一个或多个)源数据对象可以出现在结构化查询语言(“SQL”)查询的FROM子句中。SQL是用于查询数据库对象的众所周知的示例语言。如本文所使用的，术语“查询”被用于指表示查询的任何形式，包括数据库语句形式的查询和用于内部查询表示的任何数据结构。术语“表”是指被查询引用或定义并且表示行的集合的任何源对象，诸如数据库表、视图或内联查询块(诸如内联视图或子查询)。
查询可以在(一个或多个)对象被加载时逐行地对来自(一个或多个)源数据对象的数据执行操作，或者在(一个或多个)对象已被加载之后对(一个或多个)整个源数据对象执行操作。由(某个)一些操作生成的结果集可以对(一个或多个)其它操作可用，并且以这种方式，可以基于某些标准将结果集过滤掉或缩小，和/或与(一个或多个)其它结果集和/或(一个或多个)其它源数据对象联接或组合。
子查询是查询的一部分或组成部分，它与查询的其它(一个或多个)部分或(一个或多个)组成部分不同，并且可以与查询的其它(一个或多个)部分或(一个或多个)组成部分分开(即，作为分开的查询)评估。查询的其它(一个或多个)部分或(一个或多个)组成部分可以形成外部查询，其可以包括或者可以不包括其它子查询。在为外部查询计算结果时，嵌套在外部查询中的子查询可以被分开评估一次或多次。
一般而言，查询解析器接收查询语句并生成查询语句的内部查询表示。通常，内部查询表示是互连的数据结构的集合，其表示查询语句的各种组件和结构。
内部查询表示可以是节点图的形式，每个互连的数据结构与节点和所表示的查询语句的组件对应。内部表示通常在存储器中生成，以用于评估、操纵和变换。
硬件概述
根据一个实施例，本文描述的技术由一个或多个专用计算设备实现。专用计算设备可以是硬连线的以执行这些技术，或者可以包括数字电子设备(诸如被持久地编程以执行这些技术的一个或多个专用集成电路(ASIC)或现场可编程门阵列(FPGA))，或者可以包括被编程为根据固件、存储器、其它存储装置或组合中的程序指令执行这些技术的一个或多个通用硬件处理器。这种专用计算设备还可以将定制的硬连线逻辑、ASIC或FPGA与定制编程相结合，以实现这些技术。专用计算设备可以是台式计算机系统、便携式计算机系统、手持设备、联网设备或者结合硬连线和/或程序逻辑以实现这些技术的任何其它设备。
例如，图6是图示可以在其上实现本发明实施例的计算机系统600的框图。计算机系统600包括总线602或用于传送信息的其它通信机构，以及与总线602耦合以处理信息的硬件处理器604。硬件处理器604可以是例如通用微处理器。
计算机系统600还包括耦合到总线602的主存储器606，诸如随机存取存储器(RAM)或其它动态存储设备，用于存储将由处理器604执行的信息和指令。主存储器606还可以用于在执行将由处理器604执行的指令期间存储临时变量或其它中间信息。当存储在处理器604可访问的非瞬态存储介质中时，这些指令使计算机系统600成为被定制以执行指令中指定的操作的专用机器。
计算机系统600还包括耦合到总线602的只读存储器(ROM)608或其它静态存储设备，用于存储用于处理器604的静态信息和指令。存储设备610(诸如磁盘、光盘或固态驱动器)被提供并耦合到总线602，用于存储信息和指令。
计算机系统600可以经由总线602耦合到显示器612(诸如阴极射线管(CRT))，用于向计算机用户显示信息。包括字母数字键和其它键的输入设备614耦合到总线602，用于将信息和命令选择传送到处理器604。另一种类型的用户输入设备是光标控件616(诸如鼠标、轨迹球或光标方向键)，用于将方向信息和命令选择传送到处理器604并用于控制显示器612上的光标移动。这种输入设备通常在两个轴(第一轴(例如，x)和第二轴(例如，y))上具有两个自由度，这允许设备指定平面中的位置。
计算机系统600可以使用定制的硬连线逻辑、一个或多个ASIC或FPGA、固件和/或程序逻辑(它们与计算机系统相结合，使计算机系统600成为或将计算机系统600编程为专用机器)来实现本文所述的技术。根据一个实施例，响应于处理器604执行包含在主存储器606中的一个或多个指令的一个或多个序列，计算机系统600执行本文所述的技术。这些指令可以从另一个存储介质(诸如存储设备610)读入到主存储器606中。包含在主存储器606中的指令序列的执行使得处理器604执行本文所述的处理步骤。在替代实施例中，可以使用硬连线的电路系统代替软件指令或与软件指令组合。
如本文使用的术语“存储介质”是指存储使机器以特定方式操作的数据和/或指令的任何非瞬态介质。这种存储介质可以包括非易失性介质和/或易失性介质。非易失性介质包括例如光盘、磁盘或固态驱动器，诸如存储设备610。易失性介质包括动态存储器，诸如主存储器606。存储介质的常见形式包括例如软盘、柔性盘、硬盘、固态驱动器、磁带或任何其它磁数据存储介质、CD-ROM、任何其它光学数据存储介质、任何具有孔图案的物理介质、RAM、PROM和EPROM、FLASH-EPROM、NVRAM、任何其它存储器芯片或盒式磁带。
存储介质不同于传输介质但可以与传输介质结合使用。传输介质参与在存储介质之间传送信息。例如，传输介质包括同轴电缆、铜线和光纤，包括包含总线602的导线。传输介质也可以采用声波或光波的形式，诸如在无线电波和红外数据通信期间生成的那些。
将一个或多个指令的一个或多个序列携带到处理器604以供执行可以涉及各种形式的介质。例如，指令最初可以在远程计算机的磁盘或固态驱动器上携带。远程计算机可以将指令加载到其动态存储器中，并使用调制解调器通过电话线发送指令。计算机系统600本地的调制解调器可以在电话线上接收数据并使用红外发送器将数据转换成红外信号。红外检测器可以接收红外信号中携带的数据，并且适当的电路系统可以将数据放在总线602上。总线602将数据携带到主存储器606，处理器604从主存储器606检索并执行指令。由主存储器606接收的指令可以可选地在由处理器604执行之前或之后存储在存储设备610上。
计算机系统600还包括耦合到总线602的通信接口618。通信接口618提供耦合到网络链路620的双向数据通信，其中网络链路620连接到本地网络622。例如，通信接口618可以是集成服务数字网(ISDN)卡、电缆调制解调器、卫星调制解调器或者提供与对应类型的电话线的数据通信连接的调制解调器。作为另一个示例，通信接口618可以是局域网(LAN)卡，以提供与兼容LAN的数据通信连接。还可以实现无线链路。在任何此类实现中，通信接口618都发送和接收携带表示各种类型信息的数字数据流的电信号、电磁信号或光信号。
网络链路620通常通过一个或多个网络向其它数据设备提供数据通信。例如，网络链路620可以提供通过本地网络622到主计算机624或到由互联网服务提供商(ISP)626操作的数据设备的连接。ISP 626进而通过全球分组数据通信网络(现在通常称为“互联网”628)提供数据通信服务。本地网络622和互联网628都使用携带数字数据流的电信号、电磁信号或光信号。通过各种网络的信号以及在网络链路620上并通过通信接口618的信号(其将数字数据携带到计算机系统600和从计算机系统600携带数字数据)是传输介质的示例形式。
计算机系统600可以通过(一个或多个)网络、网络链路620和通信接口618发送消息和接收数据，包括程序代码。在互联网示例中，服务器630可以通过互联网628、ISP 626、本地网络622和通信接口618发送对应用程序的所请求代码。
接收到的代码可以在它被接收到时由处理器604执行，和/或存储在存储设备610或其它非易失性存储装置中以供稍后执行。
软件概述
图7是可以用于控制计算系统600的操作的基本软件系统700的框图。软件系统700及其组件，包括它们的连接、关系和功能，仅仅意在是示例性的，并且不意味着限制(一个或多个)示例实施例的实现。适于实现(一个或多个)示例实施例的其它软件系统可以具有不同的组件，包括具有不同的连接、关系和功能的组件。
软件系统700被提供以用于指导计算系统600的操作。可以存储在系统存储器(RAM)606和固定存储装置(例如，硬盘或闪存)610上的软件系统700包括内核或操作系统(OS)710。
OS 710管理计算机操作的低级方面，包括管理进程的执行、存储器分配、文件输入和输出(I/O)以及设备I/O。表示为702A、702B、702C...702N的一个或多个应用程序可以被“加载”(例如，从固定存储装置610传送到存储器606中)以供系统700执行。意图在计算机系统600上使用的应用或其它软件也可以被存储为可下载的计算机可执行指令集，例如，用于从互联网位置(例如，Web服务器、app商店或其它在线服务)下载和安装。
软件系统700包括图形用户界面(GUI)715，用于以图形(例如，“点击”或“触摸手势”)方式接收用户命令和数据。进而，可以由系统700根据来自操作系统710和/或(一个或多个)应用702的指令来作用于这些输入。GUI 715还用于显示来自OS 710和(一个或多个)应用702的操作结果，用户可以对其提供附加的输入或终止会话(例如，注销)。
OS 710可以直接在计算机系统600的裸硬件720(例如，(一个或多个)处理器604)上执行。可替代地，管理程序或虚拟机监视器(VMM)730可以插入在裸硬件720和OS 710之间。在这个配置中，VMM 730充当OS 710与计算机系统600的裸硬件720之间的软件“缓冲”或虚拟化层。
VMM 730实例化并运行一个或多个虚拟机实例(“访客机”)。每个访客机包括“访客”操作系统(诸如OS 710)，以及被设计为在访客操作系统上执行的一个或多个应用(诸如(一个或多个)应用702)。VMM 730向访客操作系统呈现虚拟操作平台并管理访客操作系统的执行。
在一些情况下，VMM 730可以允许访客操作系统如同其直接在计算机系统700的裸硬件720上运行一样运行。在这些实例中，被配置为直接在裸硬件720上执行的访客操作系统的相同版本也可以在VMM 730上执行而无需修改或重新配置。换句话说，VMM 730可以在一些情况下向访客操作系统提供完全硬件和CPU虚拟化。
在其它情况下，访客操作系统可以被专门设计或配置为在VMM730上执行以提高效率。在这些实例中，访客操作系统“意识到”它在虚拟机监视器上执行。换句话说，VMM 730可以在一些情况下向访客操作系统提供半虚拟化。
计算机系统进程包括硬件处理器时间的分配以及(物理和/或虚拟)存储器的分配，存储器的分配用于存储由硬件处理器执行的指令、用于存储由硬件处理器执行指令所生成的数据、和/或用于当计算机系统进程未运行时在硬件处理器时间的分配之间存储硬件处理器状态(例如，寄存器的内容)。计算机系统进程在操作系统的控制下运行，并且可以在计算机系统上执行的其它程序的控制下运行。
云计算
本文一般地使用术语“云计算”来描述计算模型，该计算模型使得能够按需访问计算资源(诸如计算机网络、服务器、软件应用和服务)的共享池，并且允许以最少的管理工作或服务提供商交互来快速提供和释放资源。
云计算环境(有时称为云环境或云)可以以各种不同方式实现，以最好地适应不同要求。例如，在公共云环境中，底层计算基础设施由组织拥有，该组织使其云服务可供其它组织或公众使用。相反，私有云环境一般仅供单个组织使用或在单个组织内使用。社区云旨在由社区内的若干组织共享；而混合云包括通过数据和应用可移植性绑定在一起的两种或更多种类型的云(例如，私有、社区或公共)。
一般而言，云计算模型使得先前可能由组织自己的信息技术部门提供的那些职责中的一些代替地作为云环境内的服务层来交付，以供(根据云的公共/私人性质，在组织内部或外部的)消费者使用。取决于特定实现，由每个云服务层提供或在每个云服务层内提供的组件或特征的精确定义可以有所不同，但常见示例包括：软件即服务(SaaS)，其中消费者使用在云基础设施上运行的软件应用，同时SaaS提供者管理或控制底层云基础设施和应用。平台即服务(PaaS)，其中消费者可以使用由PaaS提供者支持的软件编程语言和开发工具，以开发、部署和以其它方式控制它们自己的应用，同时PaaS提供者管理或控制云环境的其它方面(即，运行时执行环境下的一切)。基础设施即服务(IaaS)，其中消费者可以部署和运行任意软件应用，和/或提供处理、存储、网络和其它基础计算资源，同时IaaS提供者管理或控制底层物理云基础设施(即，操作系统层下面的一切)。数据库即服务(DBaaS)，其中消费者使用在云基础设施上运行的数据库服务器或数据库管理系统，同时DbaaS提供者管理或控制底层云基础设施和应用。
为了说明可以用于实现(一个或多个)示例实施例的基本底层计算机组件而呈现了上述基本计算机硬件和软件以及云计算环境。但是，(一个或多个)示例实施例不必限于任何特定的计算环境或计算设备配置。代替地，根据本公开，(一个或多个)示例实施例可以在本领域技术人员将理解为能够支持本文呈现的(一个或多个)示例实施例的特征和功能的任何类型的系统体系架构或处理环境中实现。
在前面的说明书中，已经参考众多具体细节描述了本发明的实施例，这些细节可以根据实施方式有所变化。因而，说明书和附图应被视为说明性而非限制性的。本发明范围的唯一和排他性指示，以及申请人意图作为本发明范围的内容，是以发布这种权利要求的具体形式从本申请发布的权利要求集合的字面和等同范围，包括任何后续更正。

Claims (13)

1.一种计算机实现的方法，包括：
配置数据库的多个列式文件中的多个列；
对于所述多个列式文件中的每个列式文件，在该列式文件中的多个列中持久化在数据库中持久化的多个半结构化文档的相应子集中出现的相应的多个文本串；
检测出现在所述多个半结构化文档中的所述多个文本串中的多个文本词；
分别为所述多个文本词中的每个文本词并且为所述多个列式文件中的每个列式文件生成多个位图中的相应位图，该相应位图包含用于所述多个列中的每一列的相应位，所述相应位指示该文本词是否出现在列式文件的列中；
在所述多个列式文件中的每个列式文件中持久化用于该列式文件的位图；
通过访问所述多个位图以检测所述多个列式文件中的哪些列式文件包含所述多个文本词中查询所指定的特定词来执行对数据库的查询。
2.如权利要求1所述的计算机实现的方法，还包括：
测量所述多个文本词中的第一文本词的第一位图与所述多个文本词中的第二文本词的第二位图之间的相似性；
在所述多个位图中并且基于测量所述相似性，将第一文本词的第一位图和第二文本词的第二位图替换为单个位图，该单个位图具有用于所述多个列中的每一列的单个相应位。
3.如权利要求2所述的计算机实现的方法，其中测量第一位图与第二位图之间的所述相似性包括Jaccard距离。
4.如权利要求2所述的计算机实现的方法，其中访问所述多个位图包括：
基于用于所述多个列中的特定列的所述单个位图的相应位，检测该特定列的值包含以下当中的至少一个：第一文本词和第二文本词；
检测该特定列的所述值包含第一文本词而不包含第二文本词。
5.如权利要求2所述的计算机实现的方法，其中：
生成所述第一文本词的所述第一位图包括：
为所述多个列中的每一列的第一部分生成第一位图的第一实例，以及
为所述多个列中的每一列的第二部分生成第一位图的第二实例；
所述计算机实现的方法还包括将第一部分持久化在第一文件中并将第二部分持久化在第二文件中；
访问所述多个位图包括，基于第一位图的所述第二实例，不访问第二文件也不访问第二部分。
6.如权利要求5所述的计算机实现的方法，还包括：
从第一一个或多个文本文档填充所述多个列中的每一列的所述第一部分；
从第二一个或多个文本文档填充所述多个列中的每一列的所述第二部分。
7.如权利要求1所述的计算机实现的方法，还包括基于所述多个列中的至少一列访问所述多个半结构化文档中的至少一个半结构化文档。
8.如权利要求1所述的计算机实现的方法，其中所述多个文本词包括：
作为特性的名称的第三文本词，以及
作为所述特性的值的一部分的第四文本词。
9.如权利要求8所述的计算机实现的方法，还包括在同一文件中持久化所述多个位图中的至少一个位图和所述特性的所述值。
10.如权利要求1所述的计算机实现的方法，其中：
所述计算机实现的方法还包括将所述多个列中的第一列持久化在第一文件中并将所述多个列中的第二列持久化在第二文件中；
访问所述多个位图包括，基于所述多个位图中的至少一个位图，不访问第二文件也不访问第二列。
11.如权利要求1所述的计算机实现的方法，还包括基于访问所述多个位图而生成基于所述多个位图中的所述至少一个位图编辑的数据。
12.一种或多种非暂态计算机可读介质，其存储一个或多个指令序列，所述指令序列在由一个或多个处理器执行时使得执行如权利要求1-11中的任一项所述的步骤。
13.一种设备，包括：
一个或多个处理器；以及
存储器，耦合到所述一个或多个处理器并且包括存储在其上的指令，所述指令在由所述一个或多个处理器执行时使得执行如权利要求1-11中的任一项所述的步骤。
CN202180050173.2A 2020-07-15 2021-04-30 列式分析存储格式的半结构化数据的概率文本索引 Pending CN116034349A (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US16/929,949 US11514697B2 (en) 2020-07-15 2020-07-15 Probabilistic text index for semi-structured data in columnar analytics storage formats
US16/929,949 2020-07-15
PCT/US2021/030116 WO2022015392A1 (en) 2020-07-15 2021-04-30 Probabilistic text index for semi-structured data in columnar analytics storage formats

Publications (1)

Publication Number Publication Date
CN116034349A true CN116034349A (zh) 2023-04-28

Family

ID=76076456

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202180050173.2A Pending CN116034349A (zh) 2020-07-15 2021-04-30 列式分析存储格式的半结构化数据的概率文本索引

Country Status (4)

Country Link
US (1) US11514697B2 (zh)
EP (1) EP4182814A1 (zh)
CN (1) CN116034349A (zh)
WO (1) WO2022015392A1 (zh)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115698978A (zh) * 2020-07-24 2023-02-03 阿里巴巴集团控股有限公司 通过列式存储格式的全面位图索引进行高效扫描
US12099504B2 (en) * 2020-10-19 2024-09-24 Ocient Holdings LLC Utilizing array field distribution data in database systems
WO2022047250A1 (en) * 2020-08-28 2022-03-03 Open Text Holdings, Inc. Token-based data security systems and methods
US11645258B2 (en) * 2021-05-26 2023-05-09 International Business Machines Corporation Preserving metadata context in a hybrid cloud context
US11645273B2 (en) 2021-05-28 2023-05-09 Ocient Holdings LLC Query execution utilizing probabilistic indexing
US20240257164A1 (en) * 2023-01-31 2024-08-01 International Business Machines Corporation Database value prediction
US20250274622A1 (en) * 2024-02-26 2025-08-28 1776 Media Network, Inc. Data management and distribution

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104715039A (zh) * 2015-03-23 2015-06-17 星环信息科技（上海）有限公司 基于硬盘和内存的列式存储和查询方法及设备
CN107545021A (zh) * 2017-05-10 2018-01-05 新华三信息安全技术有限公司 一种数据存储方法及装置
CN108140046A (zh) * 2015-10-23 2018-06-08 甲骨文国际公司 对于任何半结构化数据格式的高效存储器中db查询处理
US20180268000A1 (en) * 2017-03-20 2018-09-20 Datameer, Inc. Apparatus and Method for Distributed Query Processing Utilizing Dynamically Generated In-Memory Term Maps
US20200210398A1 (en) * 2018-12-28 2020-07-02 Oracle International Corporation Technique of comprehensively support autonomous json document object (ajd) cloud service

Family Cites Families (54)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5625711A (en) * 1994-08-31 1997-04-29 Adobe Systems Incorporated Method and apparatus for producing a hybrid data structure for displaying a raster image
US5729637A (en) * 1994-08-31 1998-03-17 Adobe Systems, Inc. Method and apparatus for producing a hybrid data structure for displaying a raster image
US5926812A (en) 1996-06-20 1999-07-20 Mantra Technologies, Inc. Document extraction and comparison method with applications to automatic personalized database searching
US7536561B2 (en) * 1999-10-15 2009-05-19 Ebrary, Inc. Method and apparatus for improved information transactions
US6804677B2 (en) 2001-02-26 2004-10-12 Ori Software Development Ltd. Encoding semi-structured data for efficient search and browsing
US7644014B2 (en) 2001-10-17 2010-01-05 Sun Microsystems, Inc. Document exchange framework for automated extensible markup language data in an e-procurement system and method
US7171404B2 (en) 2002-06-13 2007-01-30 Mark Logic Corporation Parent-child query indexing for XML databases
US7257569B2 (en) 2002-10-31 2007-08-14 International Business Machines Corporation System and method for determining community overlap
US7356528B1 (en) 2003-05-15 2008-04-08 At&T Corp. Phrase matching in documents having nested-structure arbitrary (document-specific) markup
US8131739B2 (en) 2003-08-21 2012-03-06 Microsoft Corporation Systems and methods for interfacing application programs with an item-based storage platform
US7877400B1 (en) 2003-11-18 2011-01-25 Adobe Systems Incorporated Optimizations of XPaths
US20050216518A1 (en) * 2004-03-26 2005-09-29 Oracle International Corporation Database management system with persistent, user-accessible bitmap values
US7493305B2 (en) 2004-04-09 2009-02-17 Oracle International Corporation Efficient queribility and manageability of an XML index with path subsetting
US7499915B2 (en) 2004-04-09 2009-03-03 Oracle International Corporation Index for accessing XML data
US7370273B2 (en) 2004-06-30 2008-05-06 International Business Machines Corporation System and method for creating dynamic folder hierarchies
US7512592B2 (en) 2004-07-02 2009-03-31 Tarari, Inc. System and method of XML query processing
US7493338B2 (en) 2004-08-10 2009-02-17 Palo Alto Research Center Incorporated Full-text search integration in XML database
US9171100B2 (en) 2004-09-22 2015-10-27 Primo M. Pettovello MTree an XPath multi-axis structure threaded index
US8156156B2 (en) 2006-04-06 2012-04-10 Universita Di Pisa Method of structuring and compressing labeled trees of arbitrary degree and shape
US20080010256A1 (en) 2006-06-05 2008-01-10 Mark Logic Corporation Element query method and system
US8326819B2 (en) 2006-11-13 2012-12-04 Exegy Incorporated Method and system for high performance data metatagging and data indexing using coprocessors
US20080120283A1 (en) 2006-11-17 2008-05-22 Oracle International Corporation Processing XML data stream(s) using continuous queries in a data stream management system
US20080243799A1 (en) 2007-03-30 2008-10-02 Innography, Inc. System and method of generating a set of search results
US8578261B1 (en) 2007-06-22 2013-11-05 Adobe Systems Incorporated Active preview of hyperlink content in browser supported file-format
US20090063538A1 (en) 2007-08-30 2009-03-05 Krishna Prasad Chitrapura Method for normalizing dynamic urls of web pages through hierarchical organization of urls from a web site
US10452716B2 (en) 2008-06-07 2019-10-22 International Business Machines Corporation Optimizing complex path endpoint resolution
US8086606B1 (en) 2008-07-15 2011-12-27 Teradata Us, Inc. Performing a keyword search based on identifying exclusive lowest common ancestor (ELCA) nodes
US8832549B2 (en) * 2009-01-02 2014-09-09 Apple Inc. Identification of regions of a document
US8484210B2 (en) 2009-06-19 2013-07-09 Sybase, Inc. Representing markup language document data in a searchable format in a database system
US8700674B2 (en) 2009-07-14 2014-04-15 Hewlett-Packard Development Company, L.P. Database storage architecture
US8326839B2 (en) 2009-11-09 2012-12-04 Oracle International Corporation Efficient file access in a large repository using a two-level cache
US8239374B2 (en) 2010-01-18 2012-08-07 Microsoft Corporation Collection of performance information for search queries executed in a tiered architecture
CN102346747B (zh) 2010-08-04 2013-02-13 鸿富锦精密工业（深圳）有限公司 在数据模型中查找参数的方法
US8583652B2 (en) 2010-11-30 2013-11-12 Oracle International Corporation Efficiently registering a relational schema
US10915575B2 (en) 2012-09-28 2021-02-09 Oracle International Corporation Evaluating XML full text search
CN104079424B (zh) * 2013-03-29 2017-07-11 国际商业机器公司 用于非对称链路聚合的装置和方法
US9292564B2 (en) 2013-09-21 2016-03-22 Oracle International Corporation Mirroring, in memory, data from disk to improve query performance
US9659045B2 (en) 2013-11-08 2017-05-23 Oracle International Corporation Generic indexing for efficiently supporting ad-hoc query over hierarchically marked-up data
KR101696338B1 (ko) 2015-02-16 2017-01-13 네이버 주식회사 컬럼-인덱스 데이터 포맷을 이용하여 빅데이터를 효율적으로 처리 및 분석하는 시스템 및 방법
US20160294651A1 (en) 2015-03-31 2016-10-06 Mckesson Corporation Method, apparatus, and computer program product for monitoring an electronic data exchange
JP6397995B2 (ja) 2015-04-13 2018-09-26 株式会社日立製作所 データベース管理システム、データベースサーバ、及び、データベース管理方法
CN104881470B (zh) * 2015-05-28 2018-05-08 暨南大学 一种面向海量图片数据的重复数据删除方法
US10262012B2 (en) 2015-08-26 2019-04-16 Oracle International Corporation Techniques related to binary encoding of hierarchical data objects to support efficient path navigation of the hierarchical data objects
US10977251B1 (en) * 2015-12-30 2021-04-13 Teradata Us, Inc. Join index bitmap for non-equality query conditions
US10621370B2 (en) 2016-05-27 2020-04-14 Intel Corporation Methods and apparatus to provide group-based row-level security for big data platforms
US10789252B2 (en) 2016-09-12 2020-09-29 Oracle International Corporation Efficient evaluation of aggregate functions
US10394814B2 (en) 2017-03-08 2019-08-27 Palantir Technologies Inc. Storing nested complex data structures in a data store
US20200110476A1 (en) * 2018-10-05 2020-04-09 Kyocera Document Solutions Inc. Digital Redacting Stylus and System
US11562085B2 (en) 2018-10-19 2023-01-24 Oracle International Corporation Anisotropic compression as applied to columnar storage formats
US10657617B1 (en) * 2018-11-26 2020-05-19 GM Global Technology Operations LLC Method and apparatus for memory access management for data processing
US20200250192A1 (en) 2019-02-05 2020-08-06 Entit Software Llc Processing queries associated with multiple file formats based on identified partition and data container objects
CN110569396B (zh) * 2019-09-03 2022-05-06 上海赜睿信息科技有限公司 一种数据搜索方法、电子设备和计算机可读存储介质
US20210209088A1 (en) 2020-01-02 2021-07-08 Alibaba Group Holding Limited Method and system to support indexing in row-group columnar storage
US11238035B2 (en) 2020-03-10 2022-02-01 Oracle International Corporation Personal information indexing for columnar data storage format

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104715039A (zh) * 2015-03-23 2015-06-17 星环信息科技（上海）有限公司 基于硬盘和内存的列式存储和查询方法及设备
CN108140046A (zh) * 2015-10-23 2018-06-08 甲骨文国际公司 对于任何半结构化数据格式的高效存储器中db查询处理
US20180268000A1 (en) * 2017-03-20 2018-09-20 Datameer, Inc. Apparatus and Method for Distributed Query Processing Utilizing Dynamically Generated In-Memory Term Maps
CN107545021A (zh) * 2017-05-10 2018-01-05 新华三信息安全技术有限公司 一种数据存储方法及装置
US20200210398A1 (en) * 2018-12-28 2020-07-02 Oracle International Corporation Technique of comprehensively support autonomous json document object (ajd) cloud service

Also Published As

Publication number Publication date
US20220019784A1 (en) 2022-01-20
EP4182814A1 (en) 2023-05-24
US11514697B2 (en) 2022-11-29
WO2022015392A1 (en) 2022-01-20

Similar Documents

Publication Publication Date Title
US11514697B2 (en) Probabilistic text index for semi-structured data in columnar analytics storage formats
CN113227998B (zh) 全面支持自主json文档对象（ajd）云服务的技术
US9805079B2 (en) Executing constant time relational queries against structured and semi-structured data
US10108633B2 (en) Using a distributed prime data sieve for efficient lossless reduction, search, and retrieval of data
US10073875B2 (en) System and method of search indexes using key-value attributes to searchable metadata
JP6006267B2 (ja) 索引キーを使用して検索を絞込むシステムおよび方法
US10019284B2 (en) Method for performing transactions on data and a transactional database
US11416458B2 (en) Efficient indexing for querying arrays in databases
EP3311494B1 (en) Performing multidimensional search, content-associative retrieval, and keyword-based search and retrieval on data that has been losslessly reduced using a prime data sieve
CN117425886A (zh) 具有仅添加数据结构的基于列表的数据搜索
EP3649566B1 (en) System and method for value based region searching and associated search operators
US9659059B2 (en) Matching large sets of words
CN102722527B (zh) 一种支持含有缺失符号的查询请求的全文检索方法
Muys Building an enterprise-scale database for RDF data
Ragavan Efficient key hash indexing scheme with page rank for category based search engine big data
El Abassi et al. Deduplication Over Big Data Integration
Tung et al. An improved indexing method for Xpath queries
US20240354318A1 (en) System and method for searching tree based organizational hierarchies, including topic hierarchies, and generating and presenting search interfaces for same
Sheguri Enhancing the Queueing Process for Yioop's Scheduler
Aggarwal High Performance Document Store Implementation in Rust
Keeton et al. Automated SQL query generation for file search operations in a scale out file system

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination