{
  "id": "enwiki-001314136590",
  "slug": "worst-case-optimal-join-algorithm",
  "title": "Worst-case optimal join algorithm",
  "qid": "",
  "lead": "operate over two relations at a time, and join them on all attributes in the join condition; worst-case optimal algorithms such as generic join operate on a single attribute at a time but join all the relations on this attribute. A worst-case optimal join algorithm is an algorithm for computing relational joins with a runtime that is bounded by the worst-case output size of the join. Traditional binary join algorithms such as hash join operate over two relations at a time; joins between more than two relations are implemented by repeatedly applying binary joins. Worst-case optimal join algorithms are asymptotically faster in worst case than any join algorithm based on such iterated binary joins. The first worst-case optimal join algorithm, generic join, was published in 2012. Worst-case optimal join algorithms have been implemented in commercial database systems, including the LogicBlox system. Worst-case optimal joins have been applied to build a worst-case optimal algorithm for e-matching.",
  "body": "operate over two relations at a time, and join them on all attributes in the join condition; worst-case optimal algorithms such as generic join operate on a single attribute at a time but join all the relations on this attribute. A worst-case optimal join algorithm is an algorithm for computing relational joins with a runtime that is bounded by the worst-case output size of the join. Traditional binary join algorithms such as hash join operate over two relations at a time; joins between more than two relations are implemented by repeatedly applying binary joins. Worst-case optimal join algorithms are asymptotically faster in worst case than any join algorithm based on such iterated binary joins. The first worst-case optimal join algorithm, generic join, was published in 2012. Worst-case optimal join algorithms have been implemented in commercial database systems, including the LogicBlox system. Worst-case optimal joins have been applied to build a worst-case optimal algorithm for e-matching.",
  "categories": [
    "23603337",
    "26220375",
    "90877290"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1314136590",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1759177960.0,
  "claims": [
    {
      "id": 33650776,
      "subject_qid": "",
      "subject_slug": "worst-case-optimal-join-algorithm",
      "predicate": "publication date",
      "object_text": "2012",
      "object_num": 20120000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1314136590",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792537311.6457422,
      "confidence": 0.95,
      "article_slug": "worst-case-optimal-join-algorithm",
      "span_start": 63,
      "span_end": 81
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001314136590",
    "type": "webpage",
    "title": "Worst-case optimal join algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/worst-case-optimal-join-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          14
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          14
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001314136590",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1314136590",
    "note": "Immutable snapshot enwiki-001314136590"
  }
}